mersenneforum.org Sumout Test in Lucas Lehmer?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-01-15, 06:08 #1 paramveer   Jan 2012 32 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 2012-01-15 at 06:10
2012-01-15, 12:54   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

2·5·839 Posts

Quote:
 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.

 2012-01-16, 02:10 #3 Christenson     Dec 2010 Monticello 70316 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.
 2012-01-16, 03:04 #4 paramveer   Jan 2012 32 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
2012-01-16, 12:25   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

2·5·839 Posts

Quote:
 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.

 2012-01-27, 18:04 #6 Maximus   Nov 2011 22·3 Posts FFT multiplies two polynomials. Let A(x)=2x+3; and so C(x)=A(x)*A(x)=4x2+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 2012-01-27 at 18:17
 2012-01-29, 18:47 #7 paramveer   Jan 2012 32 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 )
2012-01-29, 21:30   #8
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2·7·461 Posts

Quote:
 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)

2012-01-30, 08:23   #9

"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts

Quote:
 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.

Quote:
 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

Quote:
 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.

- - -

Quote:
 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.

Last fiddled with by cheesehead on 2012-01-30 at 08:42

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 carpetpool Miscellaneous Math 2 2017-07-30 09:21 Mathsgirl Information & Answers 23 2014-12-10 16:25 storm5510 Math 22 2009-09-24 22:32 CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 10:31.

Sat Aug 13 10:31:05 UTC 2022 up 37 days, 5:18, 2 users, load averages: 0.75, 0.86, 0.95