This topic may need moving to expert, but in essence it's still a question so I'll start off here.

If you're not sure what this topic is about, read a little side information here. If you're still not sure what this is about, then I suggest not reading onward.

For a particular project I need a Pseudo Random Number Generator (PRNG). Mark is not going to include a random seed for the random function in Game Maker, so I need to design one myself.

I've been looking around a bit on the Internet for a relatively simple formula that nevertheless has a reasonably good distribution. This is a pretty popular one, and easy to implement:



In this case, x1 is the new random value, and x0 is the old random value. I found information on this page, including the standard values VB uses for a, c and the standard seed. While there are of course better formulae around, this one suffices for my needs. Besides, being implemented in Game Maker script, the simpler the better if you need to call it often.

So, using the suggested values for a and c, I've written the following functions. One called rnd_seed, reading this:



This sets the seed, necessary before calling the function rnd_get:



The first line calls the formula with the parameters as currently used by visual basic - the second line returns the result divided by 16777216. This should always result in a value between 0 and 1, the latter exclusive. Note that the last division is not applied to global.rnd itself - it would mess up the seed for the next call of the function.

Here's a test script that draws 10000 numbers of 0 through 9, and counts them in an array, using VB's original seed:



When displaying the results of the array res, I would expect that each number is drawn around 1000 times.

I get these results:

0:5000
1:0
2:0
3:0
4:0
5:0
6:0
7:5000
8:0
9:0

Of course, the floor() command may cause some bias towards a particular value, but this is ridiculous. I hand-calculated a few random values, and then the results come out as you would expect them.

Now, it says this on the GM To Do list:



But I didn't think the numbers would become high enough to influence the formula (seeing the mod division brings it down every time). It seems that especially the multiplication in the formula above doesn't give Game Maker the correct answer.

Now, it turns out you need about 4 or 5 digits less for a to prevent Game Maker running around in the circles above. But my knowledge of random numbers ends here - I don't know what the 'best other' numbers are for a and c. What I've tried turns up with horribly bad distribution.

