20111110, 23:36  #1 
Nov 2011
2^{2}·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? 
20111110, 23:58  #2 
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 overreaction to your last post prevent you from learning some math, either. 
20111111, 00:11  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
2·3,191 Posts 
Maximus is entirely right that signeddigit 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 floatingpoint 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^20element 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 20111111 at 00:18 
20111111, 13:09  #4  
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
Quote:
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 20111111 at 13:43 

20111118, 11:03  #5 
Nov 2011
2^{2}×3 Posts 
Thanks for replies.
It seems I have found nothing new. 
20111118, 20:42  #6 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
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. :) 
20111119, 04:22  #7 
Dec 2010
Monticello
5·359 Posts 

20111120, 02:14  #8  
∂^{2}ω=0
Sep 2002
República de California
2·7·829 Posts 
Quote:


20120129, 21:26  #9 
Nov 2011
2^{2}×3 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 10base K(x) may looks like K(x)=x^{3}9x^{2}10x, or K(x)=x^{5}10x^{4}+x^{2}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(S^{2}) (and may be in numbers in intermediates while IFFT is processed). It will lead to smaller coefficients in resulting polynomial S^{2} after IFFT, I think. Will it works? Is this idea new? 
20120130, 22:41  #10 
Tribal Bullet
Oct 2004
2·3·19·31 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Windows 10 in Ubuntu, good idea, bad idea, or...?  jasong  jasong  8  20170407 00:23 
A Fib expression with multiplication  MattcAnderson  Homework Help  5  20161101 08:16 
5 digit multiplication  MattcAnderson  Puzzles  8  20141205 15:09 
New Multiplication Algorithm  vector  Miscellaneous Math  10  20071220 18:16 
Multiplication Tendency  clowns789  Miscellaneous Math  5  20050311 00:23 