20031002, 16:27  #12  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Let m and n be the exponents of the two Mersenne numbers we're doing in parallel. For simplified analysis, assume that m is less than, but close to, n (m < n << m log m), so that the execution time and space for 2^n1 are only slightly more than those for 2^m1. As you've already pointed out, the modulo (2^m1)*(2^n1) will not be as efficiently calculated as a modulo (2^k1) would be, unless someone comes up with an algorithmic improvement. Even if the algorithmic efficency were the same: as you also pointed out, each modulo (2^m1)*(2^n1) calculation would involve (m+n)bit numbers, which are larger than (2m)bit numbers. Doubling the size of the numbers would already more than double the computation time (there's a log m factor), and this is even slightly worse. So each step of modulo (2^m1)*(2^n1) arithmetic takes more time (and more space) than the time (and space) required for the combination of separate mod 2^m1 and mod 2^n1 steps. This applies only up to the S(m1) step, but that is almost all the way to S(n1) anyway. There's just no savings to be had. 

20031007, 20:32  #13 
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Other ideas I have been dwelling on in LL testing seem equally fruitless; still one can hope.
Since the work involved in LL testing seems to not have any shortcuts, the only other options are to extract more meaning from the work done or abort the sequence sooner if possible. I believe that if any value repeats in a LL sequence, the generator is in a cycle and don't think it is necessary to continue any further. Maybe that there could be a chance to get somewhere by trying to factor the number using the LL sequence values as data for Pollard's rho method. Looking at Knuth's 4.5.4, I see that a pseudorandom number generator of f(x)=(x^{2} + c) Mod N is specifically deprecated when c = 2 (as it is in the LL sequence) because of recurrence relationships that exist. All the same I wonder if that could be worked around. Maybe by taking the data bits from the FFT before they are unscrambled into the correct order. Since the rho method depends on the GCD algorithm, it seems like an expensive operation to throw into a finely tuned routine. I wish my math ability was at least at the level of a math crank. At least I am muttering to myself like one at the moment. 
20031016, 22:17  #14  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Quote:
I include it here because it answers my implied question and finishes my speculation in that direction nicely. I should have read the forum more! 

20050902, 22:55  #15  
"Jason Goatcher"
Mar 2005
5·701 Posts 
Quote:
Maybe I'll get flamed for this, but has anyone ever been ACTUALLY KNOWN to to do the arithmetic on the actual numbers, using the hard drive? There is a small possibility that we're dealing with an,"Everybody knows the world is flat, so why bother?" type of thing. 

20050902, 23:19  #16  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Exercise: Compute the first few terms of the sequence x_0 = 4, x_{n+1} = x_n^2  2, i.e. 4, 14, 194, ... (a) Look at what happens to the number of digits in successive terms as you go along. (b) Estimate the number of digits for the x_29, x_59 and x_87 terms, and how much the hard disk space required would cost. Estimate how long the final division would take, assuming it can process one million digits in the dividend per second. (c) Try to estimate the number of digits in the x_25964949 term. Note: the x_29, x_59 and x_87 terms are what are needed to discover the primes M31, M61 and M89, respectively. Alex 

20050902, 23:41  #17  
Sep 2004
185_{10} Posts 
Quote:
I think you read 2^400, where you should have seen 2^(2^400), taking 2^400 bits on your "hard drive", not 400... Philippe. 

20050902, 23:42  #18  
Oct 2004
tropical Massachusetts
3·23 Posts 
Quote:
You're saying the number of bits in the number of bits of S(n) is a manageable number. Which has no bearing when it's S(n) itself that you're proposing we try to handle. The number of digits in the number of digits of one googolplex is 101. So of course one googolplex is a nice manageable number, right?? 

20050903, 01:59  #19  
Cranksta Rap Ayatollah
Jul 2003
641 Posts 
Quote:


20050903, 16:22  #20  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C_{16} Posts 
Quote:
The real problem, as already pointed out by Philippe, is that jasong makes the mistake of thinking that 2^(2^400) has only 400 bits. 2^(2^400) actually has 2^400 bits. Since 2^400 > 10^100, the number 2^(2^400) actually has over a googol bits.    Jasong, Storing the explicit value of a number the size of 2^(2^400) requires over (well over) ten million billion trillion trillion trillion trillion trillion trillion trillion bits. Last fiddled with by cheesehead on 20050903 at 16:33 

20050904, 00:26  #21  
Oct 2004
tropical Massachusetts
3×23 Posts 
Quote:
It's doubleplus ungood using log log N in a place where log N is what is required. Last fiddled with by trilliwig on 20050904 at 00:31 

20050904, 01:48  #22  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Last fiddled with by cheesehead on 20050904 at 01:49 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
faster than LL?  paulunderwood  Miscellaneous Math  13  20160802 00:05 
Is it faster to run 1 worker or many?  arbiter21  Information & Answers  17  20160205 05:04 
My CPU is getting faster and faster ;)  lidocorc  Software  2  20081108 09:26 
3PRP faster than LL for GIMPS?  bearnol  Math  35  20051012 14:33 
Faster than LL?  clowns789  Miscellaneous Math  3  20040527 23:39 