mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

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

26×11 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.

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?
diep is offline   Reply With Quote
Old 2019-10-18, 19:32   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·5,813 Posts
Default

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
Reply

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 07:12.

Tue Apr 20 07:12:48 UTC 2021 up 12 days, 1:53, 0 users, load averages: 3.35, 2.92, 2.82

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.