Hmmm... for some odd reason I didn't post the sec/iteration for a large FFT
(someone pointed this out to me)
So I ran JavaLucas with an FFT of 256k Its getting 1.75 sec/iteration. So...
not too shabby really...
Anyways, on to the questions:
1) What the algorithm for finding the best FFT size. I was doing:
int n = 1;
int mm = q/16+1;
while (n < mm) n <<= 1;
n>>=1;
but that is wrong...
So I looked at MacLucasUNIX, and it has:
while (n < ((BIG_DOUBLE)q)/ROUNDED_HALF_MANTISSA + 4.0)
n <<= 1;
size = n + ((n & MASK) >> SHIFT);
What I can't find is where the ROUNDED_HALF_MANTISSA came from, and why the
mask and shift operation?
2) I'm looking at the code, in Lucac.c and it looks like:
a) create the scrambled array scrambled[j] = n[permute[j-1]] *
two_to_phi[permute[j-1]]
(not quite sure why)
b) it converts the scrambled array to fft, squares it, does the
inverse fft...
c) multiplies the scrambled array * two_to_minusphi
(Is this the mod here???)
d) calls addsignal
(this one has me lost)
e) calls patch
(carry?)
So, my question is, where is the subtraction?
n = (n*n-2) % (2**p-1)
I see the square, I see (I think) the mod... wheres the -2?
3) I was thinking in the shower this morning... (Odd ain't it?)
And for all n < 2**p-1, the answer will always be n*n-2 right? Also, if n <
sqrt(MAXLONG), then we can do it in place without the FFT...
Just looking at some data sets, the odd of n being less than sqrt(MAXLONG)
is actually not to bad... (especially in Java which has 64-bit longs)...
So where does this short cut fit in? (with a big FFT, this can be a big
difference (I think))...
Thanks for any help
-Jeremy
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
