[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]