Random unsigned 64 bit integers

[julkas 12]

I need platform independent and FPC compatible random unsigned 64 bit generator.

Here is my solution:
 

program rnd;
{$IF Defined(FPC)}{$MODE Delphi}{$ENDIF}
{$INLINE ON}

function RandU64(): UInt64; inline;
begin
  Result := UInt64(Random($10000));
  Result := (Result shl 16) or UInt64(Random($10000));
  Result := (Result shl 16) or UInt64(Random($10000));
  Result := (Result shl 16) or UInt64(Random($10000));  
end;

var
  i: integer;
  
begin
  Randomize();
  for i := 1 to 1000 do
    WriteLn(RandU64());
end.

Can it be done better?

Thanks.

[David Heffernan 2345]

14 minutes ago, julkas said:

Can it be done better?

Random returns 32 bits of randomness, why only use 16 of them? In other words, can't you do this with two calls to Random rather than four.

 

Furthermore, Random is a pretty low grade PRNG. Depending on what you intend to use this for, you may want to use a better PRNG.

[Stefan Glienke 2002]

Take a look into @Primož Gabrijelčič GpRandomGen.pas

[julkas 12]

I don't know much about PRNG.

I just found xoroshiro128starstar - http://prng.di.unimi.it/.

What you think about?

 

program rand;
{$IF Defined(FPC)}{$MODE Delphi}{$ENDIF}
{$INLINE ON}

var
  seed: array[0..1] of uint64;  

function rotl(x: uint64; k: integer): uint64; inline;
begin
	Result := (x shl k) or (x shr (64 - k));
end;

function xoroshiro128starstar(): uint64;
var
  s0, s1: uint64;
  
begin
  s0 := seed[0];
  s1 := seed[1];
  Result := rotl(s0 * 5, 7) * 9;

  s1 := s1 xor s0;
  seed[0] := rotl(s0, 24) xor s1 xor (s1 shl 16); // a, b
  seed[1] := rotl(s1, 37); // c
end;

var
  i: integer;
  
begin
  seed[0] := 3;
  seed[1] := 1000000007;
  
  for i := 1 to 1000 do
    WriteLn(xoroshiro128starstar());
end.

Online link - https://ideone.com/cB6zSa

 

Thanks for replies.

Edited October 22, 2020 by julkas

[Bill Meyer 337]

3 hours ago, julkas said:

I don't know much about PRNG.

I just found xoroshiro128starstar - http://prng.di.unimi.it/.

What you think about?

See: https://en.wikipedia.org/wiki/Xoroshiro128%2B
As the commentary indicates, all PRNGs have some deficiencies, and those may or may not be of concern in a given application. This one is reputedly of high statistical quality, and very fast. 
I did not find an expression of the algorithm, so there remains the question of whether the implementation is accurate.

Edited October 22, 2020 by Bill Meyer

[Stefan Glienke 2002]

50 minutes ago, Bill Meyer said:

I did not find an expression of the algorithm, so there remains the question of whether the implementation is accurate.

The description is in the paper and the reference implementation in c is in the very links on that page.

 

Attention though: there is xoroshiro and xoshiro in different variations.

Edited October 22, 2020 by Stefan Glienke

[Bill Meyer 337]

40 minutes ago, Stefan Glienke said:

The description is in the paper and the reference implementation in c is in the very links on that page.

 

Attention though: there is xoroshiro and xoshiro in different variations.

Indeed, I had looked at the page with his implementation, but failed to open the page with the article. 😞 

Multitasking is best done by machine.

[Arnaud Bouchez 407]

Your xoroshiro128starstar implementation is not thread-safe, by the way.

 

Why not just use (Int64(Random(maxInt)) shl 32) or Random(maxInt) which is fine and cross-compiler?

 

Or on modern CPU:

function RdRand32: cardinal; {$ifdef CPU64}
{$ifdef FPC}nostackframe; assembler; asm{$else} asm .noframe {$endif FPC} {$else}
{$ifdef FPC}nostackframe; assembler;{$endif} asm {$endif}
  // rdrand eax: same opcodes for x86 and x64
  db $0f, $c7, $f0
  // returns in eax, ignore carry flag (eax=0 won't hurt)
end;

function RdRand64: QWord;
begin
  result := (QWord(RdRand32) shl 32) or RdRand32;
end;

Note that RDRAND opcode is not available on old processor, not very fast, and sometimes returns 0 of -1 on AMD... but it is a good seed for entropy.

 

See also the Random32 function in https://github.com/synopse/mORMot/blob/master/SynCommons.pas which is based on Lecuyer, and use good entropy seed.

and the TAESPRNG class in https://github.com/synopse/mORMot/blob/master/SynCrypto.pas which is a true cryptographic random generator, using AES-NI very fast asm.
Both are thread-safe and use the NIST SP 800-90A compliant RDRAND Intel x86/x64 opcode as entropy source, if available.

