I have made good progress over the past few months in understanding the math behind the Recursion With Carry generator. In particular I know how to design one and compute its period. There are two initial states that collapse instantly to a period of one. I can find the non-zero trivial state as well. First you need to calculate an integer:
((2^32)^4)*2111111111 + ((2^32)^3)*1492 + ((2^32)^2)*1776 + (2^32)*5115 - 1 =
718373885684172166973216179348278232025854377983
(2^32 is the base of the generator. ) This integer must be a prime. Marsaglia calls this integer m. If m is a prime, the period will be some number that can even divide (m-1)/2. That integer is:
359186942842086083486608089674139116012927188991
If this is also a prime, then m is called a safe prime. The period will either be the huge number above or 1. All zeros will repeat forever with a period of 1. You already know that. But set the Carry to 2111119493 and all 4 X's to 4294967295 and the generator will also have a period of 1. I believe that this is the only other case where the generator has a period of 1. These numbers come from:
2111119493 = (2111111111 + 1492 + 1776 + 5115) -1
4294967295 = (2^32) - 1 |