An idea for implementation of FFT multiplication.

[Maximus]

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?

[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.

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.

[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.

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.

[davieddy]

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

[Maximus]

Thanks for replies.
It seems I have found nothing new.

[cheesehead]

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. :-)

[Christenson]

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....

[ewmayer]

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.

[Maximus]

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)=x³-9x²-10x, or K(x)=x⁵-10x⁴+x²-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²) (and may be in numbers in intermediates while IFFT is processed). It will lead to smaller coefficients in resulting polynomial S² after IFFT, I think.
Will it works? Is this idea new?

[jasonp]

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.