Recent

Author Topic: Is there a faster random function?  (Read 9015 times)

Gustavo 'Gus' Carreno

  • Hero Member
  • *****
  • Posts: 1119
  • Professional amateur ;-P
Re: Is there a faster random function?
« Reply #15 on: March 03, 2024, 11:20:04 am »
Hey Thaddy,

This means by rough estimate that random eats about 95% of the processing power! :shock:
That can't de unless you call randomize all the time. You should call that just once.
Choose one of the Marsalia randoms that do not use mod.
https://wiki.freepascal.org/Marsaglia%27s_pseudo_random_number_generators

Thanks!! This is awesome!!!

Will have a go at this next!!!

Cheers,
Gus
Lazarus 3.99(main) FPC 3.3.1(main) Ubuntu 23.10 64b Dark Theme
Lazarus 3.0.0(stable) FPC 3.2.2(stable) Ubuntu 23.10 64b Dark Theme
http://github.com/gcarreno

Thaddy

  • Hero Member
  • *****
  • Posts: 14352
  • Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #16 on: March 03, 2024, 12:28:01 pm »
Note I just edited the wiki to provide a previous not implemented Randomize.
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

Gustavo 'Gus' Carreno

  • Hero Member
  • *****
  • Posts: 1119
  • Professional amateur ;-P
Re: Is there a faster random function?
« Reply #17 on: March 03, 2024, 02:06:47 pm »
Hey Thaddy,

Note I just edited the wiki to provide a previous not implemented Randomize.

Thank you so much for that!!!!

Cheers,
Gus
Lazarus 3.99(main) FPC 3.3.1(main) Ubuntu 23.10 64b Dark Theme
Lazarus 3.0.0(stable) FPC 3.2.2(stable) Ubuntu 23.10 64b Dark Theme
http://github.com/gcarreno

Nitorami

  • Sr. Member
  • ****
  • Posts: 489
Re: Is there a faster random function?
« Reply #18 on: March 03, 2024, 04:05:25 pm »
I am currently putting together a few fast, small-footprint and good quality random generators for MonteCarlo simulations. My favourite candidate used to be George Marsaglias MWC as posted by Eric, just in plain Pascal. On my laptop, it takes 1.2ns per call (32bit) in a micro-benchmark.

I recently replaced it by Bob Jenkin's "no nice math" small chaotic generator. This is based on random invertible mappings and produces excellent quality numbers at 0.9ns per call (www.burtleburtle.net). There is one issue with that sort of generators: they have no fixed period and have a small risk of falling into shorter cycles, in theory down to 1. The risk is however astronomically small and not of any practical concern. You'll find an extensive review and test results on Melissa O'Neills page https://www.cs.hmc.edu/~oneill/.

A very similar generator is Chris Doty-Humphrey's SFC. By feeding a counter into the mapping stage, he can guarantee a minimum period of 2^32. On my machine, it achieves similar performance as Bob Jenkin's.

My priority is speed, so I made a reduced version with smaller state. It takes 0.73ns per call at still very good statistical quality. It may not pass the Crush tests because the state is simply too small but even the 16-bit version passes Rabbit at 1GB file size, so it is good enough for my purpose. You may be able to shave it down to 0.5ns per call by removing one roldword step, of course at the cost of quality.
Here is the code, without randomisation or anything else around.

Code: Pascal  [Select][+][-]
  1. function RNG_Tiny: dword; inline;
  2. const state: record A,B,C: dword end = (A:12; b:12376; C:8763);
  3. begin
  4.   with state do begin
  5.     c := c+1;
  6.     b := a+roldword (b,18);
  7.     a := roldword (a,7) + b+c;
  8.     result := a;
  9.   end;
  10. end;
  11.  


EDIT: Simply by removing the counter (c), the performance goes up to 0.5ns/call, or 2 billion values per second, on a single core of a CPU with 2.5GHz core speed. I think this is the fastest you can possibly get. The generator still passes the rabbit tests; the price for omitting the counter is factor 2^32 shorter period, and no minimum period can be guaranteed. It is possible that with certain seed values the generator falls into shorter cycles than average (average should be around 2^62). That should hardly be of concern for your application.
« Last Edit: March 03, 2024, 05:18:55 pm by Nitorami »

