Randomize improvement
lazarus / 64-FPC development

----------------------------------------------------------------------
Eugene Loza · 2016-12-07 09:19

Recently I've been toying with xorshift random generation algorithm
and to make it thread-safe and more random I've made a randomization
procedure wihch together with gettickcount64 (as SysUtils does)
considers also "now" and local variable memory address.
https://github.com/castle-engine/castle-
engine/blob/master/src/base/castlerandom.pas#L96
Maybe SysUtils.randomize could be improved in a similar way?
(+) More random "random seed".
(+) Thread safety (as SysUtils.random is not intended to have multiple
instances this is actually not needed)
(+) Randomize now doesn't have to be called only once (a problem
sometimes encountered by people).
(-) This procedure is more complex and works significantly slower.

Also there is a urandom randomization algorithm
http://wiki.freepascal.org/Dev_random which is even better. Are there
any problems with using it as a default in *nix systems?

----------------------------------------------------------------------
Jonas Maebe · 2016-12-07 10:57

Small side remark: random is in the system unit, not in sysutils.

Random must behave the same on all platforms, because it is often used
to generate a reproducible sequence of numbers (by setting randseed to
a particular value), and those should be the same everywhere.

You can call randomize as much as you want with system.random, it just
decreases the amount of randomness you will get. There is no point in
"fixing" that, since the whole point is that simply calling random
over and over again will give you the maximum amount of randomness
possible.

Thread-safety is indeed out of scope for the default random number
generator, and if you need that, you should use a different one.

----------------------------------------------------------------------
Thaddy · 2017-04-03 09:45

By now I have a threadsafe and compatible random. I include it here as
a snippet, because I am working on a larger set of randoms.
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i unit
tsrandom;intefacetype     { A threadsafe implementation of Free
Pascal's random number generator.      The Free Pascal default Random
is not thread safe.      This algorithm is fully compatible will Free
Pascal's Random.      It is an implementation of a Mersenne Twister. 
   See:https://en.wikipedia.org/wiki/Mersenne_Twister      This class
only guarantees a repeatable series of random values      within the
same thread. Every thread has it's own Random and Randseed.     
Exported data, however, can be repeated provided the Randseed is
known.      Every Randseed needs to be initialized on a per thread
basis.}     { TThreadSafeRandom }     TThreadSafeRandom = class
sealed    strict private      class function GetSeed: Cardinal;
inline;static;      class procedure SetSeed(AValue: Cardinal);inline;
static;      class procedure Initialize(const
ASeed:Cardinal);inline;static;      class procedure
Twist;inline;static;      class function IM:Cardinal;inline;static;  
  class constructor create;    public      class procedure
Randomize;inline;static;      class function Random: extended;
overload;static;inline;      class function
Random(range:longint):longint;overload;static;inline;      class
function Random(range:int64):int64;overload;static;inline;      class
property RandSeed:Cardinal Read GetSeed write SetSeed;    end;    
TsRand = type TThreadSafeRandom; implementationconst  // Define
MT19937 constants (32-bit RNG)  N = 624;M = 397;R = 31;A = $9908B0DF;F
= 1812433253;  U = 11;S = 7;B = $9D2C5680;T = 15;C = $EFC60000;L =
18;  MASK_LOWER = QWORD(1) << R - 1;  MASK_UPPER = QWORD(1) << R;  //
conversion constants. Converts IM output from Cardinal to Float. 
CONVERT_UNSIGNED = Extended (1.0/int64(1 shl 32)); //  0..1 
CONVERT_SIGNED   = Extended (2.0/int64(1 shl 32)); // -1..1 Threadvar 
MtRandSeed:Cardinal;  MtOldRandSeed:Cardinal;  Index:Cardinal; 
mt:array[0..N-1] of dword; { TThreadSafeRandom } class function
TThreadSafeRandom.GetSeed: Cardinal;begin  Result :=
mtRandSeed;end; class procedure TThreadSafeRandom.SetSeed(AValue:
Cardinal);begin  mtRandSeed := AValue; 
Initialize(mtRandseed);end; class procedure
TThreadSafeRandom.Initialize(const ASeed: Cardinal);var 
i:dword;begin  mt[0] := Aseed; for  i := 1 to pred(N) do   mt[i] := F
* (mt[i - 1] xor (mt[i - 1] >> 30)) + i; index := N;end; class
procedure TThreadSafeRandom.Twist;inline;static;var  i:integer;begin 
for i:=0 to N-M-1 do    mt[i]:=mt[i+M] xor {twist} (((mt[i] and
MASK_UPPER) or    (mt[i+1] and MASK_LOWER)) shr 1)xor(dword(-(mt[i+1]
and 1)) and A);  for i:=N-M to N-2 do   
mt[i]:=mt[i+(M-N)]xor{twist}(((mt[i] and MASK_UPPER) or    (mt[i+1]
and MASK_LOWER)) shr 1)xor(dword(-(mt[i+1] and 1)) and A);   
mt[N-1]:=mt[M-1] xor {twist} (((mt[n-1] and MASK_UPPER) or (mt[0] and 
  MASK_LOWER)) shr 1)xor(dword(-(mt[0] and 1)) and A); 
