View Single Post
Old 2019-04-14, 17:50   #6
kriesel's Avatar
Mar 2017
US midwest

29×173 Posts
Default Why don't we compute the Lucas series once, and only modulo later?

This occasionally comes up as either a joke or an innocent question.

The short answer is, nowhere to put the immense data, and most of the iterations to generate the table would take too long, and accessing the data and applying the modulo to such immense numbers would each take too long.

For small p, one could compute the LL sequence terms without applying the modulo each time. For example, for p=7,
the LL sequence, si+1=Si2-2
S0 = 4 (2+ bits)
S1 = 14 (~4 bits)
S2 = 194 (~8 bits)
S3 = 37634 (~16 bits)
S4 = 1,416,317,954 (~31 bits)
S5 = 2,005,956,546,822,746,114 (~61 bits)
/ (27-1) = 15,794,933,439,549,182 with remainder zero. 27-1 is a Mersenne prime.

In fact, this happens at the beginning of every LL test as coded in prime95 and other software, until the value reaches p bits or more in the computation for any M(p). The number of bits in the series almost doubles at each iteration, independently of the value p, until the modulo begins to have effect. The number of iterations to reach 84,000,000 bits is about 25. The size doubles at each iteration, rapidly reaching sizes the human mind is not well suited for grasping. We very quickly run out of places to put the data, even if going to extremes.

If we somehow used the entire observable universe as a data storage medium, including the estimated amount of dark matter, at 10 bits of data storage per proton mass, we could store the result of only about 266. full-length modulo-free iterations. That falls quite a bit short of 84 million, the current GIMPS first test wavefront. (It's actually a bit worse, since the bit efficiency in fft form and need for storage of other data increases storage needs faster than computed above; ~263 iterations.) Some of those bits would be billions of light years away from others.

The modulo applied frequently is one of the things that make it possible to accomplish any primality tests at the current wavefront of first test or double check. It's more efficient to apply it every iteration when the sequence value is large compared to the computing device's word size.

Top of reference tree:

Last fiddled with by kriesel on 2019-11-19 at 15:52
kriesel is offline