speter

  • Sr. Member
  • ****
  • Posts: 349
Re: Is there a faster random function?
« Reply #19 on: March 04, 2024, 12:52:31 am »
I got a range check error when I tested Nitorami's function.

I've attached the project. This is the calling code...

Code: Pascal  [Select][+][-]
  1. var
  2.   a : integer;
  3.   k : dWord;
  4. begin
  5.   for a := 1 to 20 do
  6.     begin
  7.       k := RNG_Tiny;
  8.       memo1.append(k.tostring);
  9.     end;
  10. end;

The error comes at line 7 in the code above (line 60 in the project).

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills. :)

Thaddy

  • Hero Member
  • *****
  • Posts: 14352
  • Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #20 on: March 04, 2024, 06:38:24 am »
yes there is  a - actually 3 - range error in that function code, It should expand to qword to prevent that.
Code: Pascal  [Select][+][-]
  1. function RNG_Tiny: dword; inline;
  2. const state: record A,B,C: dword end = (A:12; b:12376; C:8763);
  3. begin
  4.   with state do begin
  5.     c := c+1;                  // <--- here
  6.     b := a+roldword (b,18);   // <--- here
  7.     a := roldword (a,7) + b+c;// <--- here
  8.     result := a;
  9.   end;
  10. end;
All additions can cause a range check / overflow.
Also note that rol can be quite an expensive instruction on some CPU's compared to xor and shifts. The function can't beat xorshift for speed and xorshift can not overflow by definition.
Of course in some cases range is not important as long as the result can be tested for randomness.
It also assumes writeable constants, and if that is allowed, this xorshift is much faster:
Code: Pascal  [Select][+][-]
  1. //Marsalia's first idea for xorshift algorithm
  2.   function xos: Cardinal;
  3.   {$push}{$T+}
  4.   const Fseed:Cardinal = 123456789;
  5.   {$pop}
  6.   begin
  7.     FSeed := FSeed xor (FSeed shl 13);
  8.     FSeed := FSeed xor (FSeed shr 17);
  9.     FSeed := FSeed xor (FSeed shl 5);
  10.     Result:= FSeed;
  11.   end;

Note both Nitorami's function and mine have no way to reset the state! Which means they are of limited applicability.

Also note that shortly after the above one Marsaglia published an improved version that I will add later.
The main difference is that it has one more state compared to Nitorami's function.
This is the original from the scientific publication, which is btw the precursor to FPC's current random generator xorshift** (in trunk)
Code: Pascal  [Select][+][-]
  1. function xor128:Cardinal;inline;
  2. {$push}{$T+}
  3. const  
  4.   x:cardinal=123456789;y:cardinal=362436069;
  5.   z:cardinal=521288629;w:cardinal=88675123;
  6. {$pop}
  7. var
  8.   t:cardinal;
  9. begin
  10.   t:=(x xor(x<<11));x:=y;y:=z;z:=w;w:=(w xor(w>>19)) xor(t xor (t>>8));
  11.   result := w;
  12. end;
Delphi's LCG is also really fast, btw,

« Last Edit: March 04, 2024, 08:10:56 am by Thaddy »
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

Nitorami

  • Sr. Member
  • ****
  • Posts: 489
Re: Is there a faster random function?
« Reply #21 on: March 04, 2024, 08:06:38 am »
@sPeter: Always disable checks for such low level stuff, once you know what you are doing, as these checks can slow things down significantly. This can be done locally. BTW - I don't get a range check error (x86-win32) but an arithmetic overflow. Of course, but the code works and does not cause any harm. You may safely use {$R-,Q-} to turn checks off.

@Thaddy: roldword/rordword are intrinsics and equally fast as shift operations on modern PCs. Only if the rotation must be emulated by two shifts, then it becomes slower. This is e.g. the case when using rolqword with the 32bit compiler.

