**[**Back to NUMBERS SWAG index**]** **[**Back to Main SWAG index**]** **[**Original**]**

*(*
>>This is not so. The period of Borland's generator is 2^32, i.e.,
>>4.3 billion. The linear recurrence is randseed :=
>>randseed*134775813+1 {mod 2^32}; (the mod is implemented by
>>letting the calculation overflow). A recurrence of the form ax+c
>>mod 2^e has maximum period when c is odd and (a mod 4) is 1.
>>Borland's formula satisfies those conditions, so it will output a
>>permutation of the range 0 to 2^32-1 before the sequence repeats.
>you have the conditions wrong. the factor 2^e has to be prime and a
>has to be a primitive element modulo the factor before you get
>maximum period. 2^e is most definitely not prime. the generator
>happens to have much less than maximum period. the other
>relationship that a and m must have is that a^2 < m. this is also
>violated in the Borland formula.
Here's an easy counter-example: x := (x*5+1) mod 2^3 yields the maximum
period repeating sequence 0,1,6,7,4,5,2,3. The modulus m = 2^3 = 8 is
not prime and 5^2 = 25 is larger than 8.
I quote Knuth's 'The Art of Computer Programming', vol.2:
(exercise 2 of section 3.2.1.2, p.20)
Are the following two conditions sufficient to guarantee the
maximum length period, when m = 2^e is a power of 2?
"(i) c is odd; (ii) a mod 4 = 1."
(answer, p.458)
Yes, these conditions imply the conditions in Theorem A, since
the only prime divisor of 2^e is 2, and any odd number is rela-
tively prime to 2^e. (In fact, the conditions of the exercise
are necessary and sufficient, if e <> 2.)
(Theorem A referred to above, p.15)
The linear congruential sequence has a period of length m if and
only if
i) c is relatively prime to m;
ii) b = a-1 is a multiple of p, for every prime p dividing m;
iii) b is a multiple of 4, if m is a multiple of 4.
If you don't believe Knuth, try this program. If you're right that the
period of Borland's generator is no more than 10^5, it won't run long
and it won't write a single asterisk (expect lots):
*)
***program **borpriod; *{calculates the period of Borland's random}
{The period should be 2^32, so this will take hours}
***var **x,y,count1,count2: longint; s: **string**;
**begin
**randomize;
x := randseed; y := randseed;
**for **count2 := 0 **to **maxlongint **do begin
for **count1 := 0 **to **999999 **do begin
**x := x*134775813+1; *{TP7's and TP6's generator for random}
*y := y*134775813+1; *{implicit modulus is 2^32}
*y := y*134775813+1; *{see Knuth vol 2, p.453 for explanation}
***if **x = y **then begin
**inc(count1); *{adjust because first count was 0}
***if **count1 = 1000000 **then begin **count1 := 0; inc(count2) **end**;
**if **count2 > 0 **then begin
**str(count1,s);
writeln(#13#10'Period: ',count2,
copy('000000',1,6-length(s)),count1);
**end
else **writeln(#13#10'Period: ',count1);
halt;
**end**;
**end**;
write('*'); *{one per million}
***end**;
**end**.

**[**Back to NUMBERS SWAG index**]** **[**Back to Main SWAG index**]** **[**Original**]**