Lazarus

Programming => General => Topic started by: ezlage on October 05, 2016, 01:41:15 am

Title: randomize
Post by: ezlage on October 05, 2016, 01:41:15 am
Friends,

In some way, at some time, somewhere, someone told me that I should not use the command "randomize" more than once in the program.

This information is true? How do I know if the command has already been executed in the application?

Sorry by my poor english.
Thank you.
Title: Re: randomize
Post by: Eugene Loza on October 05, 2016, 07:03:12 am
someone told me that I should not use the command "randomize" more than once in the program
The manual says:
Quote
Randomize initializes the random number generator of Free Pascal, by giving a value to Randseed, calculated with the system clock.
More detailed analysis shows:
Code: Pascal  [Select][+][-]
  1.   procedure randomize;
  2.   begin
  3.     randseed:=GetTickCount;
  4.   end;
So, basically you can use "randomzie" as often as you like. However... do you really need to? Once is perfectly enough.

(UPD) Hovwever... Yes. If I understand correctly GetTickCount (quote) "provides number of milliseconds since Windows was started". So, you get only ~58 millions random sequences per day of a normal software user who turns off the computer at night :) Basically if you "measure" 1-second long random number sequences you might get a repeat in a year or two. And if you repeat the experiment in special conditions (e.g. right after turning on the computer) you have a ~0.01% chance to catch a repeating combination if startred manually and much higher probability if started in autorun. If you call randomize again somewhere in an non-trivial place you might mixh those random sequences, so, basically you get absolutely unrepeatable combinations of random numbers.
But that doesn't make any practical sense, right?

So IMHO: If you don't need multiple randomize - don't do them. It'll just mess up your code without any good sense. If you accidentally or unavoidably have more than one randomize - don't care.
Title: Re: randomize
Post by: useroflazarus on October 05, 2016, 07:53:10 am
for random seed you can use the local variables:

Code: Pascal  [Select][+][-]
  1. procedure TForm1.FormActivate(Sender: TObject);
  2. var rndDouble : double;
  3. begin
  4.   Edit1.Text:=floattoStr(rndDouble);
  5. end;
  6.  

Every time it generate random value, for example:
DEC                                                    HEX
5,88763352687033E-297             026ECDCFFFFFFFFD
5,50401551648458E-297             026CCBFFFFFFFFFB
1,21524922083397E-296             027FCA700000001A
....
after it you can interpretate HEX as integer or calculate crc32 or other... :)
Title: Re: randomize
Post by: Thaddy on October 05, 2016, 08:02:19 am
@useroflazarus
You seem to take advantage of a dirty stack. That is wrong. The local stack is dirty, yes, and appears to give random values, but in fact it is often deterministic.
Therefor it is not suitable as a random seed.
Apart from gettickcount,some processors, like the one in the RaspberryPi, modern intels too, are able to generate a hwrnd value that can be used as random seed and have (close to) indeterministic values.

What is worse, that code relies on specific compiler settings. E.g. try to compile with -Ct and that code is not random.
Title: Re: randomize
Post by: RAW on October 05, 2016, 01:39:07 pm
I found this in an old Delphi-Book...
Code: Pascal  [Select][+][-]
  1. Procedure MyRandomize;
  2.  Begin
  3.   Randomize;
  4.   RandSeed:= ((RandSeed Shl 8) Or GetCurrentProcessID) Xor GetTickCount;
  5.  End;    
  6.  
Title: Re: randomize
Post by: marcov on October 05, 2016, 02:27:47 pm
Repeated seeding of randomize (besides being useless) can cause non uniform distributions of random results.
Title: Re: randomize
Post by: RAW on October 05, 2016, 03:08:07 pm
Thanks a lot...
I need RANDOMIZE in my next program, so I decided to check if this is working better than the "normal" one.
Now I don't use it  :)

