20050920, 22:53  #34 
Sep 2005
5_{8} 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?

20061103, 19:38  #35  
Oct 2006
73 Posts 
Quote:
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. 

20061103, 19:58  #36  
∂^{2}ω=0
Sep 2002
República de California
2×3×29×67 Posts 
Quote:
1) The base appears explicitly in the carry step following the IFFT, and 2) The base appears implicitly in the precisiondependent limits on the sizes of inputs to the FFT. But the actual core FFT routines are baseindependent. 

20061104, 10:09  #37 
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. 
20061104, 13:54  #38  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{4}×3^{2}×53 Posts 
Quote:


20070616, 22:51  #39 
Aug 2005
Brazil
552_{8} Posts 
I tried to use the fft function that came with the matrix package (numpy) of python (If I can't even use a premade, 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 Last fiddled with by fetofs on 20070616 at 22:51 
20110219, 14:37  #40  
(loop (#_fork))
Feb 2006
Cambridge, England
3×19×113 Posts 
Quote:
I wonder whether you're transforming back from an array of digits to an integer using (doubleprecision) 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 ninedigit inputs, set up with contents like [0,0,0,0,0,0,0,0,0,9,8,7,6,5,4,3,2,1] 

20110219, 15:08  #41 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·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 20110219 at 15:13 
20110219, 15:19  #42 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
best thing I've found for visually seeing it is http://www.gweep.net/~shifty/portfol...eet/index.html

20110828, 15:34  #43 
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 sumsigns and pisigns and brackets... Could someone please give me a hint, where I probaply could get information on this? Some "searchstrings" for an extended google/amazon/wikipediasearch would also be very much helpful to me. Cheers, ciic. 
20110828, 16:59  #44 
Jun 2003
19×271 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any technology you guys are excited about?  jasong  Lounge  31  20151009 20:55 
These dell guys can't possibly be serious...  Unregistered  Hardware  12  20061103 03:53 
You guys are famous  jasong  Sierpinski/Riesel Base 5  1  20060322 01:06 
Hi guys !  Crystallize  Lounge  6  20030927 13:08 
How do you guys do this?  ThomRuley  Lone Mersenne Hunters  1  20030529 18:17 