Recent

Author Topic: Randomize improvement  (Read 8627 times)

Eugene Loza

  • Hero Member
  • *****
  • Posts: 663
    • My games in Pascal
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 FOSS games in FreePascal&CastleGameEngine: https://decoherence.itch.io/ (Sources: https://gitlab.com/EugeneLoza)

Jonas Maebe

  • Hero Member
  • *****
  • Posts: 1058
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: 14201
  • Probably until I exterminate Putin.
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 »
Specialize a type, not a var.

jwdietrich

  • Hero Member
  • *****
  • Posts: 1232
    • 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;

http://www.formatio-reticularis.de

Lazarus 2.2.6 | FPC 3.2.2 | PPC, Intel, ARM | macOS, Windows, Linux

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Randomize improvement
« Reply #4 on: July 24, 2019, 06:28:37 am »
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.
Specialize a type, not a var.

abouchez

  • Full Member
  • ***
  • Posts: 110
    • Synopse
Re: Randomize improvement
« Reply #5 on: November 26, 2020, 09:08:07 pm »
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/bbda37425bf8eb0ffa859d813e712ad2de6edbd4/src/core/mormot.core.base.pas#L8264

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Randomize improvement
« Reply #6 on: November 26, 2020, 09:27:47 pm »
(-) 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

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Randomize improvement
« Reply #7 on: November 26, 2020, 10:04:03 pm »
It 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?  >:D >:D when it should be one?  8-)
« Last Edit: November 26, 2020, 10:21:12 pm by Thaddy »
Specialize a type, not a var.

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: Randomize improvement
« Reply #8 on: November 27, 2020, 03:47:49 pm »
It 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.

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?  >:D >:D when it should be one?  8-)

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

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Randomize improvement
« Reply #9 on: November 27, 2020, 05:31:48 pm »
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);.
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.
« Last Edit: November 27, 2020, 05:46:07 pm by Thaddy »
Specialize a type, not a var.

 

TinyPortal © 2005-2018