2019-10-18, 17:23 | #1 |
Sep 2006
The Netherlands
2×17×23 Posts |
Newssites reporting faster way to multiply
I see some websites shouting out loud about a faster way to do multiplication.
After wasting some of my time there i found the paper here. https://hal.archives-ouvertes.fr/hal-02070778/document My time is pretty limited and my knowledge limited there. What do you think of it? If i browse through the document i see on page 3 mentionned: "theorem 1.1 then implies that the DFT may be evaluated in time O( mp log(mp)). This compares favourably with the traditional FFT (fast Fourier transform) approach, which requires O(m log m) operations in (collection) C". This seems weird to me. We know p is > 1, so mp log mp is going to be larger than m log m. In short FFT, not to mention DWT, eats it alive then. Of course this is fragmentaric cut'n pasting from the text so i'm not sure what is intended in the paper. Any thoughts of those who read it fully? |
2019-10-18, 19:32 | #2 |
∂^{2}ω=0
Sep 2002
República de California
2^{3}×3×487 Posts |
This first popped up on the forum ~6 months ago, has been covered in multiple threads. The latest outbreak is here - a few posts later I give links to the older threads about the paper. Upshot: due to slow growth with n of convolution output sizes, FFT-based multiply has an added (log log n) term in the work estimate reflecting that input word sizes must decrease as n increases - observant GIMPSers may have noticed this, by way of each FFT-size doubling cutting the input word size by something around 0.25 bits or more.
The paper says that by using FFT in some "violent nested way" one can improve the basic FFT-mul's n * log n * log log n work estimate to a true n * log n one. (Your question re. the p-term is answered by the combination of the missing log log n term and the stuff hidden in the asymptotic constant implied by the O() notation). But the minimum n needed for their new improved method to possibly even begin to be competitive with existing FFT-mul methods is so fantastically huge that the result is of 0 practical significance. Last fiddled with by ewmayer on 2019-10-18 at 19:33 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
New way to multiply | petrw1 | Other Mathematical Topics | 7 | 2019-03-30 00:08 |
Multiply Pandigital 2 | davar55 | Puzzles | 3 | 2013-01-07 20:23 |
Multiply Pandigital | davar55 | Puzzles | 18 | 2010-12-22 22:07 |
Multiply | mgb | Lounge | 0 | 2008-07-28 12:54 |
Multiply Perfect Numbers | grandpascorpion | Math | 5 | 2006-11-24 19:47 |