And - have you tested the xorshift ? I have tested many generators, and don't use xorshift because 1) it has only a period of 2^32, 2) it generates each 32-bit-word exactly once only, 3) it has known flaws and fails quickly on randomness tests, and 4) and most important, it is MUCH slower on my machine, approximately factor 3. This is because the repeated reading and writing to the same variable FSeed prevents the CPU from parellelising the flow. It may have been a fast generator when Marsalia designed it but times have changed.

Thanks for the hint about writeable constants. I tend to forget this because I normally use mode objfpc.

EDIT
Microbenchmark xos: 1.45ns
xor128: 0.9ns

Rabbit test of xor128
       Test                          p-value
 ----------------------------------------------
  5  LinearComp                     1 - eps1
 22  MatrixRank, 320 x 320            eps
 23  MatrixRank, 1024 x 1024          eps
 ----------------------------------------------
 All other tests were passed

But I agree these flaws will not be an issue for the OP's purposes.
« Last Edit: March 04, 2024, 08:21:08 am by Nitorami »

Thaddy

  • Hero Member
  • *****
  • Posts: 14352
  • Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #22 on: March 04, 2024, 08:14:22 am »
No the above is only tested for compilation.
I can test it in the same manner as I did for the wiki. Have to look up my test sources.
(See diagram in the wiki,  FIPS-140-2 and Diehard)
« Last Edit: March 04, 2024, 08:29:37 am by Thaddy »
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

Gustavo 'Gus' Carreno

  • Hero Member
  • *****
  • Posts: 1119
  • Professional amateur ;-P
Re: Is there a faster random function?
« Reply #23 on: March 05, 2024, 09:32:07 am »
Hey Thaddy,

I've made this repository from your Free Pascal Wiki entry.

I'm using my default trend and using the MIT License.

But this is your code and I need you to guide me on what License to use, or even just use the Unlicense one.

Can you please advise?

Cheers,
Gus
Lazarus 3.99(main) FPC 3.3.1(main) Ubuntu 23.10 64b Dark Theme
Lazarus 3.0.0(stable) FPC 3.2.2(stable) Ubuntu 23.10 64b Dark Theme
http://github.com/gcarreno

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Re: Is there a faster random function?
« Reply #24 on: March 12, 2024, 10:37:43 am »
Although not as fast as the fastest, this gives excellent quality.
It runs 3 LCGs in parallel, with prime numbers as the main parameters. It passes all tests in PractRand. You can use any prime numbers for the 3 main parameters (multiplier, modulus, seed), which provides almost unlimited extensibility. For example, you could cycle through a series of prime number parameters, as each parameter set reached the end of its period.
Code: Pascal  [Select][+][-]
  1. function LCG3:uint32; inline;
  2. var
  3. CON1 :uint32 = 1;
  4. MUL1 :uint32 = 65419;
  5. MOD1 :uint32 = 65423;
  6. SEED1 :uint32 = 65437;
  7.  
  8. CON2 :uint32 = 1;
  9. MUL2 :uint32 = 65447;
  10. MOD2 :uint32 = 65449;
  11. SEED2 :uint32 = 65479;
  12.  
  13. CON3 :uint32 = 1;
  14. MUL3 :uint32 = 65497;
  15. MOD3 :uint32 = 65519;
  16. SEED3 :uint32 = 65521;
  17. begin
  18. SEED1:= (((SEED1 * MUL1) + CON1) MOD MOD1);
  19. SEED2:= (((SEED2 * MUL2) + CON2) MOD MOD2);
  20. SEED3:= (((SEED3 * MUL3) + CON3) MOD MOD3);
  21. RESULT:= ((SEED1 XOR SEED2 XOR SEED3) MOD 4294967296);
  22. end;
Note that the constants used here are just an example. Any prime numbers can be used (within the limits of the word size), and the statistical quality is always excellent.
It is reasonably fast (on my PC, 18ns per call for the 32-bit version). The method works even better with 64-bit integers, and gives a significantly longer periods.
I think this is good balance between speed, quality and extensibility/flexibility.
See https://en.wikipedia.org/wiki/Wichmann%E2%80%93Hill

