Hi,
I'm trying to understand Crandall's algorithm but I'm not sure to get the
idea behind it. So let me explain you what I've understand and I would
appreciate it if you could tell me if I got it right.
We have two numbers A and C that we decompose like this:
A = a0*b^0 + a1*b^1 + a2*b^2 + a3*b^3 ...
B = c0*b^0 + c1*b^1 + c2*b^2 + c3*b^3 ...
where b is any base.
then we store the coefficients ai and ci in 2 arrays and A*B is equivalent
to the convolution of these 2 arrays.
If my reasonning is OK then my first question is how the algorithm choose b
?
Also, I found somewhere a text written by George Woltman that resume
Crandall's algorithm :
1. Multiply every FFT element by a "magic number".
2. Perform an FFT.
3. Do a complex squaring of each FFT element.
4. Perform an inverse FFT.
5. Divide every FFT element by the "magic number" and divide by N.
6. Round every FFT element to an integer.
7. Propagate carries.
8. Subtract 2 from first FFT element.
9. Loop.
I was wondering what is the purpose of the "magic number" (it is two_to_phi
in lucas.c) ?
It looks to me that the "magic number" is superfluous and that the
algorithm could work without it, no ?
Next, in the lucas.c file header, it is written:
Usage:
% lucas q N [n] [err]
where q = Mersenne exponent, N = fft run-length, n = Number of
Lucas iterations (or 0 for full test), err = 1 to report maximum
convolution errors.
N can be any power-of-two for which two conditions are met:
q/N < 32, and the maximum convolution error is < 0.5 for every
Lucas-Lehmer iteration.
Is there someone that could be able to explain me the reasons that are
behind the 2 conditions (q/N < 32 and maximum convolution error is < 0.5
for every Lucas-Lehmer iteration ) (BTW, sorry for my ignorance but what
does maximum convolution error mean ?)
TIA
Olivier Langlois - [EMAIL PROTECTED] -
http://www3.sympatico.ca/olanglois
Electrical Engineering Student
�cole de Technologie Sup�rieure - http://www.etsmtl.ca
Montreal, Canada
