Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Siquo]

While on the subject of RNG's (well, slightly), does anyone know of a decent pseudo-RNG that doesn't work with reseeding itself, and the seeding itself is really fast?

So effectively I want this:

Code: [Select]

int randomNumber = RandomGenerator(double x); and preferably I can do even this:

Code: [Select]

int randomNumber = RandomGenerator(double x, double y, double z, double u, double v);(Because yes, I need a 5 dimensional Perlin noise.)
The problem with the Mersenne twister etc. is that the numbers are called in order, and I won't know if the xth number I call is going to be the x+nth time the next time around, and I want a consistent (determined) result. And reseeding them every single time is quite an expensive call.

[Max White]

The problem there is that you need to seed from something. Either the time, user input, or self seeding are the only options within my current understanding.

[Siquo]

The "double" input(s) is/are the seed.
I'm going to go with pre-calculated arrays of random numbers, that's definitely the fastest, I just hope the "periodicity" is large enough.

[Starver]

Keep an eye on whether you want lower<=X<=higher or lower<=X<higher, and what the local rnd() function gives.  (Other combinations possible, but those two are the most common.)

Spoiler: Long and probably incomprehensible treatment of the subject, you can probably skip this (click to show/hide)

Most commonly, you're happy with the double <= result but the return is just <higher, which means for "Random number from 1..10" you'd only be getting 1..9, which might cause you problems if you rely on an occasional 10 popping out.  You could also end up with the opposite, when 10s pop out when you were imagining you'd only get 9 (or, thinking you were correcting for the former, 11s pop out when your desired maximum is 10).