If anyone can think of good values, or can suggest another simply-to-implement PRNG (haven't found good alternatives yet), I'd be happy to hear.

Smarty

http://gm.big-brain.org/item.php?id=5 ?

- Put this at the end of your post if you want a rule against inline signatures.

This is the one I made, but I've never actually tested it statistically:where:
I based that off of an algorithm I found in a Don Knuth book I believe. Now that I look at it, it looks like it might have some precision problems with GM6. I've only used it in GM5 and it seems to work.

tsg1zzn, I've never seen Eric's script before, but it uses the same formula as I do - except that it indeed uses smaller numbers for a and the modulus divider (c is not used). These default values have a good distribution for a 0-9 range of numbers, but with 100,000 tries in the 0-99 range, there are loads of gaps with numbers having not a single hit at all. It's strange that it can't even hit more than just about 10-15 numbers.

Xot, with the same test your number generator seems to have a better distribution. At 100,000 tries, the hits for certain numbers in the 0-99 range vary between 500 and 1500. It doesn't visibly suffer too much from the precision problem. It's not perfect, but at least more workeable than the formula described above. Wondering if tweaking the parameters might improve it a bit.

Thanks for the suggestions so far,

Smarty

I guess I would first try reducing "global.cryptM=100000000;" by a factor of 10. That might improve precision since 100,000,000 is actually bigger than GM6 can reliably use, but 10,000,000 should be fine (?? maybe ??). You might have to reduce M by factor of 100 and M1 by factor of 10. Not really sure how the algorithm works.

Well obviously it will miss certain numbers if you input large values for A and C; just look at the formula. There is no division, so the bigger whole numbers you put into it, the bigger the results will be, and the bigger a gap will be in between them. My suggestion is to use very small numbers (decimal numbers) and/or fractions. Graph the equation with a (non-random) sequence of numbers and you will see what I mean.

I came across the same problem with the same formula. My quick-fix was:
a = 43234
c = 6323
newx = ( oldx * a + c ) mod 255

It produces the following distribution with floor function at 10,000 trials:
0: 1043
1: 625
2: 1249
3: 1040
4: 832
5: 833
6: 1250
7: 1041
8: 835
9: 1252

Which still looks worse than Xot's algorithm from what you said. It'll be interesting to see a clean solution, I need one also.

Look up info on lagged fibonacci generators. They're supposed to be pretty good and pretty fast.

A standard congruental equation would be like this:


("N" being the random number and "i" being the seed)

It is rather complex trying to come up with alternative values for a and b (assuming the format (a * n[i-1] + mod c). C is just a 2^x value which makes it such that the function has a range of 0 and (c-1). The smaller the values of A and B, the more limited the randomness of the parent function is. IE Christopher Tremblay recommends the values a=49948198753856273, b=7478206353254095475. If you're really interested in testing your own values, I recommend his book "Mathematics for Game Developers".

There are of course other methods to pseudo-random functions (check out Fibonacci!).

The alternative is to not use the GM data handling functions at all and instead use your own. This would take some work and of course it would be slow because it would require that you check and execute execute lots of conditional statements which are normally done on a higher level. I would write the code but I don't feel I really understandard the problem. If you could test this a little more and explain it it would help.

I do think this should go to the experts forum, as it involves a high level of mathematics and your dilema has no simple solution.



EDIT:


A Fibonacci generator wouldn't be as fast as the congruential method.

The problem is those values are much, much greater than GM can use accurately, so any math done with them will be suspect. In fact, neither of those numbers can be represented at all in GM. A DLL might solve that problem, but I'm not sure how much the overhead from calling a DLL would slow down the game. I guess it depends on how often you need to call it. And if a DLL was used, then it would make sense just to use C's built in random functions rather than write a new routine.

Running the same test, your first suggestion gives the 0-99 range hits of either around 0, around 1000 or around 2000. The second has comparable outcome. So far, the initial values you suggested score best.

Pyroguy, the mod operator does exactly that - a mod b returns a value that is at highest b-1. So the numbers can never grow 'too big'. To get a value between 0 and 1, all you have to do then is divide by the same value b.

Geargod, I haven't mentioned this, but ultimately I would like to draw numbers a little bit bigger than 100. The downside of your quickfix is that the mod division is only 255 which only returns 255 unique possible results from the equation. This means that if you try to create random numbers bigger than 254, you will never get some numbers of the range. All values for a, c and m for this PRNG suffer from that, but in essence, the more unique numbers you need, the higher the mod division should be.

Diveloperz, As Xot points out, GM has a problem with these high values - even the standard one you gave (gives me a distribution as mentioned in the first post). I'd also say that 32768 unique random values may not suit all games. Designing my own data handling routines would cause a lot of unwanted overhead, there must be some other solution. I'll look into Fibonacci PRNGs first.

If you're not sure what the problem is, try this (numbers taken from your post):



Check the result with the original number: off by 1. Now try this:



Off by a lot. And it isn't the string function that is responsible for this - try integer division of any of those numbers by e.g. 10^16 before displaying them, then compare that value with what a calculator gives you.

You'd actually expect that this deviation doesn't hurt the PRNG that much - but the mod division often seems to give a result of 0 on such numbers, which explains the sequence I got in my first post.

Xot, in the past I have actually created a DLL in Delphi which used Delphi's PRNG - for a project that needed anywhere between 0 and 150 random number calls per step, because I considered that calling a DLL would by far be faster than a PRNG in engined GML, even given the DLL call overhead. It's not difficult to do, however an 'in-house' solution seemed so much more elegant.

Right now it looks like I'll need a DLL anyway for just that, or agree with the slightly wonky PRNG you provided.

Smarty

Edit: indeed, time to move the topic.

This topic got me thinking about how to determine how good a random-number generator really is. My first thought was to do the same things that've been discussed here: Look to see how they populate an interval (like 1 to 100 for example).

But I discovered if you look more closely you see hidden patterns and repetition (NOT good). So I wrote a little app to check this.

I apply two tests: I plot adjacent pairs of points on an XY (100 by 100) grid to reveal any hidden patterns, and to see how well it fills the space. I also plot the "binned" values in bins between 0 and 100 see how it fills.

Of course, the average and RMS values are useful too. Here are some examples (all for 10,000 samples):

GM's Built-in Random Generator:


GM built-in generator looks great. No repetition and it fills the space very uniformly with no obvious patterns.

GearGOD's example above:


The behavior in GearGOD's example is common I think. I checked some similar generators from the net and they did similar things. The average and RMS are OK, but there's lots of repetition (hence and the pattern in the XY gird). And it misses LOTS of numbers in the interval, as Pyroguy pointed out.

Here's one that I made up:



Surprisingly, I get pretty good performance from my simple-minded approach. Just need a suitable seed value (I used 0.7 for the case I showed). Wouldn't have thought this would work quite so well.

But I'll keep working with the basic forms:
approach... to see what I can come up with.

Very interesting tests, KL LC. What you've shown with GearGod's function is suprising and illuminating. I still don't quite get what you're doing with XY plot, but it looks like a great test.

KC LC, the tests you did were rather limited. Of course anything that looks like a linear random function can be used for most pseudo-random purposes, but if you want to search for patterns you will need to look at the random distribution with greater dimentions. I could hook you up with some programs but that would mean vilating the distribution agreement....

You're right, I only showed a couple of examples. I'm working on a more complex pattern detector using POV-Ray for displaying things.

But just so there's no confusion: my goal is not to find patterns... I'm trying to avoid them. Just using the pairs-plot to check for obvious problems.

It's nothing more than forming XY pairs from adjacent members of the random sequence, and then making a cartesian plot (properly scaled of course).

Like Diveloperz said, there are more complex tests. Mine is simple and quick. But if the generator fails this test... no point looking deeper, right?

I starting doing this after making a surface from a random-generator I got off the web. I noticed "ridges" that shouldn't be there. The generator was this one:


It generates the right average, the right RMS, and the binned values look OK. Everything's fine, right? No! Look at the pattern in the XY-plot test (you can see the remains of the natural log function):



The question is, "Does this really matter?" Maybe not. You could still use this to generate sequences that look quite random. It's just the principle of the thing...random should mean random. Like the GM built-in generator.

Try looking (thereto avoiding) at a random function in 3D. But yeah, I see what you mean. If you're only using a pseudo-random function for AI direction of acceleration, then you only need to test it in one dimention, and if it looks perfectly random on that level, it's fine for your purposes.

Kasey, what I'm most surprised with is that you have 'just' come up with an alternative PRNG that seems to works fine for me, and is likely decent enough for the common game. At least, you make it look good in your tests.

As you pointed out, GM's random number routine looks fine. Since Game Maker was written in Delphi, I wouldn't be surprised if Mark used Delphi's default PRNG. According to this text (couldn't find any more authorative information on it) it's written in assemby, so it's fast. That's essential for an engine like Game Maker's.

But for our purpose - games - the linear congruential method for PRNG as it was used by me, GearGOD and EricDB should be fine - provided we have workable parameters in Game Maker. After all Microsoft uses it for it's RND function in it's development platform Visual Basic.

But we've seen that specific seeds, or it's parameters, might cause this PRNG to run into GMs accuracy problem, making it cough up (rounded? floored?) numbers that bias the outcome towards particular numbers. My first post was an extreme example of that, only using the MS's suggested parameters for the linear congruential method. 'Good' parameters for the linear congruential method may be found on the Internet, so 'all' we need to do is find out which work well for Game Maker.

Problem is that the vaster the result of the method, the higher the parameters will be - and the higher the parameters, the more a chance to run into the accuracy issue. Maybe we do need a different PRNG.

Smarty

Again, I tell you, the plausible alternative is to work around GM's real data accuracy issue by not using GM functions at all until the data is in a form that GM can handle. You could store the mishandled data in strings instead of as reals, then pass them to a function which does the multiplication based on the numeric character values in that string, then pass the returned string into a similar function for finding the mod given two numberic character strings.

Of course this would be slow, but maybe not unreasonably so. It adds a lot of unneeded code, but not an unreasonable ammount. And of course the code would just be a series of conditional statements with a few string handling functions. If you call the pseudo-random function a hundred times per step it may alter the game's constant FPS, but I don't think it would be unreasonable to use for just like a hundred calls per second (a few per step). Maybe the runner could handle several hundred per step; I'd have to test it. Of course the length of the values being used in the pseudo-random function would affect the speed at which the random function is executed.

The other alternative of course is to pass the data to a DLL, but this may not be the most preferable as you (Smarty) mentioned.

I can write the scripts if there's any interest.

Diveloperz

Speed of course is all dependent of the system. But it doesn't matter. Although juggling with numbers in that way is of course conceiveable, I'd much rather go for a slightly less trustworthy PRNG - performance over accuracy, so to say. Seeing that events triggered by players may request new random values, two games are unlikely to end up the same.


Thank you, but not for me. Not sure if anyone else is interested.

Ideally, I would prefer any of the following:

• PRNGs are included in Game Maker through functions (but I've asked Mark twice, and he has refused twice). I think they are a requirement for a game engine.
• Mark fixes the bad GM accuracy somehow (not too hopeful there since he doesn't seem to know where it came from)

For now, Kasey's home-brew PRNG is the most convenient alternative. As a last option I'll resort to a DLL, but preferably not. I still have some hopes for the linear congruential method.

Smarty

Of course, that's the real problem. Please forgive the horrible pun. I hope he figures out the problem.

I agree, they are a necessity, especially for multi-player games.

It's actually to the point. You see, I'm worse.


That's what I first wanted to state, but then I thought, even in single player games it would be great if you can save an entire level by just saving a few seeds.

Perhaps we should shift our attention from finding the right PRNG towards defining what the current limits of GM's 'real' numbers are. Any programming language has a limit to it's reals. If we know where GM's accuracy issues start, we can work around them too.

Of course, really convenient would be when GM generated an error when hitting the limits. But where compiled applications just hit an overflow and crash immediately, engines would have to check the limits themselves - something that may seriously slow down the execution speed of the engine.

Smarty

People who say this accuracy problem is only imaginary are just being irrational. I believe it's a complex problem that will take a rational approach to solve it. Fixing this should be Mark's prime goal.

OK, somebody STOP me please!

...back on topic...
True for some games, but not for others. For example, a puzzle game that uses random numbers to scramble letters, or to hide things behind doors, etc. won't have much re-play value if the setup is always the same each time.

"Hard coding" the seed into the game won't help, of course. What I do sometimes is to pick a seed based on the computer's internal time. Less likely to get repetitive outcomes that way.

I agree. I went through this for a GM app I wrote to calculate Mandelbrot sets. As I zoom into the set I eventually start seeing pixelized images because GM can no longer differentiate between adjacent points in the set. (Thanks to Yourself for figuring out what was going on.)

Granted, granted, you win... Stop pulling your hair out by the root.


Of course the setups may be the same. What I meant is that the player should triggers random events in different parts of the game. While the RND sequence is the same, they are applied to elements of the game that the player decides. Therefore, the outcome is much more unpredictable. Puzzle games do not fall into that category, usually.

Delphi's RND seed limit is 2^32. So even with GMs built-in functions, there are no more than 2^32 different set-ups - the seed limit defines this. Every programming language uses a PRNG, and they all have a max seed. Consider a game like MineSweeper - there is a likely chance that the game you play has already been played by someone else.


That's exactly how the Delphi Randomize function works, which is used to seed the Random function: the internal time is converted to a seed. Since Game Maker produces different random sequences each call, and since it likely uses the Delphi PRNG, you might as well initiate your PRNG with Game Maker's random function... Unless it needs a higher seed, of course.

Smarty

I searched the forums a while ago and saw someone did a seedable random script...I got it but never really tested it...it also gives biased numbers...

Going to test KC LC's method now...

This is really important...you could also do replays of games with just saved user input and a random seed for example

edit:

KC LC's sin method works very well with small numbers as seed. Though it'll get more and more biased with larger seeds. Or very small...but it's good enough for me. At least for now.

I'm going to be working on a solution today. I came across the Ranlux algorithm last night after spending some time searching for something designed for older computers with more limited precision. It produces random numbers with 24-bit precision which should be a perfect fit for GM6's 24-bit mantissa. Unfortunately the original version is written in Fortran, a language I don't know. I've found some other Ranlux variants in other languages that will hopefully come in handy in reproducing this in GML. I'll keep you posted.

For the curious:

EDIT: Actually, I've got too much other stuff to do right now, this is getting shifted to low priority.

This is exactly why I started playing with my own PRNG's. I want to be able to shuffle a puzzle in random ways each time the game is played, but ALSO be able to easily repeat that sequence for the same input seed.

True. I should have mentioned this. Best to keep the seed under 10 or so, otherwise the 0-1 interval filling gets a little "grainy". Of course, the seed needn't be an integer, so this isn't too much of a restriction.

You're all crazy.

Well, my PRNG used to work great, but the precision problem that was introduced some time back totally wrecked it. I'm going to create a 20-bit (as opposed to 32-bit) implementation. KCLC, could you post a link to the program you used (wrote?) to test the various generators?

Edit:
One type of PRNG is the LCG (linear congruential generator). Most built-in PRNGs are of this type. They work on this formula:

next_num = (a * previous_num + c) mod m

Since the next number only depends on the previous number, plus some constants, we can see that it's equivalent to having a very long list of "random" numbers, and simply giving out the next number in the list when asked. When we run out of numbers, we start over at the beginning. So, what makes a good list?

1) It should be long.
2) It should contain an even distribution of numbers.
3) The numbers shouldn't be in any obvious order.