The explanation in the book was: ..without RANDOMIZE RANDSEED starts at zero...
(very old Delphi-Book)
Title: Re: randomize
Post by: Thaddy on October 05, 2016, 04:13:34 pm
That's because randomness in computing has to be able to reproduce itself for e.g. statistical reasons.
Clearly not something your math teacher payed any attention to, even worse if it was your programming teacher..
(Grumpy mode again) >:D

Random means a distribution close to equal chance, white noise if you want.
The seed determines where it starts.
If you do not use a random seed, the distribution is still equal, but it is repeatable.
You actually need that.... Guess why?
(Actually the Mersenne twister in FPC  and other algorithms all output the same results given the same seed)
Title: Re: randomize
Post by: Eugene Loza on October 05, 2016, 08:36:11 pm
Hmm... and I've just came up with a simlar question.
Can I get TWO random seeds simultaneously running flawlessly in FPC without making some "my own random generation procedure"?

In detail:
I'm generating a map for a computer game based on random.
If I give the random equal random seed it'll generate equal maps (that's what I want).
BUT, there are a few parallel processes running like "generating..." and a random image, which uses random and therefore disrupts the random sequence of the map generation process.
Can I separate "random for map generation which has to strictly reproduce the random numbers sequence" and "everything else I don't care about"?

Or should I just write my own random number generator? E.g. Xorshift algorithm? I might even gain some performance boost :)
Title: Re: randomize
Post by: useroflazarus on October 05, 2016, 08:55:19 pm

Or should I just write my own random number generator? E.g. Xorshift algorithm? I might even gain some performance boost :)

https://en.wikipedia.org/wiki/Mersenne_Twister который используется в Lazarus достаточно быстрый, можно его алгоритм и использовать :)
Title: Re: randomize
Post by: Eugene Loza on October 05, 2016, 09:33:24 pm
https://en.wikipedia.org/wiki/Mersenne_Twister который используется в Lazarus достаточно быстрый, можно его алгоритм и использовать :)
Можно, но xorshift кажется проще :) и мне, вообще говоря, не нужен "идеальный" генератор случайных чисел - они должны быть просто последовательностью чисел для генерации карты для компьютерной игры...

Yes. It's possible, but Xorshift seems much simpler and I don't really need ideal random distribution, just a random for my map generator:
Code: Pascal  [Select][+][-]
  1. var x,y,z,w: Cardinal;
  2.  
  3. procedure Xorshift_randomize;
  4. begin
  5.  randomize;
  6.  x:=random(maxint);
  7.  y:=random(maxint);
  8.  z:=random(maxint);
  9.  w:=random(maxint);
  10. end;
  11.  
  12. function xorshift:single;
  13. var t: Cardinal;
  14. begin
  15.   t:=x;
  16.   t:=t xor (t shl 11);
  17.   t:=t xor (t shr 8);
  18.   x:=y;
  19.   y:=z;
  20.   z:=w;
  21.   w:=w xor (w shr 19);
  22.   w:=w xor t;
  23.   result:=w/maxint/2;
  24. end;
Title: Re: randomize
Post by: User137 on October 05, 2016, 10:14:56 pm
Hmm... and I've just came up with a simlar question.
Can I get TWO random seeds simultaneously running flawlessly in FPC without making some "my own random generation procedure"?
You can use the fpc's own random() for multiple sets, but it involves on you managing multiple sets of randseed.

Code: Pascal  [Select][+][-]
  1. var
  2.   seeds: array of cardinal; // Use same type as randseed
  3.   currSet: integer;
  4.  
  5. function RandomSet(setN: integer): single;
  6. begin
  7.   if setN <> currSet then begin
  8.     seeds[currSet]:=randseed;
  9.     randseed:=seeds[setN];
  10.     currSet:=setN;
  11.   end;
  12.   result:=random;
  13. end;
Title: Re: randomize
Post by: Eugene Loza on October 05, 2016, 10:23:51 pm
You can use the fpc's own random() for multiple sets, but it involves on you managing multiple sets of randseed
Thanks a lot! This one looks really nice!
Title: Re: randomize
Post by: Eugene Loza on October 05, 2016, 10:33:43 pm
UPD: I've tested and XorShift algorithm above works 3.16 times faster than FPC random :)
Title: Re: randomize
Post by: ezlage on October 06, 2016, 01:29:13 pm
So, basically you can use "randomzie" as often as you like. However... do you really need to? Once is perfectly enough.