Thaddy

  • Hero Member
  • *****
  • Posts: 14352
  • Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #25 on: March 12, 2024, 11:15:37 am »
MUL and even worse MOD? Not to my taste for speed.
You will get the same effect when you call xorshift three times. And I know "a little bit" about equally distributed pseudo randoms as you might know.
It is for PRNG' s also quite old. Science has advanced.
I suspect the current prng in trunk is better and probably faster than that.

The main reason is that a modulo operation other than with powers of two are really expensive, even on modern cpu's.
The reason that a modulo operation with a power of two is faster than a modulo operation with any other value is that a modulo with a power of two can be replaced with
x and (y-1).
The FPC compiler optimizes exactly so automatically and independent of optimization level.
MOD operations with a non-power of two requires quite a " few" more cycles. Read: a lot!

Note that the new PRNG in trunk uses just xor, rotate and shift.
https://wiki.freepascal.org/index.php?title=User_Changes_Trunk#Random_generator
« Last Edit: March 12, 2024, 11:40:51 am by Thaddy »
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

Thaddy

  • Hero Member
  • *****
  • Posts: 14352
  • Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #26 on: March 12, 2024, 12:08:21 pm »
Hey Thaddy,

I've made this repository from your Free Pascal Wiki entry.

I'm using my default trend and using the MIT License.

But this is your code and I need you to guide me on what License to use, or even just use the Unlicense one.

Can you please advise?

Cheers,
Gus
My code is free as in free beer licensed. I am not aware of any licensing issues, but much is of course copyrighted, but not licensed. E.g. the same as Marsaglia's code. There are also no known patent issues.
(Note some other prng' s are patented. I translated them but left them out on purpose, besides, they are not even good enough)
« Last Edit: March 12, 2024, 12:15:24 pm by Thaddy »
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

Gustavo 'Gus' Carreno

  • Hero Member
  • *****
  • Posts: 1119
  • Professional amateur ;-P
Re: Is there a faster random function?
« Reply #27 on: March 13, 2024, 06:19:18 pm »
Hey Thaddy,

My code is free as in free beer licensed. I am not aware of any licensing issues, but much is of course copyrighted, but not licensed. E.g. the same as Marsaglia's code. There are also no known patent issues.

I'm very, VERY ignorant of the minutia of licensing, so in that context, me doing it under MIT by default, is Ok, or is it not Ok?

(Note some other prng' s are patented. I translated them but left them out on purpose, besides, they are not even good enough)

My intention was to have a personal record of those functions, kinda like spread the knowledge among various sources.
I don't mind the quality, or lack thereof. It's the quality of the knowledge that I'm after.

Cheers,
Gus
Lazarus 3.99(main) FPC 3.3.1(main) Ubuntu 23.10 64b Dark Theme
Lazarus 3.0.0(stable) FPC 3.2.2(stable) Ubuntu 23.10 64b Dark Theme
http://github.com/gcarreno

Thaddy

  • Hero Member
  • *****
  • Posts: 14352
  • Sensorship about opinions does not belong here.
Re: Is there a faster random function?
« Reply #28 on: March 13, 2024, 06:42:17 pm »
It is OK to re-licensed it to MIT, but I would prefer NOLICENSE
« Last Edit: March 14, 2024, 06:59:59 am by Thaddy »
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

Gustavo 'Gus' Carreno

  • Hero Member
  • *****
  • Posts: 1119
  • Professional amateur ;-P
Re: Is there a faster random function?
« Reply #29 on: March 13, 2024, 06:51:50 pm »
Hey Thaddy,

It is OK to re-licensed it to MIT, but I would prefer NOLICECE

Ay, ay Sir 🫡 !!

Will change it to "The Unlicense" !!

Cheers,
Gus
Lazarus 3.99(main) FPC 3.3.1(main) Ubuntu 23.10 64b Dark Theme
Lazarus 3.0.0(stable) FPC 3.2.2(stable) Ubuntu 23.10 64b Dark Theme
http://github.com/gcarreno

 

TinyPortal © 2005-2018