Since the previous result is the only variable (i.e. not constant) in the calculation, and the result of the calculation is taken "mod m", we know that there are only m possible states for the generator to be in. So a large value for m equals a long list. It's also desirable that every result from [0..m-1] is used (rather than have some numbers represented more than once, and other numbers missing entirely). This can be guaranteed by choosing a, c, and m according to these constraints:

1) a-1 must be a multiple of p, for every prime p dividing m. (this is trivial if you use a power of 2 for m, since you need only check that a is odd)
2) a-1 must be a multiple of 4, if m is a multiple of 4.
3) c must be relatively prime to m. (share no common prime factors)
4) c shound be chosen as close as possible to m * (0.5 +/- sqrt(3)/6)

Since GM loses integer precision around 2^24, I added a constraint of my own to the list:
5) a * m + c must be less than 2^24.

I came up with:
a = 125
m = 131072
c = 27699

a * m + c = 16,411,699
2 ^ 24 = 16,777,216

The period of this LCG is only 131,072 (meaning that the 131,073rd random number will be the same as the first, and the sequence will repeat indefinitely) whereas a "real" 32-bit LCG would have a period of 2^32, or 4,294,967,296. However, it exhibits good behavior: every possible result from 0 to 131071 is equally represented.

Here's the code for my new "24-bit" LCRNG:



