Mersenne Digest Tuesday, July 1 2003 Volume 01 : Number 1078
---------------------------------------------------------------------- Date: Sat, 28 Jun 2003 22:23:41 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Double Checking On Saturday 28 June 2003 18:47, you wrote: > Will the 64-bit residue be the SAME when a given exponent > was originally Lucas-Lehmer tested with a 384K FFT, but > the double-check is performed using a 448K FFT ? Hopefully - in fact the whole 2^p-1 bit residue R(p) should be the same! R(2)=4 R(n+1) = R(n)^2 -2 modulo 2^p-1 I don't see how the FFT run length should affect this ... in fact the FFT is only used at all because it's the most efficient method known of doing the multiplication of very large numbers. If the residues calculated with 384K FFT & 448K FFT are different, then: - - most likely, at least one of the runs has been affected by a "glitch" of some sort; - - or, the 384K FFT run length is too small & some data value was rounded to the wrong integer during the run - I do not think that this is very likely unless serious abuse has been made of the SoftCrossoverAdjust parameter; - - or, there is a systematic error in the program code for at least one of the run lengths. Since short runs (400 or 1000 iterations) have been crosschecked with various FFT run lengths, again I do not think this is very likely. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 28 Jun 2003 22:23:41 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Double Checking On Saturday 28 June 2003 18:47, you wrote: > Will the 64-bit residue be the SAME when a given exponent > was originally Lucas-Lehmer tested with a 384K FFT, but > the double-check is performed using a 448K FFT ? Hopefully - in fact the whole 2^p-1 bit residue R(p) should be the same! R(2)=4 R(n+1) = R(n)^2 -2 modulo 2^p-1 I don't see how the FFT run length should affect this ... in fact the FFT is only used at all because it's the most efficient method known of doing the multiplication of very large numbers. If the residues calculated with 384K FFT & 448K FFT are different, then: - - most likely, at least one of the runs has been affected by a "glitch" of some sort; - - or, the 384K FFT run length is too small & some data value was rounded to the wrong integer during the run - I do not think that this is very likely unless serious abuse has been made of the SoftCrossoverAdjust parameter; - - or, there is a systematic error in the program code for at least one of the run lengths. Since short runs (400 or 1000 iterations) have been crosschecked with various FFT run lengths, again I do not think this is very likely. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 29 Jun 2003 01:42:26 -0400 From: Pierre Abbat <[EMAIL PROTECTED]> Subject: Mersenne: Squaring huge numbers I am investigating 64-100 sequences, which are chains of bases such that the number written 100 in each is written 64 in the next (e.g. 8,10,16,42). I quickly wrote a Python program to compute them. It is now computing the square of a 1555000 digit number and has been doing so since the 17th. What squaring algorithm is Python using? Is there a faster way of squaring numbers where the number of digits doubles at each iteration? phma - -- .i toljundi do .ibabo mi'afra tu'a do .ibabo damba do .ibabo do jinga .icu'u la ma'atman. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 29 Jun 2003 07:24:26 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Squaring huge numbers On Sunday 29 June 2003 05:42, Pierre Abbat wrote: > I am investigating 64-100 sequences, which are chains of bases such that > the number written 100 in each is written 64 in the next (e.g. 8,10,16,42). > I quickly wrote a Python program to compute them. It is now computing the > square of a 1555000 digit number and has been doing so since the 17th. What > squaring algorithm is Python using? I don't know offhand, but: (a) Python is interpreted; (b) the Python interpreter is open source, so it shouldn't be hard to find out how it does big integer arithmetic; (c) you might also look for a dependence on the GNU multi-precision library (GMP) since that is an obvious candidate; (d) whatever method it's using doesn't seem to be very efficient - you have been running for 10 days to execute something which mprime/Prime95 would accomplish in a small fraction of a second. > Is there a faster way of squaring > numbers where the number of digits doubles at each iteration? There is x^2 code in the published mprime/Prime95 source. To do what you require would obviously require you to hack together something to load the initial work vectors & read the result back out when you've finished. Also you would need to start with twice the FFT run length you would require for the multiplication modulo 2^p-1 (so there is room for the double-length result) & double the run length again for each squaring. But it looks more like lots of work than being difficult. An alternative approach, cobble something together using GMP, which is reasonably efficient for general work, though not blindingly so. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 29 Jun 2003 07:24:26 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Squaring huge numbers On Sunday 29 June 2003 05:42, Pierre Abbat wrote: > I am investigating 64-100 sequences, which are chains of bases such that > the number written 100 in each is written 64 in the next (e.g. 8,10,16,42). > I quickly wrote a Python program to compute them. It is now computing the > square of a 1555000 digit number and has been doing so since the 17th. What > squaring algorithm is Python using? I don't know offhand, but: (a) Python is interpreted; (b) the Python interpreter is open source, so it shouldn't be hard to find out how it does big integer arithmetic; (c) you might also look for a dependence on the GNU multi-precision library (GMP) since that is an obvious candidate; (d) whatever method it's using doesn't seem to be very efficient - you have been running for 10 days to execute something which mprime/Prime95 would accomplish in a small fraction of a second. > Is there a faster way of squaring > numbers where the number of digits doubles at each iteration? There is x^2 code in the published mprime/Prime95 source. To do what you require would obviously require you to hack together something to load the initial work vectors & read the result back out when you've finished. Also you would need to start with twice the FFT run length you would require for the multiplication modulo 2^p-1 (so there is room for the double-length result) & double the run length again for each squaring. But it looks more like lots of work than being difficult. An alternative approach, cobble something together using GMP, which is reasonably efficient for general work, though not blindingly so. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 1 Jul 2003 17:06:35 +0100 From: "Doug Feather" <[EMAIL PROTECTED]> Subject: Mersenne: What does this star mean for double checking work? This is a multi-part message in MIME format. - ------=_NextPart_000_0009_01C33FF3.2089A400 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Currently I have the following double checking work assigned: 8217767 D* 64 1539456 24.1 10.9 70.9 28-Jun-03 12:17 07-Jun-03 = 13:00 DougF 498 v19/v20 9301753 D 64 1.2 10.9 60.9 30-Jun-03 13:38 = 30-Jun-03 10:15 UBuild3 1794 v19/v20 9694667 D 65 4566464 11.2 1.9 60.9 30-Jun-03 13:38 = 20-Jun-03 10:24 UBuild3 1794 v19/v20 9697967 D 64 10.8 33.9 75.9 28-Jun-03 12:17 = 20-Jun-03 19:44 DougF 498 v19/v20 9708187 D 64 424832 9.0 5.0 62.0 01-Jul-03 14:34 = 22-Jun-03 15:54 UBuild2 1794 v19/v20 9726763 D 64 6.2 5.9 60.9 30-Jun-03 13:38 = 25-Jun-03 11:31 UBuild3 1794 v19/v20 9739237 D 64 3.4 10.0 62.0 01-Jul-03 14:34 = 28-Jun-03 05:14 UBuild2 1794 v19/v20 What does the star after the "D" mean on the first one of these? Doug. - ------=_NextPart_000_0009_01C33FF3.2089A400 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content=3D"text/html; charset=3Diso-8859-1" = http-equiv=3DContent-Type> <META content=3D"MSHTML 5.00.2919.6307" name=3DGENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=3D#ffffff> <DIV><FONT face=3DArial size=3D2>Currently I have the following double = checking work=20 assigned:</FONT></DIV> <DIV><FONT size=3D2><BR><FONT face=3D"Courier New">8217767 D* = 64 =20 1539456 24.1 10.9 70.9 28-Jun-03 = 12:17 =20 07-Jun-03 13:00 = DougF 498=20 v19/v20<BR> 9301753 D =20 64  = ; =20 1.2 10.9 60.9 30-Jun-03 13:38 30-Jun-03 = 10:15 =20 UBuild3 1794 v19/v20<BR> 9694667 = D =20 65 4566464 11.2 1.9 = 60.9 =20 30-Jun-03 13:38 20-Jun-03 10:24 =20 UBuild3 1794 v19/v20<BR> 9697967 = D =20 64  = ; =20 10.8 33.9 75.9 28-Jun-03 12:17 20-Jun-03 = 19:44 =20 DougF 498 v19/v20<BR> = 9708187=20 D 64 424832 =20 9.0 5.0 62.0 01-Jul-03 14:34 22-Jun-03 = 15:54 =20 UBuild2 1794 v19/v20<BR> 9726763 = D =20 64  = ; =20 6.2 5.9 60.9 30-Jun-03 13:38 25-Jun-03 = 11:31 =20 UBuild3 1794 v19/v20<BR> 9739237 = D =20 64  = ; =20 3.4 10.0 62.0 01-Jul-03 14:34 28-Jun-03 = 05:14 =20 UBuild2 1794 v19/v20</FONT></FONT></DIV> <DIV><FONT face=3DArial size=3D2></FONT> </DIV> <DIV><FONT face=3DArial size=3D2>What does the star after the = "D" mean on=20 the first one of these?</FONT></DIV> <DIV><FONT face=3DArial size=3D2> Doug.</FONT></DIV> <DIV> </DIV></BODY></HTML> - ------=_NextPart_000_0009_01C33FF3.2089A400-- _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #1078 *******************************