3 ms·
From my understanding, this won't have any implications on the way ALUs are designed, correct? I was taught that Russian Peasant multiplication[1] was the most
by dwrodri 7y ago
From my understanding, this won't have any implications on the way ALUs are designed, correct? I was taught that Russian Peasant multiplication[1] was the most straightforward method for implementing multiplication efficiently on hardware. I would have to imagine that performing a Fast Fourier Transform (FFT from the paper) would add significant overhead. Can anyone more familiar with ALU design confirm or deny this?
[1] = http://mathforum.org/dr.math/faq/faq.peasant.html http://mathforum.org/dr.math/faq/faq.peasant.html
- acqq 7y agoFFT is already integrated in the libraries, e.g.: "GNU multiple precision arithmetic library" https://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms.html#Mul... "NxN limb multiplications and squares are done using one of seven algorithms, as the size N increases. Algorithm Threshold ... FFT MUL_FFT_THRESHOLD"
- hinkley 7y agoIs my math off or is RP already nlogn? Edit: I see my error. N is number of digits, not size of number. By our usual definition of n, table multiplication is log10(n)², which is much smaller.