mersenneforum.org > Math FFT explanation for non math guys
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-20, 22:53 #34 Chaos   Sep 2005 58 Posts 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?
2006-11-03, 19:38   #35
DJones

Oct 2006

73 Posts

Quote:
 Originally Posted by ewmayer 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.

2006-11-03, 19:58   #36
ewmayer
2ω=0

Sep 2002
República de California

2×3×29×67 Posts

Quote:
 Originally Posted by DJones 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.

 2006-11-04, 10:09 #37 DJones     Oct 2006 73 Posts 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.
2006-11-04, 13:54   #38
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

24×32×53 Posts

Quote:
 Originally Posted by DJones 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.

 2007-06-16, 22:51 #39 fetofs     Aug 2005 Brazil 5528 Posts 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
2011-02-19, 14:37   #40
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

3×19×113 Posts

Quote:
 Originally Posted by fetofs 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]

 2011-02-19, 15:08 #41 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts 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
 2011-02-19, 15:19 #42 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts best thing I've found for visually seeing it is http://www.gweep.net/~shifty/portfol...eet/index.html
 2011-08-28, 15:34 #43 ciic     May 2011 FR Germany - Berlin 2×7 Posts 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.
 2011-08-28, 16:59 #44 axn     Jun 2003 19×271 Posts http://en.wikipedia.org/wiki/List_of...atical_symbols See: congruence, summation, product.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 31 2015-10-09 20:55 Unregistered Hardware 12 2006-11-03 03:53 jasong Sierpinski/Riesel Base 5 1 2006-03-22 01:06 Crystallize Lounge 6 2003-09-27 13:08 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