Jump to content
julkas

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.

Share this post


Link to post
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.

  • Like 2

Share this post


Link to post

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

Share this post


Link to post
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 by Bill Meyer

Share this post


Link to post
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

Share this post


Link to post
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.

Share this post


Link to post

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

Share this post


Link to post
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
  • Like 1

Share this post


Link to post
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

Share this post


Link to post
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. 

Share this post


Link to post
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

Share this post


Link to post
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)

  • Like 1
  • Haha 1

Share this post


Link to post

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

Share this post


Link to post
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, 

Share this post


Link to post
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
  • Like 1

Share this post


Link to post
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.

Share this post


Link to post

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.

 

Share this post


Link to post

Windows Vista 32bit, CPU - Intel E2200

 

$ time mult/prng_t.exe
3907851 values < 72057594037927935

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

 

Share this post


Link to post
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).

Share this post


Link to post
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

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×