No, I do not need to run it more than once. I can prevent the command to run for my class after having already been performed in another piece of code, just checking if the variable "RandSeed" is zero. So I wanted to know if I have to worry about the rest of the code of a program that uses my class.

So IMHO: If you don't need multiple randomize - don't do them. It'll just mess up your code without any good sense. If you accidentally or unavoidably have more than one randomize - don't care.

This helps me! Thank you, Eugene.
Title: Re: randomize
Post by: ezlage on October 06, 2016, 01:32:19 pm
Apart from gettickcount,some processors, like the one in the RaspberryPi, modern intels too, are able to generate a hwrnd value that can be used as random seed and have (close to) indeterministic values.

Thaddy, how can I take advantage of this feature of Intel processors?
Title: Re: randomize
Post by: Eugene Loza on October 06, 2016, 01:38:35 pm
if I have to worry about the rest of the code of a program that uses my class.
Randomize sets a "global" randseed. I.e. randomize affects all the code (units, classes, any part of the code, maybe, except external dll libraries) whenever you initialize it.

P.S. I've tested XorShift algorithm above and it is 3x faster at 64 bit system... but 1.5x slower at 32 bit! I'll have to modify it a little to preform better for 32 bit, I think... I remember there's another approach to the algorithm for 32-bit systems random number generation...
Title: Re: randomize
Post by: ezlage on October 06, 2016, 01:42:51 pm
In some way, at some time, somewhere, someone told me that I should not use the command "randomize" more than once in the program.

I found it: http://forum.lazarus.freepascal.org/index.php?topic=19183.0
Title: Re: randomize
Post by: jwdietrich on May 10, 2025, 11:32:36 pm
Randomize is a computationally expensive function. It slows down the program significantly. Therefore, it is advisable to use it once only.
Title: Re: randomize
Post by: Thaddy on May 11, 2025, 08:50:33 am
Some notes about the current status of cspring randoms:
1. If you are on Linux, please note that if your kernel version is 4.8 or higher you can simply read /dev/urandom (not random, but urandom) for cryptographically secure random data.
2. Unless you still need to support XP and older, on Windows you should use the bcrypt api and NOT the commonly used older crypto api.

Both are much faster and more secure than running through hoops like the examples we had to give in the olden days.

For the people who do want to look stupid by arguing otherwise: yes, urandom is cspring for modern kernels. It works such that the entropy pool is already filled before the startup of the system is completed.
The bcrypt API in Windows is preferred over the old crypto api for years, but a good satisfactory translation is not yet available. I have some small examples:
First bcrypt unit:
Code: Pascal  [Select][+][-]
  1. unit BCrypt;
  2.  
  3. interface
  4. { this partial bcrypt translation covers only the cryptographically
  5.   secure pseudo random generator (cspring) part }
  6. uses
  7.   Windows;
  8.  
  9. const
  10. { comes as 32 bit and 64 bit, Intel, arm and aarch64,
  11.   depending on windows platform }
  12.   BCRYPT_LIB = 'bcrypt.dll';
  13. // NTSTATUS values
  14.   STATUS_SUCCESS = $00000000;
  15. // Algorithm Identifiers
  16.   BCRYPT_RNG_ALGORITHM       = 'RNG';
  17.   BCRYPT_RNG_FIPS186_DSA_ALGORITHM = 'FIPS186DSARNG';
  18.   BCRYPT_RNG_DUAL_EC_ALGORITHM = 'DUALECRNG';
  19. // Flags
  20.   BCRYPT_RNG_USE_ENTROPY_IN_BUFFER = $00000001;
  21.   BCRYPT_USE_SYSTEM_PREFERRED_RNG = $00000002;
  22.  
  23. type
  24.   BCRYPT_ALG_HANDLE = THandle;
  25.   PBCRYPT_ALG_HANDLE = ^BCRYPT_ALG_HANDLE;
  26.   NTSTATUS = LongInt;
  27.  
  28. // Function prototypes
  29. function BCryptOpenAlgorithmProvider(
  30.   phAlgorithm: PBCRYPT_ALG_HANDLE;
  31.   pszAlgId: LPCWSTR;
  32.   pszImplementation: LPCWSTR;
  33.   dwFlags: DWORD
  34. ): NTSTATUS; winapi; external BCRYPT_LIB;
  35.  
  36. function BCryptCloseAlgorithmProvider(
  37.   hAlgorithm: BCRYPT_ALG_HANDLE;
  38.   dwFlags: DWORD
  39. ): NTSTATUS; winapi; external BCRYPT_LIB;
  40.  
  41. function BCryptGenRandom(
  42.   hAlgorithm: BCRYPT_ALG_HANDLE;
  43.   pbBuffer: PUCHAR;
  44.   cbBuffer: ULONG;
  45.   dwFlags: DWORD
  46. ): NTSTATUS; winapi; external BCRYPT_LIB;
  47.  
  48. implementation
  49. end.
