mersenneforum.org Newssites reporting faster way to multiply
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-18, 17:23 #1 diep     Sep 2006 The Netherlands 11×71 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 ewmayer ∂2ω=0     Sep 2002 República de California 101101100110102 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

 Similar Threads Thread Thread Starter Forum Replies Last Post petrw1 Other Mathematical Topics 7 2019-03-30 00:08 davar55 Puzzles 3 2013-01-07 20:23 davar55 Puzzles 18 2010-12-22 22:07 mgb Lounge 0 2008-07-28 12:54 grandpascorpion Math 5 2006-11-24 19:47

All times are UTC. The time now is 13:22.

Tue Nov 30 13:22:06 UTC 2021 up 130 days, 7:51, 0 users, load averages: 1.23, 1.34, 1.26