mersenneforum.org An idea for implementation of FFT multiplication.
 Register FAQ Search Today's Posts Mark Forums Read

 2011-11-10, 23:36 #1 Maximus   Nov 2011 22·3 Posts An idea for implementation of FFT multiplication. I don't know if a following idea is implemented in Prime95 already, so I just tell, what I think. We can use negative digits in the numbers, so digits after an iteration before carrying may be 4 times less. It will cause smaller errors and it will be possible to increase exponent tested for the same FFT size. Example 1374 -> 14(-3)4 Am I right?
 2011-11-10, 23:58 #2 Christenson     Dec 2010 Monticello 5·359 Posts Negative digits (and therefore a nonunique representation of a number) is an interesting concept, but I don't think it maps well to binary numbers. For what it's worth, I don't think that the numbers being used internally by Prime95 (or any of the other programs) are represented as decimals except on input and output. The arithmetic simply isn't optimised that way....it's all binary/base 256, depending on whether you decide for the moment that the contents of a byte is a digit or not. I suspect that what you will find is that the extra bit(s) required to do a signed digit representation probably make operations more complicated, but I'll have to defer to someone with implementation experience to help figure this out. But I'll warn you, those guys are very, very sharp, and have been at it a long time, so don't get your hopes up...but don't let the over-reaction to your last post prevent you from learning some math, either.
 2011-11-11, 00:11 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×7×461 Posts Maximus is entirely right that signed-digit representation is nice for FFT multiplies, precisely because it makes the products on average four times smaller and means many things are distributed symmetrically around zero in a way that fits nicely into the floating-point unit and the statistics. So the FFT code does already use it. Christenson: for the FFT we're looking at base 2^20 or so (note that an exponent around 20 million uses a 2^20-element FFT) rather than pure binary - the important requirement is that, for an FFT of size N using digits with values up to d, N*d^2 is small enough that it can be recovered as an integer after whatever rounding errors are introduced by the two FFTs for the squaring. Last fiddled with by fivemack on 2011-11-11 at 00:18
2011-11-11, 13:09   #4
davieddy

"Lucan"
Dec 2006
England

647410 Posts

Quote:
 Originally Posted by Christenson Negative digits (and therefore a nonunique representation of a number) is an interesting concept, but I don't think it maps well to binary numbers.
It's more than interesting: it's useful.
You know about the convention in FP that the first bit is always 1, so it is tacitly assumed.
There is the "sign" bit which can add an extra bit as well.

David

Last fiddled with by davieddy on 2011-11-11 at 13:43

 2011-11-18, 11:03 #5 Maximus   Nov 2011 22×3 Posts Thanks for replies. It seems I have found nothing new.
2011-11-18, 20:42   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by Maximus Thanks for replies. It seems I have found nothing new.
We thank you for trying!

Please, if you think you have thought of another improvement:

1. Try researching here and elsewhere to see whether it's already been discussed.

2. If you can't find any other mention after a sincere search, then ask about it here, as you did this time. Most GIMPSters will respond courteously, though I can't guarantee that all will. :-)

2011-11-19, 04:22   #7
Christenson

Dec 2010
Monticello

5·359 Posts

Quote:
 Originally Posted by cheesehead We thank you for trying! Most GIMPSters will respond courteously, though I can't guarantee that all will. :-)
There is only one discourteous one, and he got himself banned this week...just so you know, getting him mad at you means you have been baptised....

2011-11-20, 02:14   #8
ewmayer
2ω=0

Sep 2002
República de California

101101110111002 Posts

Quote:
 Originally Posted by fivemack Maximus is entirely right that signed-digit representation is nice for FFT multiplies, precisely because it makes the products on average four times smaller and means many things are distributed symmetrically around zero in a way that fits nicely into the floating-point unit and the statistics. So the FFT code does already use it.
The now-standard term for this is "balanced-digit representation." A useful simple illustrative exercise is to consider the 0-index ("DC") output of a length-N DFT, which is just the sum of all N inputs. For purposes of large-integer multiply. we square that and then do an inverse DFT, and cannot afford to lose any significant bits in the process. Compare the kind of input-size limits that result for the 2 types of input-digit representations.

 2012-01-29, 21:26 #9 Maximus   Nov 2011 C16 Posts Carrying while doing iFFT Hello again! What if we do carrying before IFFT is fully completed? We cannot do exact carrying of course, but what about a "partial" carrying? Let's call some polynomial K(x) as carrying polynomial. For 10-base K(x) may looks like K(x)=x3-9x2-10x, or K(x)=x5-10x4+x2-10x, or other forms. So if we add K(x) to some polynomial A(x) then a partial carrying will occur. If we choose proper K(x) then find its FFT (and intermediate values may be) then we can try to reduce sum of numbers in FFT(S2) (and may be in numbers in intermediates while IFFT is processed). It will lead to smaller coefficients in resulting polynomial S2 after IFFT, I think. Will it works? Is this idea new?
 2012-01-30, 22:41 #10 jasonp Tribal Bullet     Oct 2004 354510 Posts You would need to know what carry propagation looks like in the transform domain. I have no idea how such a 'propagate carry' signal would be represented.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 8 2017-04-07 00:23 MattcAnderson Homework Help 5 2016-11-01 08:16 MattcAnderson Puzzles 8 2014-12-05 15:09 vector Miscellaneous Math 10 2007-12-20 18:16 clowns789 Miscellaneous Math 5 2005-03-11 00:23

All times are UTC. The time now is 08:43.

Fri Aug 19 08:43:23 UTC 2022 up 1 day, 6:11, 0 users, load averages: 0.80, 0.94, 0.97