mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2012-01-15, 06:08   #1
paramveer
 
Jan 2012

32 Posts
Default 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
paramveer is offline   Reply With Quote
Old 2012-01-15, 12:54   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by paramveer View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-01-16, 02:10   #3
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

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.
Christenson is offline   Reply With Quote
Old 2012-01-16, 03:04   #4
paramveer
 
Jan 2012

118 Posts
Default

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
paramveer is offline   Reply With Quote
Old 2012-01-16, 12:25   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by paramveer View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-01-27, 18:04   #6
Maximus
 
Nov 2011

C16 Posts
Default

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
Maximus is offline   Reply With Quote
Old 2012-01-29, 18:47   #7
paramveer
 
Jan 2012

916 Posts
Default

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 )
paramveer is offline   Reply With Quote
Old 2012-01-29, 21:30   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×3,191 Posts
Default

Quote:
Originally Posted by paramveer View Post
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)
fivemack is offline   Reply With Quote
Old 2012-01-30, 08:23   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by paramveer View Post
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
cheesehead is offline   Reply With Quote
Reply

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 2018-03-11 23:20
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer primality test CMOSMIKE Math 5 2002-09-06 18:46

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

Fri Mar 5 19:10:58 UTC 2021 up 92 days, 15:22, 1 user, load averages: 1.65, 1.69, 1.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.