Edited October 22, 2020 by Arnaud Bouchez

[Arnaud Bouchez 407]

6 hours ago, David Heffernan said:

Furthermore, Random is a pretty low grade PRNG. Depending on what you intend to use this for, you may want to use a better PRNG.

Small precision:

On Delphi, Random() is pretty basic and low grade.

On FPC (which is quoted by the OP), its implementation is much better, and based on proved algorithms.

Edited October 22, 2020 by Arnaud Bouchez

[julkas 12]

17 hours ago, Arnaud Bouchez said:

Why not just use (Int64(Random(maxInt)) shl 32) or Random(maxInt) which is fine and cross-compiler?

Random(MaxInt) generates values only from the interval [0, 2147483646]. So you will never got random UInt64 value x, where Lo(x) or Hi(x) are from the interval [2147483647, 4294967295]

Edited October 23, 2020 by julkas

[Fr0sT.Brutal 900]

(Random(X)/X)*High(UInt64)

[David Heffernan 2345]

35 minutes ago, Fr0sT.Brutal said:

(Random(X)/X)*High(UInt64)

Absolutely not. Some UInt64 values can never be returned and the performance will be poor. 

[Fr0sT.Brutal 900]

1 hour ago, David Heffernan said:

Some UInt64 values can never be returned

Which ones?

1 hour ago, David Heffernan said:

performance will be poor.

Performance was not mentioned

[Anders Melander 1784]

2 hours ago, Fr0sT.Brutal said:

Which ones?

Most of them. You're scaling a 31-bit integer value in the approximate range 0..X-1 to the range 0..2^64-1

 

2 hours ago, Fr0sT.Brutal said:

Performance was not mentioned

A lot of things wasn't mentioned. For example here's my solution which satisfies all the criteria that was mentioned:

• The result is 64-bit unsigned.
• It's cross platform.
• It compiles with FPC.
• It's random (for a large enough sample size).

and as a bonus

• It's super fast.

function SuperRandom: UInt64;
begin
  Result := 1;
end;

 