And here's a screenshot from a quick program I wrote to check it against GM's built-in PRNG. Random numbers between 1 and 200 are generated and used to plot points on the 200x200 white squares. The graphs show how many of each number (1-200) have been generated, relative to the expected number.

Mine is on top, GM's is on bottom.



KCLC's generator using sin() starts out looking great, but after a while it develops problems: some numbers are over- or underrepresented:

I just thought I'd add my 2 cents...

That's actually true, noticed it as well while I was testing it. Though, you really need quite a lot of random number calls...Ten thousand, and you won't notice it yet. A hundred thousand and it still shouldn't be a problem if the seed is good. More...well, not that I need more, but it might be a problem.

EricDB, very nice call on finding acceptable parameters for the linear congruential method (admittedly, I didn't quite follow constraints 2-4, but I'll take your word for it).

I wonder if 2^24 really is GM's real limit though. Because there is one downside - as you correctly point out, the interval size is also the number of states of the generator, so in this case, the seed limit. I don't want to be picky, but I consider 131,072 (2^17) seeds - or rather, entry points into a random sequence - not very high. If GM's real limit is higher, constraint 5 can be loosened.

Of course, this could also be solved if the LCG's parameters could be randomised as well, taking the constraints into consideration. A little bit trickier to conceive, of course.

ArchMageOmega, that looks like the implementation of a lagged Fibonacci generator.

Your test method doesn't seem entirely honest, however. There are three tests running simultaneously, all pulling numbers from the same generator. So none of the three tests pull numbers from it in sequence (well, unless you call every 4th number a sequence, and sometimes a 5th when a random value is pulled out by the RNG object every 60 steps, but it does obscure the result a bit).

Other than that, the results look OK. Even though the input seed parameters are of the range 0-65535, there are 10, making the seed pretty large. Well, of course the seed is pulled from GM's PRNG so theoretically there is still one seed. On the downside it's definitely slower than the LCG of course, and there are more parameters to pass.

Anyone else catch a flaw?

Smarty

Yeah, 2^24 (which is 16777216) is the limit. Fire up any game in debug mode, go to the debug window, and enter these expressions:

16777215 + 1 (GM returns 16777216 - correct)
16777215 + 2 (GM returns 16777218 - oops!)
16777216 + 1 (GM returns 16777216 - oops!)

You're right, that a period of 2^17 isn't ideal. It's utterly unsuitable for any cryptographic purpose beyond hiding things from casual inspection. However, in the context of a game, I think it will be acceptable. The numbers are equally represented (which is true of any LCG) and the order "looks" random.

My original PRNG library had support for multiple streams. I'll update it to support the new 24-bit routines. If 2^17 isn't enough, you could always interleave two or more streams.

