20120115, 06:08  #1 
Jan 2012
11_{8} Posts 
Sumout Test in Lucas Lehmer?
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. Last fiddled with by paramveer on 20120115 at 06:10 
20120115, 12:54  #2  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:


20120116, 02:10  #3 
Dec 2010
Monticello
5×359 Posts 
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. 
20120116, 03:04  #4 
Jan 2012
1001_{2} Posts 
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 
20120116, 12:25  #5 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 

20120127, 18:04  #6 
Nov 2011
2^{2}·3 Posts 
FFT multiplies two polynomials.
Let A(x)=2x+3; and so C(x)=A(x)*A(x)=4x^{2}+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). Last fiddled with by Maximus on 20120127 at 18:17 
20120129, 18:47  #7 
Jan 2012
3^{2} Posts 
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 ) 
20120129, 21:30  #8 
(loop (#_fork))
Feb 2006
Cambridge, England
2×3,191 Posts 

20120130, 08:23  #9  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C_{16} Posts 
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 LL 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. Quote:
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 Quote:
   Quote:
Last fiddled with by cheesehead on 20120130 at 08:42 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
A second proof for the LucasLehmer Test  carpetpool  Miscellaneous Math  2  20170730 09:21 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer primality test  CMOSMIKE  Math  5  20020906 18:46 