Hi to all:
George Woltman wrote:
>
> P.S. A brief explanation of convolution errors: Since the FFT in prime95
> is done in floating point arithmetic, round-off errors build up. After the
> FFT, every value is rounded back to an integer. The convolution error is
> the largest amount that a result value differs from the correct integer
> value. If the convolution error exceeds 0.5, then the round-back-to-integer
> step will round to the wrong integer value - a catastrophic failure.
>
> Another way to look at this: Each FFT value contains about 20 bits of data.
> That is, values ranging from 2^19 to -2^19. Consider an FFT of 128K elements.
> If each FFT value was close to the 2^19 value, then each result value would
> need 19+19+17=55 bits to hold the result. Since a float only holds 53 bits
> there would be a loss of information. Fortunately, probability assures us
> that it is extremely unlikely that every (or even most) FFT values will
> be close to the 2^19 maximum value.
>
I'm not sure I've understood that correctly. FFT's is a good method to
evaluate convolution products in O(n log n) time instead of O (n*n).
Well, let M(p) prime, thus if the first term in L-L test L(0)=4, we will
get L(p-2)=0 mod M(p). And we also get L(p-3)*L(p-3)=2 mod M(p) which
have two solutions. One is 2^((p+1)/2), and in its binary expansion we
only have one '1' and all remaining bits are 0. The last convolution
would be very easy.
*BUT* what if L(p-3) is -2^((p+1)/2) ?.
All bits in L(p-3) are '1' except only one '0'. If we perform a
convolution for L(p-3)*L(p-3) we can have problems if we have no bits
enough. MURPHY THEOREM: We will fault in last iteration and we will let
go a big prime... and 50000$. :-(
Likely, internal representation in each iteration are no the bits of
binary expansion in float form, (I haven't studied in detail the FFT
George uses), so don't worry. ;-)
----------------------------------
| Guillermo Ballester Valor |
| [EMAIL PROTECTED] |
| c/ cordoba, 19 |
| 18151-Ogijares (Spain) |
----------------------------------
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