Second a cross-platform cspring:
Code: Pascal  [Select][+][-]
  1. unit uCspring;
  2. {$mode objfpc}
  3. interface
  4. { cross-platform cspring }
  5. function SystemCSPRNG(var Buffer; Bytes: LongWord): Boolean;inline;
  6.  
  7. implementation
  8. uses
  9.   {$ifdef mswindows}windows,bcrypt;{$endif}
  10.   {$ifdef UNIX}cthreads;{$endif}
  11.  
  12. {$ifdef mswindows}
  13. function WinCSPRNG(var Buffer; Bytes: LongWord): Boolean;
  14. var
  15.   hAlgorithm: PBCRYPT_ALG_HANDLE;
  16. begin
  17.   Result := False;
  18.   if BCryptOpenAlgorithmProvider(@hAlgorithm, BCRYPT_RNG_ALGORITHM, nil, 0) = STATUS_SUCCESS then
  19.   try
  20.     if BCryptGenRandom(PtrUint(hAlgorithm), @Buffer, Bytes, 0) = STATUS_SUCCESS then
  21.       Result := True;
  22.   finally
  23.     BCryptCloseAlgorithmProvider(ptrUint(hAlgorithm), 0);
  24.   end;
  25. end;
  26. (*
  27. { this is for XP, that does not have bcrypt, change windows to jwaWindows. }
  28. function WinLegacyCSPRNG(var Buffer; Count: DWORD): Boolean;
  29. var
  30.   hProv: HCRYPTPROV;
  31. begin
  32.   Result := CryptAcquireContext(hProv, nil, nil, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
  33.   if Result then
  34.   try
  35.     Result := CryptGenRandom(hProv, Count, @Buffer);
  36.   finally
  37.     CryptReleaseContext(hProv, 0);
  38.   end;
  39. end;
  40. *)
  41. {$else}
  42.  
  43. { The Linux CSPRING can simply be read from /dev/urandom on modern
  44.    kernels >= 4.8 and is cryptographically secure. Entropy is determined
  45.    during system startup and so directly available when startup is finished.
  46.    Older kernels, though, used a simpler less secure PRNG, without taking
  47.    enough entropy from the hardware }
  48. function UnixCSPRNG(var Buffer; Bytes: LongWord): Boolean;
  49. var
  50.   f: File of byte;
  51. begin
  52.   Result := False;
  53.   Assign(f, '/dev/urandom');
  54.   Reset(f, 1);
  55.   try
  56.     BlockRead(f, Buffer, Bytes);
  57.     Result := True;
  58.   finally
  59.     Close(f);
  60.   end;
  61. end;
  62. {$endif}
  63.  
  64. function SystemCSPRNG(var Buffer; Bytes: LongWord): Boolean;
  65. begin
  66.   {$IFDEF WINDOWS}
  67.     Result := WinCSPRNG(Buffer, Bytes);
  68.   {$ENDIF}
  69.   {$IFDEF UNIX }
  70.     Result := UnixCSPRNG(Buffer, Bytes);
  71.   {$ENDIF}
  72. end;
  73. end.
This code completely bypasses any other random number generators and is also much, much faster.

Demo:
Code: Pascal  [Select][+][-]
  1. program cspringdemo;
  2. { demo for various sizes of cspring random numbers, signed and unsigned. }
  3. {$mode objfpc}
  4. uses ucspring;
  5.  
  6. var
  7.   // unsigned
  8.   Buf8 : array[0..9] of byte;
  9.   Buf16: array[0..9] of word;
  10.   Buf32: array[0..9] of dword;
  11.   Buf64: array[0..9] of qword;
  12.   // signed
  13.   Buf8s : array[0..9] of ShortInt;
  14.   Buf16s: array[0..9] of SmallInt;
  15.   Buf32s: array[0..9] of integer;
  16.   Buf64s: array[0..9] of int64;
  17.   b:ShortInt;
  18.   c:SmallInt;
  19.   d:Integer;
  20.   e:Int64;
  21.   f:byte;
  22.   g:word;
  23.   h:dword;
  24.   i:qword;
  25. begin
  26.   if SystemCSPRNG(Buf8s,length(Buf8s)) then
  27.     for b in Buf8s do write(b:5);
  28.   writeln;
  29.   if SystemCSPRNG(Buf16s,length(Buf16s) * 2) then
  30.     for c in Buf16s do write(c:10);
  31.   writeln;
  32.   if SystemCSPRNG(Buf32s,length(Buf32s) * 4) then
  33.     for d in Buf32s do write(d:20);
  34.   writeln;
  35.   if SystemCSPRNG(Buf64s,length(Buf64s) * 8) then
  36.     for e in Buf64s do write(e:40);
  37.   writeln;
  38.   if SystemCSPRNG(Buf8,length(Buf8)) then
  39.     for f in Buf8 do write(f:5);
  40.   writeln;
  41.   if SystemCSPRNG(Buf16,length(Buf16) * 2) then
  42.     for g in Buf16 do write(g:10);
  43.   writeln;
  44.   if SystemCSPRNG(Buf32,length(Buf32) * 4) then
  45.     for h in Buf32 do write(h:20);
  46.   writeln;
  47.   if SystemCSPRNG(Buf64,length(Buf64) * 8) then
  48.     for i in Buf64 do write(i:40);
  49.   writeln;
  50. end.


Title: Re: randomize
Post by: Thaddy on May 11, 2025, 09:44:24 am
Randomize is a computationally expensive function. It slows down the program significantly. Therefore, it is advisable to use it once only.
If you use my above code you do not need to call randomize at all.
Title: Re: randomize
Post by: jwdietrich on May 11, 2025, 11:49:08 am
Randomize is a computationally expensive function. It slows down the program significantly. Therefore, it is advisable to use it once only.
If you use my above code you do not need to call randomize at all.

What is the way to use it on macOS?
Title: Re: randomize
Post by: Thaddy on May 11, 2025, 12:53:52 pm
Randomize is a computationally expensive function. It slows down the program significantly. Therefore, it is advisable to use it once only.
If you use my above code you do not need to call randomize at all.

What is the way to use it on macOS?
AFAIK the UNIX define holds true for MacOS, so should work, I have a Mac mini so I will test that, but I think it should work out of the box.
[edit] It does!.
Performance is well in the μs range. Single byte read 150μs, using blockread it becomes ~12μs per byte read. (M4 mini). Extrapolates to about  850μs for 1 Kb on average.

Side note: Windows > XP also seems to have a system allocated buffer from startup and appropiate entropy, so this is the way to go in the future on most operating systems.
Title: Re: randomize
Post by: Thaddy on May 11, 2025, 05:26:25 pm
For the casual reader: this also means that the original postings in 2016 are no longer relevant, except for the deterministic remarks referring to prng's, not cspring.
TinyPortal © 2005-2018