Sumout Test in Lucas Lehmer?

[paramveer]

While implementing torture test,i found following issue:
1)when doing SumOut test:What are the actual values tested?
->Acc to GIMPS Test checks:
(sum of the input FFT values)2 = (sum of the output IFFT values)

->below is what i understood
For eg:
if i have to square 4 using FFT then,
input to fft is (4,4)
OUtput of iFFT is 16.

According to above: (4+4)^2=64.
which is not equal to 16.

[science_man_88]

Originally Posted by paramveer

While implementing torture test,i found following issue:
1)when doing SumOut test:What are the actual values tested?
->Acc to GIMPS Test checks:
(sum of the input FFT values)2 = (sum of the output IFFT values)

->below is what i understood
For eg:
if i have to square 4 using FFT then,
input to fft is (4,4)
OUtput of iFFT is 16.

According to above: (4+4)^2=64.
which is not equal to 16.

d(x+y) means multiply last I checked not exponentiation so it becomes (4+4)*2 = (8)*2=16 not 64.

[Christenson]

Dear Paramveer:
SM88 is right, you should be calculating (4+4)*2.

To get an intuitive grasp for this, the fourier transform is a linear operation, and so is its inverse. FFT means fast fourier transform, that is, certain arithmetic tricks have been found (and popularised by Cooley and Tuckey) to make it go faster than it would if you followed the classical definition.

Therefore, if the input terms double, so must the output terms. This means, as SM88 says, that the operation on the sum of terms MUST be multiplication or division by a constant, since any other operation would not preserve linearity.

[paramveer]

then how will it be correct in case of squaring 5
-> input(5,5)
-> output=25

=> test::
-> (5+5)*2=10*2=20

-> 20!=25

[science_man_88]

Originally Posted by paramveer

then how will it be correct in case of squaring 5
-> input(5,5)
-> output=25

=> test::
-> (5+5)*2=10*2=20

-> 20!=25

even using exponentiation you wouldn't be that close 10^2=100 a lot farther away.

[Maximus]

FFT multiplies two polynomials.
Let A(x)=2x+3;
and so C(x)=A(x)*A(x)=4x²+12x+9.
In this case we get:
INPUT(0,0,2,3), and SUMINPUT=5,
OUTPUT(0,4,12,9) and SUMOUT=25.
It is due to SUMINPUT=A(1), SUMOUT=C(1) and C(1)=A(1)*A(1).

SUMINPUT and SUMOUT calculates the sum of the coefficients of polynomial, not the value.

In case of squaring 5 we get:
INPUT(0,0,0,5);
OUTPUT(0,0,0,25).

[paramveer]

I am still not getting,please see below:
let A(x)=x+2
B(x)=x+1

and C(x)=A(x)*(B(x)
then SumInput=Coeff(A)+ coeff(B)
ie, (1+2) + (1+1)
ie. 5
and square =5^2=25

C(x)= (x+2)(x+1)=x^2+3x + 2
sumout=coeff(C)
(1+3+2)
=6

now Suminput^2 NOT EQUAL sumout(25 != 6 )

[fivemack]

Originally Posted by paramveer

I am still not getting,please see below:
let A(x)=x+2
B(x)=x+1

and C(x)=A(x)*B(x)

That's where you've gone wrong; let C(x) = A(x)^2 = x^2 + 4*x + 4, and the sum of coefficients of C(x) is 9 which is the square of the sum of the coefficients of A(x)

[cheesehead]

Originally Posted by paramveer

I am still not getting,

That's because the definition "(sum of the input FFT values)^2 = (sum of the output IFFT values)" applies to only the case where the two input FFTs are equal.

It's not the definition of the more general case where the two input FFTs are not equal.

Since the L-L test involves only multiplications of two identical FFTs (i.e., squaring), never the more general case, the sumout rule in GIMPS is presented as involving the square of inputs, without noting that the square is only the specific case of a product.

please see below:
let A(x)=x+2
B(x)=x+1

and C(x)=A(x)*(B(x)

The sumout involves the product of the two sums of input coefficients.

That product would be the same as the square only if the coefficients of A(x) and B(x) were equal.

Sum of Coeff(A) = 1+2 = 3
Sum of Coeff(B) = 1+1 = 2

Product = 3 * 2 = 6

C(x)= (x+2)(x+1)=x^2+3x + 2
sumout=coeff(C)
(1+3+2)
=6

... so the product of the two sums of input coefficients does equal the sum of the output coefficients in the general multiplication case.

- - -

then SumInput=Coeff(A)+ coeff(B)
ie, (1+2) + (1+1)
ie. 5
and square =5^2=25

If you hadn't had the mistaken idea that squaring, rather than product, was a fundamental operation of the general sumout test, you'd probably have noticed that (1+2) * (1+1) = 3 * 2 is what you wanted, not (1+2) + (1+1) = 5.