index:=0;end; class constructor TThreadSafeRandom.create;begin 
initialize(0);  mtOldRandSeed := 0;end; class procedure
TThreadSafeRandom.Randomize;begin  // Hm. Not ideal... 
system.Randomize;  // assumes the Randseed is atomic for read 
mtrandseed := RandSeed;end; class function TThreadSafeRandom.Random:
extended;overload;inline;static;begin  Result := IM *
CONVERT_UNSIGNEDend; class function TThreadSafeRandom.Random(range:
longint): longint;begin  if Range < 0 then inc(Range);  Result := IM *
Range shr 32;end; class function TThreadSafeRandom.Random(range:
int64): int64;begin  Result:=IM;  Result:=Result or ((qword(IM) shl
32) and high(int64));  if Range<>0 then    Result := Result mod range 
else    Result := 0;end; class function TThreadSafeRandom.IM:
Cardinal;inline;static;var  i:integer;begin  i := index;  if  (index
>= N) or (mtRandSeed<>mtOldRandSeed) then  begin    Twist;   
mtRandSeed:=not(mtRandSeed);    mtOldRandSeed:=mtRandSeed;    i :=
index;  end;  Result := mt[i];  index := i + 1;  Result := Result xor
(mt[i] >> U);  Result := Result xor (Result << S) and B;  Result :=
Result xor (Result << T) and C;  Result := Result xor (Result >>
L);end;end.
Note I am not sure about ThreadsafeRandom.Randomize here: assumes too
much.
Anyway: I needed this for repeatability and as such it is threadsafe.
It passes all comparisons with FPC's default Random.
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i program
randomtests;{$assertions on}uses  // prngenerators,marsaglia; 
tsrandom; var  i:integer;begin  Randseed := 12345;  TsRand.Randseed :=
Randseed;  writeln('FPC     <Random>   tsRAND'); 
writeln('-------------------------');  for i := 1 to 10 do  begin   
write(Random(100):12,'|',TsRand.Random(100):12);    if i mod 1 = 0
then writeln;  end;  Assert(randseed-tsRand.Randseed = 0,'Fatal error:
Randseeds are out of sync');  for i := 1 to 10 do  begin   
write(Random:4:10,'|',TsRand.Random:4:10);    if i mod 1 = 0 then
writeln;  end;  Assert(randseed-tsRand.Randseed = 0,'Fatal error:
Randseeds are out of sync'); 
writeln('-------------------------'); end.

----------------------------------------------------------------------
jwdietrich · 2017-04-04 19:53

Thanks!

----------------------------------------------------------------------
Thaddy · 2019-07-24 04:28

I noticed there is a more serious bug than the cast having to do with
the int64 implementation.
See https://bugs.freepascal.org/view.php?id=35878#bugnotes
I am currently updating the code to contain the real MT19937-64, so it
is complaint with the standard.
Another "bug" was that the unit should be compiled with range checks
and overflow checks disabled.
That is in this case correct and complaint with the original MT19937
implementation.
I will post a new version once I translated  MT19937-64 to Pascal.

----------------------------------------------------------------------
abouchez · 2020-11-26 20:08

I know this forum post is a bit old, but it is a reference about
thread-safe random for the RTL.

We published a small and efficient thread-safe random, with proper
seed, in mORMot2.
See the Random32() functions and the TLecuyer class. There are also
some nice and proven ideas about the seed in GetEntropy().
Check https://github.com/synopse/mORMot2/blob/bbda37425bf8eb0ffa859d81
3e712ad2de6edbd4/src/core/mormot.core.base.pas#L8264

----------------------------------------------------------------------
marcov · 2020-11-26 20:27

Quote from: Eugene Loza on December 07, 2016, 10:19:17 am(-) This
procedure is more complex and works significantly slower.

It always is useful to make a separate prng unit. But this kills it
for the central prng.

----------------------------------------------------------------------
Thaddy · 2020-11-26 21:04

Quote from: marcov on November 26, 2020, 09:27:47 pmIt always is
useful to make a separate prng unit. But this kills it for the central
prng.
Marco, that three year old code IS a central prng! Jonas would not fix
it so I wrote it.
Plz check the code, I am open for improvements, but the current commit
from Ondrej is like Trump.... Bloat.

Also the code is very simple. The only thing that maybe needs platform
is randomize for platforms lesser than 32 bit.
(and although different from Jonas' implementation, the results are
always the same)
Maybe Ondrej can explain why he touched so many units?    when it
should be one?

----------------------------------------------------------------------
PascalDragon · 2020-11-27 14:47

Quote from: Thaddy on November 26, 2020, 10:04:03 pmQuote from: marcov
on November 26, 2020, 09:27:47 pmIt always is useful to make a
separate prng unit. But this kills it for the central prng.
Marco, that three year old code IS a central prng! Jonas would not fix
it so I wrote it.
Plz check the code, I am open for improvements, but the current commit
from Ondrej is like Trump.... Bloat.
The commit was reverted, because Ondrej did not discuss this with the
remainder of the devs and we were against it.

Quote from: Thaddy on November 26, 2020, 10:04:03 pmAlso the code is
very simple. The only thing that maybe needs platform is randomize for
platforms lesser than 32 bit.
(and although different from Jonas' implementation, the results are
always the same)
Maybe Ondrej can explain why he touched so many units?    when it
should be one? 

If you looked at the code you would know why all System units had to
be touched, because the platform specific Randomize is implemented in
each platform specific System unit. In his commit he introduced a new
general Randomize and changed the platform specific one to
Randomize(var RandSeed: LongInt);.

----------------------------------------------------------------------
Thaddy · 2020-11-27 16:31

Quote from: PascalDragon on November 27, 2020, 03:47:49 pmIf you
looked at the code you would know why all System units had to be
touched, because the platform specific Randomize is implemented in
each platform specific System unit. In his commit he introduced a new
general Randomize and changed the platform specific one to
Randomize(var RandSeed: LongInt);.
That's why my alarm bells went off. Glad it is reversed. But also
pleased Ondrej put some effort in. That is much appreciated.
His approach to the randomize gives me some inspiration to solve my
concerns from 3 years ago.