* * *

Author Topic: Randomize improvement  (Read 1072 times)

Eugene Loza

  • Sr. Member
  • ****
  • Posts: 376
    • Decoherence Studio :)
Randomize improvement
« on: December 07, 2016, 10:19:17 am »
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?
My Free and Open Source games in Lazarus/FreePascal/CastleGameEngine:
https://decoherence.itch.io/
(and some ancient games in Turbo Pascal too)

Jonas Maebe

  • Hero Member
  • *****
  • Posts: 556
Re: Randomize improvement
« Reply #1 on: December 07, 2016, 11:57:02 am »
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

  • Hero Member
  • *****
  • Posts: 3640
Re: Randomize improvement
« Reply #2 on: April 03, 2017, 11:45:49 am »
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]
  1. unit tsrandom;
  2. inteface
  3. type
  4.  
  5.     { A threadsafe implementation of Free Pascal's random number generator.
  6.       The Free Pascal default Random is not thread safe.
  7.       This algorithm is fully compatible will Free Pascal's Random.
  8.       It is an implementation of a Mersenne Twister.
  9.       See:https://en.wikipedia.org/wiki/Mersenne_Twister
  10.       This class only guarantees a repeatable series of random values
  11.       within the same thread. Every thread has it's own Random and Randseed.
  12.       Exported data, however, can be repeated provided the Randseed is known.
  13.       Every Randseed needs to be initialized on a per thread basis.}
  14.  
  15.     { TThreadSafeRandom }
  16.  
  17.     TThreadSafeRandom = class sealed
  18.     strict private
  19.       class function GetSeed: Cardinal; inline;static;
  20.       class procedure SetSeed(AValue: Cardinal);inline; static;
  21.       class procedure Initialize(const ASeed:Cardinal);inline;static;
  22.       class procedure Twist;inline;static;
  23.       class function IM:Cardinal;inline;static;
  24.       class constructor create;
  25.     public
  26.       class procedure Randomize;inline;static;
  27.       class function Random: extended; overload;static;inline;
  28.       class function Random(range:longint):longint;overload;static;inline;
  29.       class function Random(range:int64):int64;overload;static;inline;
  30.       class property RandSeed:Cardinal Read GetSeed write SetSeed;
  31.     end;
  32.  
  33.     TsRand = type TThreadSafeRandom;
  34.  
  35. implementation
  36. const
  37.   // Define MT19937 constants (32-bit RNG)
  38.   N = 624;M = 397;R = 31;A = $9908B0DF;F = 1812433253;
  39.   U = 11;S = 7;B = $9D2C5680;T = 15;C = $EFC60000;L = 18;
  40.   MASK_LOWER = QWORD(1) << R - 1;
  41.   MASK_UPPER = QWORD(1) << R;
  42.   // conversion constants. Converts IM output from Cardinal to Float.
  43.   CONVERT_UNSIGNED = Extended (1.0/int64(1 shl 32)); //  0..1
  44.   CONVERT_SIGNED   = Extended (2.0/int64(1 shl 32)); // -1..1
  45.  
  46. Threadvar
  47.   MtRandSeed:Cardinal;
  48.   MtOldRandSeed:Cardinal;
  49.   Index:Cardinal;
  50.   mt:array[0..N-1] of dword;
  51.  
  52. { TThreadSafeRandom }
  53.  
  54. class function TThreadSafeRandom.GetSeed: Cardinal;
  55. begin
  56.   Result := mtRandSeed;
  57. end;
  58.  
  59. class procedure TThreadSafeRandom.SetSeed(AValue: Cardinal);
  60. begin
  61.   mtRandSeed := AValue;
  62.   Initialize(mtRandseed);
  63. end;
  64.  
  65. class procedure TThreadSafeRandom.Initialize(const ASeed: Cardinal);
  66. var
  67.   i:dword;
  68. begin
  69.   mt[0] := Aseed;
  70.  for  i := 1 to pred(N) do
  71.    mt[i] := F * (mt[i - 1] xor (mt[i - 1] >> 30)) + i;
  72.  index := N;
  73. end;
  74.  
  75. class procedure TThreadSafeRandom.Twist;inline;static;
  76. var
  77.   i:integer;
  78. begin
  79.   for i:=0 to N-M-1 do
  80.     mt[i]:=mt[i+M] xor {twist} (((mt[i] and MASK_UPPER) or
  81.     (mt[i+1] and MASK_LOWER)) shr 1)xor(dword(-(mt[i+1] and 1)) and A);
  82.   for i:=N-M to N-2 do
  83.     mt[i]:=mt[i+(M-N)]xor{twist}(((mt[i] and MASK_UPPER) or
  84.     (mt[i+1] and MASK_LOWER)) shr 1)xor(dword(-(mt[i+1] and 1)) and A);
  85.     mt[N-1]:=mt[M-1] xor {twist} (((mt[n-1] and MASK_UPPER) or (mt[0] and
  86.     MASK_LOWER)) shr 1)xor(dword(-(mt[0] and 1)) and A);
  87.   index:=0;
  88. end;
  89.  
  90. class constructor TThreadSafeRandom.create;
  91. begin
  92.   initialize(0);
  93.   mtOldRandSeed := 0;
  94. end;
  95.  
  96. class procedure TThreadSafeRandom.Randomize;
  97. begin
  98.   // Hm. Not ideal...
  99.   system.Randomize;
  100.   // assumes the Randseed is atomic for read
  101.   mtrandseed := RandSeed;
  102. end;
  103.  
  104. class function TThreadSafeRandom.Random: extended;overload;inline;static;
  105. begin
  106.   Result := IM * CONVERT_UNSIGNED
  107. end;
  108.  
  109. class function TThreadSafeRandom.Random(range: longint): longint;
  110. begin
  111.   if Range < 0 then inc(Range);
  112.   Result := IM * Range shr 32;
  113. end;
  114.  
  115. class function TThreadSafeRandom.Random(range: int64): int64;
  116. begin
  117.   Result:=IM;
  118.   Result:=Result or ((qword(IM) shl 32) and high(int64));
  119.   if Range<>0 then
  120.     Result := Result mod range
  121.   else
  122.     Result := 0;
  123. end;
  124.  
  125. class function TThreadSafeRandom.IM: Cardinal;inline;static;
  126. var
  127.   i:integer;
  128. begin
  129.   i := index;
  130.   if  (index >= N) or (mtRandSeed<>mtOldRandSeed) then
  131.   begin
  132.     Twist;
  133.     mtRandSeed:=not(mtRandSeed);
  134.     mtOldRandSeed:=mtRandSeed;
  135.     i := index;
  136.   end;
  137.   Result := mt[i];
  138.   index := i + 1;
  139.   Result := Result xor (mt[i] >> U);
  140.   Result := Result xor (Result << S) and B;
  141.   Result := Result xor (Result << T) and C;
  142.   Result := Result xor (Result >> L);
  143. end;
  144. 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]
  1. program randomtests;
  2. {$assertions on}
  3. uses
  4.   // prngenerators,marsaglia;
  5.   tsrandom;
  6.  
  7. var
  8.   i:integer;
  9. begin
  10.   Randseed := 12345;
  11.   TsRand.Randseed := Randseed;
  12.   writeln('FPC     <Random>   tsRAND');
  13.   writeln('-------------------------');
  14.   for i := 1 to 10 do
  15.   begin
  16.     write(Random(100):12,'|',TsRand.Random(100):12);
  17.     if i mod 1 = 0 then writeln;
  18.   end;
  19.   Assert(randseed-tsRand.Randseed = 0,'Fatal error: Randseeds are out of sync');
  20.   for i := 1 to 10 do
  21.   begin
  22.     write(Random:4:10,'|',TsRand.Random:4:10);
  23.     if i mod 1 = 0 then writeln;
  24.   end;
  25.   Assert(randseed-tsRand.Randseed = 0,'Fatal error: Randseeds are out of sync');
  26.   writeln('-------------------------');
  27.  
  28. end.


« Last Edit: April 03, 2017, 11:54:07 am by Thaddy »
Why do the Danish always try to fuck up any programming language?

jwdietrich

  • Hero Member
  • *****
  • Posts: 925
    • formatio reticularis
Re: Randomize improvement
« Reply #3 on: April 04, 2017, 09:53:06 pm »
Thanks! :)
function GetRandomNumber: integer; // xkcd.com
begin
  GetRandomNumber := 4; // chosen by fair dice roll. Guaranteed to be random.
end;

Lazarus 1.6.4 | FPC 3.0.2 | PPC, Intel, ARM | macOS, Windows, Linux

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus