What do you want to see in a Random Number Generator?

Member
Posts: 64
Joined: 2005.06
Post: #1
After spending two weeks straight trying to write the recognition capabilities of an online text adventure parser*, I've decided to take a several day break and program something else to help clear my mind.

I've ended up deciding on writing a small and simple toolkit framework, as I plan on writing a Cocoa version of my text adventure once the web (ruby) version is done (hah). A lot of easy to use ruby functionality (especially with strings) is lost in Cocoa (it's there, but there is a lot more work to be done to use it) not to mention various other things that I want to be able to have but is somewhat lacking.

For right now though, I'm focusing on only one of these things, and that is of course, random number generation. Sure, there's rand() and even random(), but they are pretty poor all considering. So I've already written an RNG that utilizes the Mersenne Twister algorithm, adapted from the version created by Michael Brundage.

So far I've written the two methods that I personally know I'll use the most, random:(int)max which of course is a random # between 0 and max - 1, and randomWithMax:(int)max min:(int)min which as you can guess, is a random # between min and max - 1.

I want to know what you guys would like to see in a RNG though. Sequential random #s (still mostly random, but each is larger than the last)? I ask because I know I'll most likely eventually need what you guys want. I also know one of the big questions that get asked when people are first starting out, is how to generate random numbers. Well, a good RNG can actually affect the outcome of a game and I get the feeling a lot of people either don't know about or don't bother with using better random generation algorithms.

* For right now, it can understand multiple commands all at once with anything between them (i.e. pick up the lighter and then light that sucker up) or (mix that god awful red potion and that nasty blue potion, and drink that awful concoction); it can even correct for spelling errors (drynk it all down), but it has a serious problem when trying to recognize similar commands with more than one word that defines them (i.e. create character and then select character) will cause lots of problems.

If anyone wants to help, I'd be more than willing to share that bit of code if it'll help get it working correctly (a lot of thought and work has gone into getting it to be able to do what it currently does).

