Good 64 bit prime number for Lehmer random number generator algorithm ?

Post by Skybuck Flying
Hello,
What is a good 64 bit prime number for a 64 bit implementation of the Lehmer
random number generator algorithm ?
Bye,
Skybuck.

I think Knuth recommends
x_{n+1} = 636413622384679305 * x_n + 1 mod 2^64
in this case

Rudy Velthuis

2007-07-09 20:27:48 UTC

Post by hagman

Post by Skybuck Flying
Hello,
What is a good 64 bit prime number for a 64 bit implementation of
the Lehmer random number generator algorithm ?
Bye,
Skybuck.

I think Knuth recommends
x_{n+1} = 636413622384679305 * x_n + 1 mod 2^64
in this case

I assume you mean

x_{n+1} = (636413622384679305 * x_n + 1) mod 2^64

since 1 mod 2^64 is 0.

--
Rudy Velthuis http://rvelthuis.de

"My advice to you is get married: if you find a good wife you'll
be happy; if not, you'll become a philosopher."
-- Socrates (470-399 B.C.)

Skybuck Flying

2007-07-09 21:48:20 UTC

Post by hagman

Post by Skybuck Flying
Hello,
What is a good 64 bit prime number for a 64 bit implementation of
the Lehmer random number generator algorithm ?
Bye,
Skybuck.

I think Knuth recommends
x_{n+1} = 636413622384679305 * x_n + 1 mod 2^64
in this case

I assume you mean
x_{n+1} = (636413622384679305 * x_n + 1) mod 2^64
since 1 mod 2^64 is 0.

Then Knuth is an idiot.

636413622384679305 is not prime.

636413622384679305 / 3 = 212137874128226435

Even my simple basic prime finder can tell you that ;)

Unless you a troll misquoting Knuth ;)

Skybuck's 64 bit prime finder with start and stop range:

// *** Begin of Code ***

procedure PrimeFinder3( Start, Stop : uint64 );
var
P : uint64;
Test : uint64;
Prime : boolean;
begin
writeln('Primes found:');

P := Start;
while P <= Stop do
begin
Prime := true;

Test := 2;
while Test < P do
begin
if P mod Test = 0 then
begin
Prime := false;
break;
end;
Test := Test + 1;
end;

if Prime then
begin
writeln( P );
end;

P := P + 1;
end;
end;

// *** End of Code ***

Bye,
Skybuck.

Rudy Velthuis

2007-07-09 22:02:08 UTC

Post by Rudy Velthuis
I assume you mean
x_{n+1} = (636413622384679305 * x_n + 1) mod 2^64
since 1 mod 2^64 is 0.

Then Knuth is an idiot.

LOL!

--
Rudy Velthuis http://rvelthuis.de

"When I die I'm going to leave my body to science fiction."
-- Steven Wright.

Skybuck Flying

2007-07-09 22:11:22 UTC

Post by Rudy Velthuis
I assume you mean
x_{n+1} = (636413622384679305 * x_n + 1) mod 2^64
since 1 mod 2^64 is 0.

Then Knuth is an idiot.

LOL!

You're an idiot too.

Hagman is an idiot too.

LOL.

Bye,
Skybuck.

Rudy Velthuis

2007-07-09 22:19:29 UTC

Post by Skybuck Flying
You're an idiot too.

Yeah, I guess so. Otherwise I would not even talk to you.

--
Rudy Velthuis http://rvelthuis.de

"A printer consists of three main parts: the case, the jammed
paper tray and the blinking red light" -- unknown

Skybuck Flying

2007-07-09 22:26:44 UTC

Post by Skybuck Flying
You're an idiot too.

Yeah, I guess so. Otherwise I would not even talk to you.

Exactly idiots like you just talk and don't learn.

Bye,
Skybuck.

Rudy Velthuis

2007-07-09 22:29:42 UTC

Post by Skybuck Flying
You're an idiot too.

Yeah, I guess so. Otherwise I would not even talk to you.

Exactly idiots like you just talk and don't learn.

Right. I guess I'll go playing with my Playskool again. <g>

--
Rudy Velthuis http://rvelthuis.de

"When did I realize I was God? Well, I was praying and I suddenly
realized I was talking to myself."
-- Peter O'Toole.

hagman

2007-07-10 07:25:07 UTC

Post by hagman

Post by Skybuck Flying
Hello,
What is a good 64 bit prime number for a 64 bit implementation of
the Lehmer random number generator algorithm ?
Bye,
Skybuck.

I think Knuth recommends
x_{n+1} = 636413622384679305 * x_n + 1 mod 2^64
in this case

I assume you mean
x_{n+1} = (636413622384679305 * x_n + 1) mod 2^64
since 1 mod 2^64 is 0.

Then Knuth is an idiot.
636413622384679305 is not prime.
636413622384679305 / 3 = 212137874128226435
Even my simple basic prime finder can tell you that ;)

It is even more easily seen to be a multiple of 5.
However, for a random number generator of type
x[n+1] = (a*x[n]+b) mod M
to be good, it is not necessary that a be prime.
I don't know why you want a prime.
For example maximal period length for M=2^64
is already guaranteed if a = 1 mod 4 and b is odd.

Post by Skybuck Flying
Unless you a troll misquoting Knuth ;)

I took it from a table where he applies the spectral
test to about 30 PRNGs.
Actually, he lists only one case for M=2^64, but
gives positive remarks about it in the text.

hagman

Skybuck Flying

2007-07-10 18:17:05 UTC

It's important that it's a prime.

Otherwise period probably shorter.

Bye,
Skybuck.

hagman

2007-07-16 06:43:48 UTC

Post by Skybuck Flying
It's important that it's a prime.
Otherwise period probably shorter.
Bye,
Skybuck.

THEOREM: With M=2^64
x[n+1] = (a*x[n]+b) mod M
has period length M if a = 1 mod 4 and b is odd.
PROOF: Exercise.

By the way, maximal period is not all that makes a good PRNG.
x[n+1] = (5*x[n]+1) mod M
and
x[n+1] = (3*x[n]+1) mod M
are awfully bad.
And the latter has lower period even though 3 is prime,
as x[n] mod 4 goes like 0,1,0,1,... or 2,3,2,3,...

hagman

Skybuck Flying

2007-07-09 23:17:56 UTC