Go Back > Fun Stuff > Lounge

Thread Tools
Old 2019-10-18, 17:23   #1
diep's Avatar
Sep 2006
The Netherlands

11×71 Posts
Default 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.

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?
diep is offline   Reply With Quote
Old 2019-10-18, 19:32   #2
ewmayer's Avatar
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
ewmayer is offline   Reply With Quote

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.