In many ways it depends on how the number is calculated.  Or how you ensure that it is calculated.  If it's essentially a float between 0.0000... and 0.11111... (binary, which might as well be 0.99999.... decimal) multiplied up to the scale that you need and then rounded to the nearest integer then while the top end number (where 1*Max would be Max, but impossible, but never mind because the top end numbers leading up to 0.9999... multiplied by Max would also round to Max) then you'll get a tad few instances of Max than of each of Min..Max-1 (statistically, the PRNG not otherwise being biased).  But if it's a truncated (rounded down) integer conversion then even 0.9999...*Max will end up as Max-1, and you'd never get Max.  (And even if it it was 0..1, a rounded down method would give you increasingly uncommon instances of Max.  1 in N, where N=number if discrete fractionals. rather than 1 in M, where M is actual number of integers in your range, and 1 in M should be the chances of each and every integer popping up.

IYSWIM.

If you can't work out how your system works, do a test on how many numbers pop out for a significant run.  Say 100 random numbers chosen from 1..10 (inclusive) and make sure you had roughly 10 of each, and no zeros (or less) or elevens (or more).  1000 times for 100 each would be better, etc, but it should highlight any under/overruns in either direction.

Then to test your negative range try testing -10..+10 (21 possible results, or -5..+15 if you want to test its asymmetry) across 1000 iterations.  You'd be looking at 47 or 48 results for each, but may vary a few in either direction.

Or even more times, if you're happy to wait the time needed for bigger numbers to be processed.  Or even a "continue forever, while uninterrupted" loop that updates its output accordingly that you can let run while you're not otherwise occupied, leaving it alone or staring at its potentially hypnotic results.  I've done that, before.  Although for different reasons...

Spoiler: And the following looks to be at least sidelong Ninjaed by Siquo and Max, by the looks of it (click to show/hide)

Also, when it comes to PRNGs, most languages have either an automatic PRNG seeding (called prior to first attempt to get a random number) or require you to set up the initial randomisation.  If you're calling it yourself there's generally a choice of giving it your own seed, to get the same sequence out of the function (though, if you start adding in other calls, it'll dislocate calls further down the line) or without you doing that, it'll do what the former (mostly) does and take something likely to be different each time, like system time.

Sometimes you want an essentially identical, albeit nominally unpredictable, stream of randomness.  Sometimes you actually want it to be different each time.  In one project of mine I actually implement multiple instances of PRNG machines so that I can controllably 'farm' identical pseudo-random number streams to give the same procedurally generated world (and that's also what I think DF does, with its various seeds that can be re-entered to regenerate the same geology/history/names, although when you just say "Make a world" the seeds themselves are randomly generated).

So, you might also want to consider which behaviour(s) you want from your system.  Running some simple code twice (at least, but should be enough), that outputs the first ten 'random' numbers and, and getting the same sequence probably means that it's identically seeded each time (although it's possible it is a coincidence, so you could run it a couple more times just to make sure, making the odds against rise tremendously each time).  Or just check the man-pages/documentation, and trust that to tell you how each behaviour is produced.

Anyway, in this deterministic universe of ours, I may have a thinko/typo in the above attempt at an explanation.  I'm sure someone else will be along in a moment to correct me or go "Huh?" about something.

[Shades]

Code: [Select]

int randomNumber = RandomGenerator(double x, double y, double z, double u, double v);(Because yes, I need a 5 dimensional Perlin noise.)
The problem with the Mersenne twister etc. is that the numbers are called in order, and I won't know if the xth number I call is going to be the x+nth time the next time around, and I want a consistent (determined) result. And reseeding them every single time is quite an expensive call.

I'm not sure I understand what your asking for here. A mersenne twister, once initially seeded, will produce the same sequence of numbers. You don't need to reseed between each request. (this is true of most pseudo random generators)

[Max White]

That is the problem, he doesn't want it to produce the same set.
Although I have no idea why that would be significant. What with the sheer number of seeds you could start from, it might as well be truly random. It isn't like anybody is going to sit down and find the logical process behind producing 5d noise for god sake.

[Shades]

That is the problem, he doesn't want it to produce the same set.
Although I have no idea why that would be significant. What with the sheer number of seeds you could start from, it might as well be truly random. It isn't like anybody is going to sit down and find the logical process behind producing 5d noise for god sake.

I want a consistent (determined) result

He wants a consistent result though, you can't have that and have a different set with the same starting seed. (although why you'd use the same starting seed then I don't know)

[Siquo]

Found it: What I need is called a noise function.

@Shades: I'm going to be asking for values at locations, so "give a random value for x=1, y=2.00056, z=0.1111039", and I'll be doing that a few trillion times.

[Starver]

So effectively I want this:

Code: [Select]

int randomNumber = RandomGenerator(double x); and preferably I can do even this:

Code: [Select]

int randomNumber = RandomGenerator(double x, double y, double z, double u, double v);(Because yes, I need a 5 dimensional Perlin noise.)

Right, if I understand correctly (which I might not), how about:

Use standard PRNG mechanism to get a seed number for each 'dimension' and (as I sort of mentioned in the previous message) for which you maintain separate PRNG streams.  That way, each stream is identical in each instance, regardless of which other (or how many other) streams have been tapped.  You can add a sixth call for a sixth dimension's seed and start that stream up without affecting the previous five streams-worth of randomness, and without having to generate a sixth column to a table.

And if you want a random-access randomness stream, the streams could each be a variant of "randomnumber(streamseed,Nthposition" where it calls the first random number from a stream based upon the seed "streamseed+Nthposition", and you can then forget about any further numbers in that stream.  Perhaps worse w.r.t. entropy (I'd be tempted to do something more complex, maybe hash the two values in some way) but, with a decent algorithm behind it, even that simple method won't be easily separated from noise, and yet gives you the same numbers for 1st, 2nd and 3rd position, even if you ask for them in order of 3rd, 2nd and 1st, and interspaced by alternate stream calls.

To that end, maybe your call could be "randomnumber(streamnumber,positionnumber)" and boil down to "seed with(fn(streamnumber,positionnumber)); return firstrandomnumber".  It would save the table, although you might want to statistically analyse an initial run to check there's no obvious problems.  The periodicity should probably be the same as your integrated randomness function, i.e. huge, but that's not guaranteed.


In light of those last two (three) ninjas... Huh?  I thought he did want identical/reproducible sets, just didn't know which separate dimensions would be requested each time, so couldn't be a single reproducible stream.  If not that, then ignore the above.  Probably best in the first place, actually.

[Max White]

Found it: What I need is called a noise function.

@Shades: I'm going to be asking for values at locations, so "give a random value for x=1, y=2.00056, z=0.1111039", and I'll be doing that a few trillion times.

Do tell though... What do you need 5d for? And trillions? Is that hyperbole or is this a result of having that many dimensions to have to transverse?

[Starver]

Well, across five dimensions and 250 points on a 'side' you'd have just less than one 'short' trillion points in total.

4000 points on a side would give 1.024 trillion points in the classic/'long' measure, but much as I prefer that scale I don't think we're talking that one anyway.


Anyway, if you're going "I want a specifically reproducible 'randomness' for point[v, w, x, y, z]", I'm actually now thinking I'd be tempted just to hash the string "v,w,x,y,z" and use that result.  A basic hash (or hash-like formula, involving powers and mods) should do, to make it non-intensive per digit.  And less resource consuming than any table that would not give obvious periodicity (unless you can use a suitably large prime*prime*prime length of table such that it doesn't match any of the prime factors inherent in the array-size, and even then I'd want a few more unique primes to be sure).


But if you've already got a method, wahay!

[MaximumZero]

Found it: What I need is called a noise function.

@Shades: I'm going to be asking for values at locations, so "give a random value for x=1, y=2.00056, z=0.1111039", and I'll be doing that a few trillion times.

Do tell though... What do you need 5d for? And trillions? Is that hyperbole or is this a result of having that many dimensions to have to transverse?

Whatever it is, I hope it's awesome.

[Max White]

Anyway, if you're going "I want a specifically reproducible 'randomness' for point[v, w, x, y, z]", I'm actually now thinking I'd be tempted just to hash the string "v,w,x,y,z" and use that result.  A basic hash (or hash-like formula, involving powers and mods) should do, to make it non-intensive per digit.  And less resource consuming than any table that would not give obvious periodicity (unless you can use a suitably large prime*prime*prime length of table such that it doesn't match any of the prime factors inherent in the array-size, and even then I'd want a few more unique primes to be sure).

That sounds sort of bulky. Assuming you were genning longs, it would be a lot easier to use a standard 5d array. Hashing is fun, but totally not needed in this case when you can fish it out with a simple index.

[Shades]

Anyway, if you're going "I want a specifically reproducible 'randomness' for point[v, w, x, y, z]", I'm actually now thinking I'd be tempted just to hash the string "v,w,x,y,z" and use that result.  A basic hash (or hash-like formula, involving powers and mods) should do, to make it non-intensive per digit.  And less resource consuming than any table that would not give obvious periodicity (unless you can use a suitably large prime*prime*prime length of table such that it doesn't match any of the prime factors inherent in the array-size, and even then I'd want a few more unique primes to be sure).

That sounds sort of bulky. Assuming you were genning longs, it would be a lot easier to use a standard 5d array. Hashing is fun, but totally not needed in this case when you can fish it out with a simple index.

He mentioned noise functions which is exactly what you want for this kind of problem. Simplex noise is cheap for 5 dimensions and would let you pick any point in the 'grid'. Generating arrays or hashing is just over complicating it.

[Max White]

But accessing this data would be fastest if you used your noise function to fill out an array first, unless you need to dynamically get new values.