www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Speed of Random Numbers

reply Giovanni Di Maria <calimero22 yahoo.it> writes:
Hi to everybody
I am doing some experiments about random numbers.
I need "extreme speed" for the generation for numbers from 1 to 8.

Generating 500_000_000 numbers with this code:



-----------------------------
import std.stdio, std.array, std.random;
void main()
{
     byte c;
     writeln("Start");
     for(int k=1;k<=500_000_000;k++)
         c=uniform!ubyte() % 8 +1;  //<<< ======= RANDOM
     writeln("Stop");
}
-----------------------------



I get these results:

c=uniform!ubyte() % 8 +1;  ======>>> Execution time: 15.563 s
c=cast(byte)uniform(1, 9); ======>>> Execution time: 24.218 s

Do you know other faster functions or methods to generate random 
numbers?

For me the "goodness of random" is NOT important.

Thank you very much
GIovanni Di Maria
Aug 03 2019
next sibling parent reply Cym13 <cpicard openmailbox.org> writes:
On Saturday, 3 August 2019 at 16:35:34 UTC, Giovanni Di Maria 
wrote:

 Hi to everybody
 I am doing some experiments about random numbers.
 I need "extreme speed" for the generation for numbers from 1 to 
 8.

 Generating 500_000_000 numbers with this code:



 -----------------------------
 import std.stdio, std.array, std.random;
 void main()
 {
     byte c;
     writeln("Start");
     for(int k=1;k<=500_000_000;k++)
         c=uniform!ubyte() % 8 +1;  //<<< ======= RANDOM
     writeln("Stop");
 }
 -----------------------------



 I get these results:

 c=uniform!ubyte() % 8 +1;  ======>>> Execution time: 15.563 s
 c=cast(byte)uniform(1, 9); ======>>> Execution time: 24.218 s

 Do you know other faster functions or methods to generate 
 random numbers?

 For me the "goodness of random" is NOT important.

 Thank you very much
 GIovanni Di Maria


To what extent isn't the quality of randomness important to you?

Your posts reminds me of the way Doom (the original) did it for 
things like enemy behaviour and shot dispersion: they generated a 
static table of 256 random numbers once and any time they needed 
a random byte they just picked the next in the table. They didn't 
have any security or sciency concern and just wanted to provide a 
different game each time so that worked well for them. You won't 
find anything faster than that I think.
Aug 03 2019
parent Giovanni Di Maria <calimero22 yahoo.it> writes:
On Saturday, 3 August 2019 at 17:17:23 UTC, Cym13 wrote:

 On Saturday, 3 August 2019 at 16:35:34 UTC, Giovanni Di Maria 
 wrote:

 [...]


 To what extent isn't the quality of randomness important to you?

 Your posts reminds me of the way Doom (the original) did it for 
 things like enemy behaviour and shot dispersion: they generated 
 a static table of 256 random numbers once and any time they 
 needed a random byte they just picked the next in the table. 
 They didn't have any security or sciency concern and just 
 wanted to provide a different game each time so that worked 
 well for them. You won't find anything faster than that I think.





Exactly Cym13.
The important is to get a different number
Ok, thank you.
G
Aug 03 2019
prev sibling next sibling parent reply lithium iodate <whatdoiknow doesntexist.net> writes:
On Saturday, 3 August 2019 at 16:35:34 UTC, Giovanni Di Maria 
wrote:

 Do you know other faster functions or methods to generate 
 random numbers?

 For me the "goodness of random" is NOT important.

 Thank you very much
 GIovanni Di Maria


First off you could try to use a faster RNG engine than the 
default. The easiest way is to define a variable containing it 
and passing it to the functions each time.

auto rng = Xorshift(1234);
randomNumber = uniform!uint(rng);

This basic change approximately halved the 5 seconds your 
original example needs on my computer.
Another simple approach that I have tried is simply hashing the 
iterator using a fast hash function.
With xxHash32 I got the time down to 0.25 seconds. I also tried 
xxHash64 and FNV1a but they were not faster in my quick test.
Aug 03 2019
parent reply Giovanni Di Maria <calimero22 yahoo.it> writes:
On Saturday, 3 August 2019 at 17:44:44 UTC, lithium iodate wrote:

 On Saturday, 3 August 2019 at 16:35:34 UTC, Giovanni Di Maria 
 wrote:

 [...]


 First off you could try to use a faster RNG engine than the 
 default. The easiest way is to define a variable containing it 
 and passing it to the functions each time.

 auto rng = Xorshift(1234);
 randomNumber = uniform!uint(rng);

 This basic change approximately halved the 5 seconds your 
 original example needs on my computer.
 Another simple approach that I have tried is simply hashing the 
 iterator using a fast hash function.
 With xxHash32 I got the time down to 0.25 seconds. I also tried 
 xxHash64 and FNV1a but they were not faster in my quick test.




