mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-09-20, 22:53   #34
Chaos
 
Sep 2005

58 Posts
Default

I have written a program that takes (N*log2(N)) bit operations to multiply 2 N digit numbers. My question is that what else does Prime95 use to multiply so fast. Could some one explain how to make the program a bit faster? What are the techniques called, any good resources?
Chaos is offline   Reply With Quote
Old 2006-11-03, 19:38   #35
DJones
 
DJones's Avatar
 
Oct 2006

73 Posts
Default

Quote:
Originally Posted by ewmayer View Post
No, for length-6 DFT-based multiply your fundamental root of unity is not e^(i*2*pi/4) = i but rather e^(i*2*pi/6) = (1 + i*sqrt(3))/2. Call this quantity E and replace all the i's in your matrix by E's and that's the desired DFT matrix. Of course there are several symmetries you can exploit to simplify the the structure of the matrix. If E := e^(i*2*pi/n), then

1) E^j = E^(j%n), e.g. E^25 = E^(25%6) = E^1 = E;
2) E^3 = -1.

Using these, the 6x6 DFT matrix can be written as
Code:
| +1   +1   +1  +1   +1   +1 |
| +1    E  E^2  -1   -E -E^2 |
| +1  E^2   -E  +1  E^2   -E |
| +1   -1   +1  -1   +1   -1 |
| +1   -E  E^2  +1   -E  E^2 |
| +1 -E^2   -E  -1  E^2    E |
I'm new to all this and never had the option of studying natural logs, imaginary numbers, and so on - I know what they all are but can't explain them and have no comprehension about how they interact. I'm currently trying to track down good information on the web, but most of it seems to assume that you know all about it already, know what all the symbols they are using actually mean, and just need to be reminded of the formulas again. I will be resorting to getting some decent books at some point, but money's tight. Anyway, back to the point.
Does the above generation of the transform matrix need to be altered for working in a different base, or is it simply a case of converting your decimal number to the desired base and taking the length of the number in the new base as the defining factor* for the size of the transform matrix which in turn is still generated as above?

*If you'll pardon the pun.
DJones is offline   Reply With Quote
Old 2006-11-03, 19:58   #36
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2×3×29×67 Posts
Default

Quote:
Originally Posted by DJones View Post
Does the above generation of the transform matrix need to be altered for working in a different base, or is it simply a case of converting your decimal number to the desired base and taking the length of the number in the new base as the defining factor for the size of the transform matrix which in turn is still generated as above?
The transform part of the FFT-based multiply is base-independent . The base appears in the transform-based multiply in two ways:

1) The base appears explicitly in the carry step following the IFFT, and

2) The base appears implicitly in the precision-dependent limits on the sizes of inputs to the FFT.

But the actual core FFT routines are base-independent.
ewmayer is offline   Reply With Quote
Old 2006-11-04, 10:09   #37
DJones
 
DJones's Avatar
 
Oct 2006

73 Posts
Default

Marvellous, thank you. Now any chance of being pointed at a suitable site / book (preferably the former) which explains why powers of e^(i * 2 * pi / n) work as a Fourier Transform matrix. Yes, I appreciate I could google this and have done so, but mathematical functions and definitions tend to be very flexible on the web, which isn't surprising when you take into account the fact that any idiot can put a webpage up.

I also appreciate I'm coming at this from the wrong end - I stumbled across the Mersenne Primes when looking for a DC project to get involved in, and have tried to backtrack through the proofs and methods so that I understand what's going on. Unfortunately backtracking through proofs, as opposed to building on proofs you already have, is proving to be rather convoluted.
DJones is offline   Reply With Quote
Old 2006-11-04, 13:54   #38
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

24×32×53 Posts
Default

Quote:
Originally Posted by DJones View Post
Now any chance of being pointed at a suitable site / book (preferably the former) which explains why powers of e^(i * 2 * pi / n) work as a Fourier Transform matrix. Yes, I appreciate I could google this and have done so, but mathematical functions and definitions tend to be very flexible on the web.
Try googling "roots of unity" instead.
Prime95 is offline   Reply With Quote
Old 2007-06-16, 22:51   #39
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