(sorry - it's Friday)

[Mahdi Safsafi 225]

On 10/22/2020 at 3:22 PM, Arnaud Bouchez said:

 

// returns in eax, ignore carry flag (eax=0 won't hurt)

 

Not so ! 

Short answer : 0 is not granted to be a random value on all architectures.  

Long answer : https://software.intel.com/content/www/us/en/develop/blogs/rdrand-do-i-need-to-check-the-carry-flag-or-can-i-just-check-for-zero.html

[Marat1961 17]

Maybe you are satisfied with the implementation of a pseudo-random sequence generator for a 64-bit integer using the Linear congruential generator method.

I used the coefficients for the generator recommended by Donald Knuth in his book.

 

Hastily sketched. Perhaps for everything to work correctly, we need to implement multiplication of 64-bit numbers.

 

class var 
  seed: Int64;

  
class function TRandom64.Def: Int64;
begin
  Result := seed * 6364136223846793005 + 1442695040888963407;
  seed := Result;
end;

 

Project https://github.com/marat1961/Tower-of-Babel.

Edited October 23, 2020 by Marat1961

[Guest]

My two cents here,

 

I would not use RDRAND in any setup and would not recommend it, it is way slow and can't be trusted as CSPRNG, i mean as cryptographically secure random number generator, due its closed and hidden behaviour, its speed range from few hundreds cycles to few thousands   https://en.wikipedia.org/wiki/RDRAND

 

@Arnaud Bouchez That TAESPRNG is neat and right but missing one small thing to be considered as "bad ass CSPRNG done right", don't use the full block in getting a random number, there is many papers explain the impact of such usage, but these papers are very hard to read like this one ( 5.1 Analysis of deterministic leakages in  https://eprint.iacr.org/2007/356.pdf ) that very hard to read and interpret even for me, but i can see easier to understand explanation here https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator 

Quote

Definitions

A forward-secure PRNG with block length ...... (can't paste the text here)

And to make it in plain English use half of the block to get random number and use the other half to generate the next state, this will preserve deterministic state, guarantee forward secrecy and prevent deterministic leakage. 

So in other words also, 

function TAESPRNG.Random32: cardinal;
var block: THash128Rec;
begin
  FillRandom(block.b);
  result := block.c0 xor block.c1;// {xor block.c2 xor block.c3};
  // or even better, just use the first part as no gain there from using two parts
  // result := block.c0;
end;

function TAESPRNG.Random64: QWord;
var block: THash128Rec;
begin
  FillRandom(block.b);
  result := block.L;//{ xor block.H};
end;

Would be better, as there is no gain from XORing these parts, 

[Guest]

And for fast PRNG algorithms, have a look at this

https://lemire.me/blog/2019/03/19/the-fastest-conventional-random-number-generator-that-can-pass-big-crush/

and look at Daniel Lemire git hub, it does have neat stuff

https://github.com/lemire/testingRNG/tree/master/source

[Remy Lebeau 1397]

12 hours ago, julkas said:

Random(MaxInt) generates values only from the interval [0, 2147483646]. So you will never got random UInt64 value x, where Lo(x) or Hi(x) are from the interval [2147483647, 4294967295]

That should be easy enough to account for, using Random(16) to generate 4 random bits that can be shifted into the UInt64's bits 0, 31, 32, and 63 which the shifted Random(MaxInt) values will never fill in, eg:

 

var
  Num, Bits: UInt64;

Num := (UInt64(Random(maxInt)) shl 32) or UInt64(Random(maxInt));
Bits := UInt64(Random(16));
Num := Num or (Bits and 1);
Num := Num or ((Bits and 2) shl 30);
Num := Num or ((Bits and 4) shl 30);
Num := Num or ((Bits and 8) shl 60);

 

Edited October 23, 2020 by Remy Lebeau

[julkas 12]

14 hours ago, Kas Ob. said:

And for fast PRNG algorithms, have a look at this

https://lemire.me/blog/2019/03/19/the-fastest-conventional-random-number-generator-that-can-pass-big-crush/

and look at Daniel Lemire git hub, it does have neat stuff

https://github.com/lemire/testingRNG/tree/master/source

Good. May be I will start with Lehmer’s generator or http://prng.di.unimi.it/splitmix64.c

[Guest]

23 minutes ago, julkas said:

Good. May be I will start with Lehmer’s generator or http://prng.di.unimi.it/splitmix64.c

That is good, and i want to point that PCG had proved its quality for bit uniformity, so it is also might be good alternative, as which will be fast ?! with Delphi compiler is hard to tell.

Anyway, i wanted to point that if you are interested in more in depth knowledge, and here i don't mean to sit and waste huge time studying, but at least get an idea when someone say an PRNG had passed some test, what they talking about, so visit 

https://en.wikipedia.org/wiki/Permuted_congruential_generator

And read it and focus on the last part the "comparison", then if you got time click on the links in "References", again not to understand everything, but in future at least you know what does "testing right" mean, and what does the quality of PRNG affect or how measured, just the bold lines.

[julkas 12]

Here is my SplitMix64.

I think it's good starting point.

Online - https://ideone.com/MCiSXd

program rand;
{$IF Defined(FPC)}{$MODE Delphi}{$ENDIF}
{$INLINE ON}
{$Q-}{$R-}

uses SysUtils;

type
  TSplitMix64 = record
    state: UInt64;
    procedure Init(seed: UInt64); inline;
    function Next(): UInt64; inline;
  end;

procedure TSplitMix64.Init(seed: UInt64);
begin
  state := seed;
end;

function TSplitMix64.Next(): UInt64;
begin
  Inc(state, $9e3779b97f4a7c15);
  Result := state;
  Result := (Result xor (Result shr 30)) * $bf58476d1ce4e5b9;
  Result := (Result xor (Result shr 27)) * $94d049bb133111eb;
  Result := Result xor (Result shr 31);
end;

const
  check: UInt64 = $FFFFFFFFFFFFFFFF shr 8;

var
  r: TSplitMix64;
  x: UInt64;
  i, c: integer;

begin
  r.Init(UInt64(GetTickCount()) * UInt64(GetTickCount()));

  for i := 0 to 1000000000 do
  begin
    x := r.Next();
    if x < check then Inc(c);
  end;    
  WriteLn(c, ' values < ', check);
  for i := 0 to 1000 do
    WriteLn(r.Next());
end.

 

[julkas 12]

Windows Vista 32bit, CPU - Intel E2200

 

$ time mult/prng_t.exe
3907851 values < 72057594037927935

real    0m14.730s
user    0m0.000s
sys     0m0.062s

 

[Marat1961 17]

1 hour ago, julkas said:

Here is my SplitMix64.

I think it's good starting point.

Why did you decide this code is a good pseudo-random sequence generator?

What is his period?
What are its statistical parameters?
What tests were performed to assess quality?

 

By the way, I'm wondering for what purpose exactly a 64-bit pseudo-random sequence generator was required?

It would be helpful to know the domain of application (DDD).

[julkas 12]

31 minutes ago, Marat1961 said:

Why did you decide this code is a good pseudo-random sequence generator?

What is his period?
What are its statistical parameters?
What tests were performed to assess quality?

 

By the way, I'm wondering for what purpose exactly a 64-bit pseudo-random sequence generator was required?

It would be helpful to know the domain of application (DDD).

For testing see - https://github.com/lemire/testingRNG

It's open source code, you can improve it or open issue.

Pascal version - https://github.com/JulStrat/primesieve-pas/blob/mult/mult/prng.pas