Thank you very much Lithium Iodate
Now i will try it.
I let know you.
Thank you
Giovanni
Aug 03 2019
parent bauss <jj_1337 live.dk> writes:
On Saturday, 3 August 2019 at 17:47:46 UTC, Giovanni Di Maria 
wrote:

 On Saturday, 3 August 2019 at 17:44:44 UTC, lithium iodate 
 wrote:

 On Saturday, 3 August 2019 at 16:35:34 UTC, Giovanni Di Maria 
 wrote:

 [...]


 First off you could try to use a faster RNG engine than the 
 default. The easiest way is to define a variable containing it 
 and passing it to the functions each time.

 auto rng = Xorshift(1234);
 randomNumber = uniform!uint(rng);

 This basic change approximately halved the 5 seconds your 
 original example needs on my computer.
 Another simple approach that I have tried is simply hashing 
 the iterator using a fast hash function.
 With xxHash32 I got the time down to 0.25 seconds. I also 
 tried xxHash64 and FNV1a but they were not faster in my quick 
 test.




 Thank you very much Lithium Iodate
 Now i will try it.
 I let know you.
 Thank you
 Giovanni


If it doesn't matter if it's predictable or not then you could 
easily make your own simple random generator with would give 
"random" results.

Of course in general it's not usable:

import std.stdio;

class Random
{
     private:
     uint _seed;
     uint _interval;

     T abs(T)(T x)
     {
         T y = x > 0 ? T.max : cast(T)0;

         return (x ^ y) - y;
     }

     public:
     this()
     {
         import core.stdc.time;

         _seed = cast(uint)time(null);
         _interval = (_seed - 20559);
     }

     T next(T)(T max)
     {
         auto value = cast(T)(abs(_interval) % T.max);

         _interval -= (_interval / 10) * _seed;

         return value;
     }
}

void main()
{
     auto random = new Random;

     foreach (_; 0 .. 1000)
     {
         auto result = random.next!ubyte(255);
         writeln(result);
     }
}
Aug 03 2019
prev sibling next sibling parent Dennis <dkorpel gmail.com> writes:
On Saturday, 3 August 2019 at 16:35:34 UTC, Giovanni Di Maria 
wrote:

 Do you know other faster functions or methods to generate 
 random numbers?

 For me the "goodness of random" is NOT important.


I found some nice random functions in this public-domain C 
single-header library collection, one of which is GameRand:

https://github.com/mattiasgustavsson/libs/blob/022370a79cf2d5f87fb43b420834a069adb5fede/rnd.h#L449

Here's the D version:
```
struct GameRand
{
	uint[2] state;
}

uint randomGameRand(ref GameRand gamerand) {
     gamerand.state[0] = ( gamerand.state[0] << 16 ) + ( 
gamerand.state[0] >> 16 );
     gamerand.state[0] += gamerand.state[1];
     gamerand.state[1] += gamerand.state[0];
     return gamerand.state[0];
}
```

It's really fast and decent enough for games (hence the name I 
suppose). See:
http://www.flipcode.com/archives/07-15-2002.shtml
Aug 03 2019
prev sibling parent reply matheus <matheus gmail.com> writes:
On Saturday, 3 August 2019 at 16:35:34 UTC, Giovanni Di Maria 
wrote:

 For me the "goodness of random" is NOT important.


If that's the case, you could roll your own RNG:

//DMD64 D Compiler 2.072.2
import std.stdio;
import std.datetime;
import std.array, std.random;

void main(){
     ubyte x;
     auto r = benchmark!(f1,f2)(10_000);
     writeln(r[0]);
     writeln(r[1]);
}

int f1(){
     static s = 10; // Seed
     s = (214013*s+2531011); // [1]
     s = (s>>16)&0x7FFF;
     auto y=(s&7)+1;
     //writeln(y);
     return y;
}

int f2(){
     byte c;
     c=uniform!ubyte() % 8 +1;
     //writeln(c);
     return c;
}


/*
[1] 
https://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
*/

/*
OUTPUT:
TickDuration(65263)   <-f1
TickDuration(635167)  <-f2
*/

Matheus.
Aug 03 2019
parent reply Giovanni Di Maria <calimero22 yahoo.it> writes:
Thank you very much to Everybody!!!!!
Giovanni
Aug 03 2019
next sibling parent Daniel Kozak <kozzi11 gmail.com> writes:
You can try http://code.dlang.org/packages/mir-random

I am using theme here:
https://github.com/TechEmpower/FrameworkBenchmarks/blob/b9cc153dcd1c20e78197b0191536f0d11b8ca554/frameworks/D/vibed/source/postgresql.d#L49

On Sun, Aug 4, 2019 at 12:20 AM Giovanni Di Maria via
Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:

 Thank you very much to Everybody!!!!!
 Giovanni
Aug 04 2019
prev sibling parent Daniel Kozak <kozzi11 gmail.com> writes:
On Sun, Aug 4, 2019 at 11:49 AM Daniel Kozak <kozzi11 gmail.com> wrote:

 You can try http://code.dlang.org/packages/mir-random

 I am using theme here:
 https://github.com/TechEmpower/FrameworkBenchmarks/blob/b9cc153dcd1c20e78197b0191536f0d11b8ca554/frameworks/D/vibed/source/postgresql.d#L49

 On Sun, Aug 4, 2019 at 12:20 AM Giovanni Di Maria via
 Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:

 Thank you very much to Everybody!!!!!
 Giovanni




You can try http://code.dlang.org/packages/mir-random

I am using theme here:
https://github.com/TechEmpower/FrameworkBenchmarks/blob/b9cc153dcd1c20e78197b0191536f0d11b8ca554/frameworks/D/vibed/source/postgresql.d#L49

And compile it with ldc
Aug 04 2019