5528 Posts
Default

I tried to use the fft function that came with the matrix package (numpy) of python (If I can't even use a pre-made, how can I write one?). First I made a stupid error, and then I got it to work. I then realized it returned results like:

Code:
myfft(987654321, 123456789) -> 121932631112626272
987654321*123456789         -> 121932631112635269
Are the imprecisions normally that big? If so, how do you fix it? Or it just doesn't matter?

Last fiddled with by fetofs on 2007-06-16 at 22:51
fetofs is offline   Reply With Quote
Old 2011-02-19, 14:37   #40
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

3×19×113 Posts
Default

Quote:
Originally Posted by fetofs View Post
I tried to use the fft function that came with the matrix package (numpy) of python (If I can't even use a pre-made, how can I write one?). First I made a stupid error, and then I got it to work. I then realized it returned results like:

Code:
myfft(987654321, 123456789) -> 121932631112626272
987654321*123456789         -> 121932631112635269
Are the imprecisions normally that big? If so, how do you fix it? Or it just doesn't matter?
No, the calculation is generally exact - if any digit in the output ever comes out as further than 0.4 from its nearest integer then you start again with a longer FFT (that is, a smaller base).

I wonder whether you're transforming back from an array of digits to an integer using (double-precision) FP rather than exact integer arithmetic; could you post your code?

You should be doing the FFT on an array of at least eighteen entries if you're working with nine-digit inputs, set up with contents like
[0,0,0,0,0,0,0,0,0,9,8,7,6,5,4,3,2,1]
fivemack is online now   Reply With Quote
Old 2011-02-19, 15:08   #41
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

I said i couldn't understand but I've heard of FFT and next thing I know it's not even here. I'd love to learn it but I fear any explanation is above me. This thread shows up 7th for fft explanation on google already.

Last fiddled with by science_man_88 on 2011-02-19 at 15:13
science_man_88 is offline   Reply With Quote
Old 2011-02-19, 15:19   #42
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

best thing I've found for visually seeing it is http://www.gweep.net/~shifty/portfol...eet/index.html
science_man_88 is offline   Reply With Quote
Old 2011-08-28, 15:34   #43
ciic
 
ciic's Avatar
 
May 2011
FR Germany - Berlin

2×7 Posts
Question Books 'N Bagels

As Bagels usually have one - a hole - also, I might think, there's one in my own knowledge about the notation of the math.

'Cose: got me two books, first the famous one authored by Richard Crandall & Carl Pomerance: "Prime Numbers - A Computational Perspective" and 2nd a rather old book authored by Bruce, J.W, Giblin P.J., Rippon, P.J "Microcomputers and Mathematics" - with I found rather helpful and interesting.

My problem comes more with the first mentioned book by Crandall et al. it uses mathm. notations which I do not understand, e.g. an "=" with three horizontal lines and sum-signs and pi-signs and brackets...

Could someone please give me a hint, where I probaply could get information on this? Some "search-strings" for an extended google/amazon/wikipedia-search would also be very much helpful to me.

Cheers, ciic.
ciic is offline   Reply With Quote
Old 2011-08-28, 16:59   #44
axn
 
axn's Avatar
 
Jun 2003

19×271 Posts
Default

http://en.wikipedia.org/wiki/List_of...atical_symbols

See: congruence, summation, product.
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Any technology you guys are excited about? jasong Lounge 31 2015-10-09 20:55
These dell guys can't possibly be serious... Unregistered Hardware 12 2006-11-03 03:53
You guys are famous jasong Sierpinski/Riesel Base 5 1 2006-03-22 01:06
Hi guys ! Crystallize Lounge 6 2003-09-27 13:08
How do you guys do this? ThomRuley Lone Mersenne Hunters 1 2003-05-29 18:17

All times are UTC. The time now is 21:47.


Thu Oct 21 21:47:27 UTC 2021 up 90 days, 16:16, 1 user, load averages: 1.96, 2.10, 2.15

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.