mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2011-11-10, 23:36   #1
Maximus
 
Nov 2011

11002 Posts
Default 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?
Maximus is offline   Reply With Quote
Old 2011-11-10, 23:58   #2
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

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.
Christenson is offline   Reply With Quote
Old 2011-11-11, 00:11   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

143568 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2011-11-11, 13:09   #4
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

194A16 Posts
Default

Quote:
Originally Posted by Christenson View Post
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
davieddy is offline   Reply With Quote
Old 2011-11-18, 11:03   #5
Maximus
 
Nov 2011

1210 Posts
Default

Thanks for replies.
It seems I have found nothing new.
Maximus is offline   Reply With Quote
Old 2011-11-18, 20:42   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by Maximus View Post
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. :-)
cheesehead is offline   Reply With Quote
Old 2011-11-19, 04:22   #7
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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....
Christenson is offline   Reply With Quote
Old 2011-11-20, 02:14   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

265278 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
ewmayer is offline   Reply With Quote
Old 2012-01-29, 21:26   #9
Maximus
 
Nov 2011

22×3 Posts
Lightbulb 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?
Maximus is offline   Reply With Quote
Old 2012-01-30, 22:41   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Windows 10 in Ubuntu, good idea, bad idea, or...? jasong jasong 8 2017-04-07 00:23
A Fib expression with multiplication MattcAnderson Homework Help 5 2016-11-01 08:16
5 digit multiplication MattcAnderson Puzzles 8 2014-12-05 15:09
New Multiplication Algorithm vector Miscellaneous Math 10 2007-12-20 18:16
Multiplication Tendency clowns789 Miscellaneous Math 5 2005-03-11 00:23

All times are UTC. The time now is 06:38.

Thu Mar 4 06:38:31 UTC 2021 up 91 days, 2:49, 1 user, load averages: 3.28, 2.84, 2.61

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.