# Random unsigned 64 bit integers

## Recommended Posts

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.

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.

• 2

I don't know much about PRNG.

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

```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.```

Thanks for replies.

Edited by julkas

3 hours ago, julkas said:

I don't know much about PRNG.

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

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 by Bill Meyer

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 by Stefan Glienke

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.

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 by Arnaud Bouchez

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 by Arnaud Bouchez
• 1

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 by julkas

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

• 1

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.

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

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)

• 1
• 1

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.

• 1

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;
```

Edited by Marat1961

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,

And for fast PRNG algorithms, have a look at this

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

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 by Remy Lebeau
• 1

14 hours ago, Kas Ob. said:

And for fast PRNG algorithms, have a look at this

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

23 minutes ago, julkas said:

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

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.

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.```

Windows Vista 32bit, CPU - Intel E2200

```\$ time mult/prng_t.exe
3907851 values < 72057594037927935

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

```

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).

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.