But if you try 1.5*16777216 - it comes up with the correct value (25165824). And this got me experimenting a bit. It seems that

For every value for n of 23 and over, the lowest value with which you can change x, where x>=2^(n-1) and x<2^n, is 2^(n-23).

So from 2^23 to 2^24-1 (8388608-16777215), this delta value is at lowest 1.
From 2^24 to 2^25-1 (16777216-33554431), this is 2.
From 2^25 to 2^26-1 (33554432-67108863), this is 4.
Et cetera...

For example, 16777216+1 doesn't work, but 16777216+2 returns a correct value.
33554432+2 doesn't work, but 33554432+4 returns a correct value.

GMs precision problem also affects decimal values, but the lowest delta value is harder to pin down there. From 2^23, decimal values cannot be used properly anymore.

Consider this:

8388608.5+0.5 results in 8388608
8388608.5+0.6 results in 8388609. Oh, so it's rounded above 0.5? No, because
8388608.6+0.5 results in 8388610!

Going back to 2^22, try displaying this value in the debugger: 4194304.5

Ouch, ouch, ouch. Rather disappointing, this is.


Even though this PRNG is a blasphemy compared to the original. Edit: sorry, that came out a little bit rude - I meant a shadow.

Well, at least there are two solutions right now. The lagged Fibonacci appears to have a better distribution, but then again it's using 10 seeds - not particularly a fair comparison. Multiple streams of the LCG I can implement easily myself.

Cheers,

Smarty

I tinkered with it a little more, and found a method that gives excellent results. I use ten independent streams. Each time a random number is requested, the previous random number, mod 10, is used to determine which of the ten streams the next number comes from. It's almost as fast as a "pure" LCRNG, but it works a lot better (considering the 24-bit constraints we have to work with).

Initiated with 10 seeds then, I assume?

Good thinking though. Would even still be faster than the LFG, which has to shift the list of previous results at each random call (of course a queue could have aided there a bit, but still).

Two reasonable solutions, for now. Almost makes me stop worrying about the bad precision.

Smarty

Bad precision? Bigint by Rithiur allows you to manipulate big numbers. Import the library, and run this test in the room creation event:



Impressive and very useful. Here's a quick app. I wrote from Smarty's code in his first post. The division was left aside.