P.S. After wrestling with Ruby (which I'm writing the web version of my text adventure in), I absolutely abhor it. I do however recognize how easy it is to do some seriously powerful stuff, like string handling.


Wow, that was longer than I thought it would be...
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #2
Buy me this and ill do anything you want http://www.araneus.fi/products-alea-eng.html Wink

edit: random permuations of sets are useful

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #3
The PRNG I use has just a few functions: set seed, signed random int, unsigned random int, signed random float (with specified maximum), and unsigned random float (with specified maximum). Pretty clean and simple.

Being able to get the current seed (so that it could be used again later to produce the same sequence of values) may also be useful.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #4
If you have a decent basic PRNG, like mersenne twister, all the rest is just simple arithmetic.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #5
FYI, Ruby uses a Meresene twister algorithm for Kernel::rand().

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #6
we've been through all this before, and what's usually most important is speed. RANROT was found to be the best for being quite random and very vast.

As far as the interface to the PRNG goes, I rarely use anything but a random float between 0 and 1.
Quote this message in a reply
Member
Posts: 64
Joined: 2005.06
Post: #7
Thanks for the replies guys. As I have it set up, when you first initialize the RNG, it is relatively slow, as the MT algorithm uses system rand() to fill the 640 some-odd MT seeds (with srandomdev(4) called once for the master seed, which the documentation said is slow but cryptographic quality).

That said, you only need to initialize it once, and from then on, the MT takes care of everything else on it's own (MT is supposed to be the fastest for the level of randomness it gives you), so there's no reason it shouldn't be pretty quick.

I'm also not against including another faster but less random algorithm for when you need it and/or another algorithm that is slower but even more random than MT. Adapting the algorithms actually isn't hard so including them if you need them is really no problem.

As for functionality, I like the idea of being able to retrieve a seed (in this case, I'd only need to retrieve the master seed produced by random(4)) so that you can replicate results, as well as getting random out of a set.
Quote this message in a reply
Member
Posts: 64
Joined: 2005.06
Post: #8
A quick update; the RNG now had this added functionality:
• You now have a choice between Mersenne Twister and RANROT
• You have the option of returning a float between 0 and 1
• Feed it an Array of any object, and it'll pick a random item in the array and return it.
• You can now set and retrieve a seed value, so values can be reproduced. If you do not set a seed value, a seed is produced using srandomdev(4) which is not reproducible.
• You can now initialize the RNG with a seed value, otherwise just call the standard - (id)init.

Here are some known problems and things I have to add though
• I need to add a signed long method
• Problem: My raw method which returns the unsigned long straight out of the generator, is sometimes negative (only RANROT can produce a negative value so it only affects RANROT). I'm still trying to figure out exactly how an unsigned long has a sign.

Here's a quick list of methods if anyone cares:
Code:
- (id)initWithSeed:(int)seed;

- (unsigned long)mtRand;
- (float)mtRandFloat;
- (int)mtRandWithMax:(int)max;
- (int)mtRandWithMax:(int)max min:(int)min;
- (id)mtRandFromSet:(NSArray *)set;

- (unsigned long)rrRand;
- (float)rrRandFloat;
- (int)rrRandWithMax:(int)max;
- (int)rrRandWithMax:(int)max min:(int)min;
- (id)rrRandFromSet:(NSArray *)set;

- (void)setSeed:(int)seed;
- (int)seed;

If you'll notice, I haven't just created a single set of methods with a "type of generator" argument. I did this to eliminate as much extra "fluff" as possible to try and keep everything as quick as possible. Speed is mainly the reason I've included the "raw" methods, mtRand and rrRand. By the way, would anyone have an idea of how to time the generation of the numbers for different methods? I'd like to see exactly how fast (or slow) it's running.
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #9
I've had a lot of success with filtered random numbers. In essence, you create a random sequence and then filter the results so that they are "fun" inside a game. For instance, remove runs of more than three numbers in a row, three ascending/descending values in a row, values that alternate up/down too many times in a row and so on, the same integer popping up too many times and so on.
Quote this message in a reply
Member
Posts: 370
Joined: 2002.04
Post: #10
As for the unsigned number having a sign, that's probably just in the display - maybe you're using a signed long conversion in NSLog or printf or something?

Did you ever wonder why we had to run for shelter when the promise of a brave new world unfurled beneath the clear blue sky?
Quote this message in a reply
Sage
Posts: 1,232
Joined: 2002.10
Post: #11
Justin Brimm Wrote:That said, you only need to initialize it once
If you are going for repeatable random numbers (i.e. fractal terrain generation LOD) then you have to init it many times per draw.

Games generally don't care about cryptographic quality at all. They just want speed:

Code:
int                randseed, m_lo, m_hi;

// ---------------------------------------------------------------------
// seed RANROT-B PRNG, 32 bits, outperforms random() by more than 10:1
// ---------------------------------------------------------------------
static inline void mysrand(int seed){ randseed = m_lo = seed; m_hi = ~seed; }


// ---------------------------------------------------------------------
// get 32 bits of noise
// ---------------------------------------------------------------------
static inline          int myrand() { m_hi = (m_hi<<16) + (m_hi>>16); m_hi += m_lo; m_lo += m_hi; return m_hi; }


// ---------------------------------------------------------------------
// get random positive float in range
// ---------------------------------------------------------------------
static inline float  frand(float x) { return ((x *(myrand() & INT_MAX)) / (float)INT_MAX); }


// ---------------------------------------------------------------------
// get random float in range
// ---------------------------------------------------------------------
static inline float frand2(float x) { return ((x * myrand()           ) / (float)INT_MAX); }
Quote this message in a reply
Member
Posts: 64
Joined: 2005.06
Post: #12
Alright, another update. I have seeding fully working now. It would still produce random numbers even after reseeding with the same number; turns out I was just forgetting to update a certain variable when seeding. I have added a reseed method as well. Reseed just takes the current seed and plugs it back in, so you can instantly reproduce the random numbers.

Two new features are filtering and buffering. Filtering does by default what Fenris mentioned, but you can change the watched numbers of the different filters (i.e. change the sequentially increasing filter to 15 numbers in a row from 8), and buffering fills a large buffer with random numbers, so when you call up a buffered random, no calculation has to be done, it just gives you a pre-calculated number from the buffer; when the buffer is empty it reverts back to just calculating one by one until you refill the buffer. I'm thinking of making it optional whether the buffer automatically fills itself when empty or if it reverts back to calculating one by one.

The idea behind buffering (let me know if it's useless and if I should just get rid of it) is that if you know you have to do a very large number of random calculations quickly, you just grab them from the buffer and once there is less of a load, you can refill the buffer for the next heavy load. If buffering is indeed useful, please let me know how large of a default buffer you would like to see.

My only problem now is the interface. I've thought about making buffering and filtering simply switches, making all calls filtered or buffered, or vice-versa, but while it has it's benefits, it has it's drawbacks. Another method is creating all combinations of methods in the interface, and again there are drawbacks and benefits. The last method is similar to the previous method, but instead adding an additional method set to the interface for each option, it just adds one extra set with all options as arguments.

This is how I see the benefits and drawbacks to each.

Individual methods
mtRand | filteredMTRand | bufferedMTRand | filteredAndBufferedMTRand

Benefits
• Fastest calls and number generation. No time is spent figuring out if something should be buffered or filtered or both.
• No need to turn filtering or buffering on or off, you simply call the appropriate methods when needed.

Drawbacks
• Most complicated interface
• Higher overhead when loading framework due to complicated interface

Dual methods
mtRand | mtRand filtered: (bool)filtered buffered: (bool)buffered

Benefits
• The original method set (those without the filtered or buffered arguments) doesn't have to calculate if something is filtered or buffered and still calculates as quickly as possible.
• Interface is simplified down to two sets of methods, one without filtering/buffering and one with.

Drawbacks
• Still more complicated interface than the switch method, which means still slightly more overhead.
• You have to specifically state yes or no if you want both buffering and filtering every-time you want either.

Switching methods
turnOnFiltering | turnOffFiltering | turnOnBuffering | turnOffBuffering

Benefits
• Simplest interface with the least amount of overhead when loading.

Drawbacks
• Adds additional "fluff" to other methods, as they now have to calculate whether you want a number that is buffered, filtered or both.
• Can no longer just grab one or two buffered or filtered numbers. You have to specifically turn buffering and filtering on and off every-time you need to change whether the number if buffered or filtered.
Quote this message in a reply
davidpk212
Unregistered
 
Post: #13
What to I want to see in a Random Number Generator?

REAL RANDOM NUMBERS, not the rubbish that comes out of most of them.
Quote this message in a reply
Member
Posts: 64
Joined: 2005.06
Post: #14
Well, time for an update. The framework itself has been done for while now, and I made an examples app that lets you take it for a spin and test out all the functionality. I'm having a problem though that I can't seem to fix and is holding everything up.

I'm having a lot of trouble linking the framework (internally linking within the app) when building a release build. I've followed Apple's instructions to the letter, I've made sure the framework is a release build, I've tried with Zerolink on and off, I've tried everything that is known the cause problems; I've even created a new project and dumped the files in and tried that, but no dice.

The problem is that it can't find the headers contained in the framework, which is odd because at least that much is correct. Both headers (one for the RNG and one central linking header for when additional classes or added in the future) have been set to public and are most definitely included with the framework.
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #15
davidpk212 Wrote:What to I want to see in a Random Number Generator?

REAL RANDOM NUMBERS, not the rubbish that comes out of most of them.

see my previous post
unknown Wrote:http://www.araneus.fi/products-alea-eng.html

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Wave generator problems... Nevada 3 2,473 May 2, 2007 04:04 PM
Last Post: Jake
  How to create a Random Map Generator Psyjax 9 11,493 Jan 17, 2007 09:07 AM
Last Post: davidpk212
  Can't use NSString to put a number on screen? kensuguro 3 5,012 Nov 7, 2005 01:16 AM
Last Post: Jordan
  Getting Number From Character In NSString Nick 2 4,499 Oct 31, 2005 10:08 AM
Last Post: Nick
  Even Number of Triangles for Any 3D model unknown 1 2,836 Sep 21, 2005 08:34 AM
Last Post: Zekaric