Thread overview | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
August 03, 2019 Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
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 |
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to Giovanni Di Maria | 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.
|
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to Cym13 | 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
|
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to Giovanni Di Maria | 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.
|
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to lithium iodate | 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
|
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to Giovanni Di Maria | 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 |
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to Giovanni Di Maria | 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);
}
}
|
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to Giovanni Di Maria | 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. |
August 03, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to matheus | Thank you very much to Everybody!!!!! Giovanni |
August 04, 2019 Re: Speed of Random Numbers | ||||
---|---|---|---|---|
| ||||
Posted in reply to Giovanni Di Maria | 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 > |
Copyright © 1999-2021 by the D Language Foundation