It would be nice to see the differences between the version without BigInt, and the version using the lib.

It is an LFG. Also, it really should have each test in a different room or at least with switches to let only one run at once. (Neither would be hard to do.) Every 4th number is a valid test, but testing every number is more important. As for the seed, well, I don't really have a sufficient source of entropy to generate 10 seeds.

The discussion about the lack of precision leads me to believe that GM uses 32-bit floating point numbers to store everything. A 23-8 (1 bit for sign) floating point number can represent anything to 23 bits of precision but can represent numbers much bigger than that. (Up to 1.11111111111111111111111 * 2^127 [in binary] or so.) If that's true, there's no way to get around it without using some other form of number. (Which means that a better RNG isn't going to help much.) It might be possible for a future version of GM to use doubles instead. They can handle numbers up to 53 bits of precision and I think most modern computers can handle them fairly well.

I could increase the number of streams to sixteen, and then use a 32-bit integer as the seed. The streams could be seeded this way:

Stream 0: bits 0-16 (Each stream uses a 17-bit seed)
Stream 1: bits 1-17
Stream 2: bits 2-18
....
Stream 15: bits 15-31

It wouldn't utilize the entire seed range, which would be 17*8 = 136 bits, but it would be more convenient for the user. Of course, I could provide another function to allow each stream to be individually seeded.

I think I can write this to be very close in performance to the "plain vanilla" LCG. Results to follow.

Edit: Crap, I just realized that 32-bit integers don't exist anymore...hence the entire reason for this exercise. Hmm...I'll come up with something that's easy and good...I don't know what it is yet, though.

That is essentially correct. As has been mentioned ad nauseum GM6 has a 24-bit mantissa. GM5 has a 53-bit mantissa. Something strange happened in the update and Mark Overmars hasn't been able to fix it. Hopefully we'll get our doubles back someday.

Okay, here's my perfected 24-bit PRNG!

The seed function (call it with an integer for the seed):

And the random function (call it with a range, just like GM's built-in random() function):

It's quite fast, and very random. Although it only has 131072 possible return values, its period is very much longer than that, since there are 16 separate streams, which are accessed at random (according to the last four bits of the previously generated value).

Edit: I noticed that values were being pulled from each stream at exactly the same rate...so that the period was only multiplied by 16...in other words, when stream 0 had been accessed 131072 times, so had streams 1-15, and we were right back where we started.

So I added the line right before the "return" line, to mix things up a bit. That did the trick. I ran the output through the DIEHARD battery of tests, and it passed every single test, except for one having to do with recurrences at particular bit positions. It's a minor problem, though, or it would have thrown off some of the other test results as well. I think it'll be more than good enough for any game you'd care to write. And it's still fast.

Yes, such a thing has been suggested by Diveloperz above, but as Rithiur also points out in mentioned thread, it can be rather slow. If you're doing several random number pulls per step, I'm sure you'll notice the frame rate drop on slower systems.


In Delphi, the related type is called Single - on some page I unfortunately lost track of it was mentioned to use one digit for the sign, 8 digits for the exponent, and 23 for the significant digits - 24 when the exponent is zero (this could explain why there are already accuracy problems om the first decimal between 2^23 and 2^24).


Wouldn't you pay some price in performance? We did that already in GM 5, of course.


"Mark, change double back into single in your type declaration". Can't imagine he missed that, however. And I would expect the runner to crash on overflowing the single (as compiled applications usually do).

Datetime functions are probably suffering from being treated as singles as well (boy, that came out strange). Delphi itself declares them as doubles.


Hah, using the result to indicate the next stream to pull a number from, ingenious. This should indeed be sufficiently random. Thanks a lot for your efforts!

Smarty

I believe I've found a perfect distribution prng function. The thing is it only works in C++ because variables will wrap around if they are too big or too small hears the code

it has one possible number to return for every possible seed which can be anything from 0 - 4294967295

the only problem is it will return 0 on a seed of 0 and 2147483648 on a seed of 214783648.

EDIT: I found a way to solve this just return 2147483648 if it's 0 and vicse versa