Ever heard the saying that an infinite number monkeys with an infinite number of type writers could write the works of Shakespeare?

Well I'm in the process of testing this theorey out. It's just a silly program but I'm learning from it all the same. The user inputs a word, and then the program starts generating random words of the same length until it finds a word that matches.

The problem I'm having though is that the same sets of words keep on being repeated. I think this is because the seed of the random number generator I'm using sometimes repeats itself. This means that the program never generates certain words and it just sits there forever. The seed loops about every 40000 times a random number is generated, so somehow I need to 'randomly' change this seed every 40000 iterations.

Since the word generating process can take a long time, I am excecuting it in a new thread. I also have a timer setup which fires every 50ms to update the screen. In the timer event I have the following code:

invoke GetTickCount ;create a random seed
mov seed,eax

Is this the best way to create a random seed? Another way, which I imagine is quicker I thought could be this:

xor seed,61842

IE, simply xor the number with some random constant.

While these two methods work when the code is placed in the timer event, they only excecute every 50ms and by that time the seed has probably looped round about 125000 times which is obviously quite a lot of wasted cycles.

Another thing I thought of would be use the first method within the main processing loop itself. But then, because GetTickCount has a resolution of about 15ms, it would constantly set the seed to the same value.

Basically, what is the fastest, most cycle saving way of doing this?

Posted on 2004-09-14 11:17:05 by DeX

Take a look at http://www.masmforum.com/viewtopic.php?t=4031&start=0
Posted on 2004-09-14 11:39:34 by roticv
Ok, so should I use rdtsc? It appears to have a much higher resolution than GetTickCount, so this is what my code looks like now:

mov eax,numTries
shr eax,14
shl eax,14
.if eax==numTries
mov seed,eax

This excecutes after each word has been created. numTries holds the number of words that have been generated so far. This code alters the seed every 16384 loops. Do you think this is a good method?
Posted on 2004-09-14 12:02:11 by DeX
Ok, so should I use rdtsc? It appears to have a much

imho you should use it together with a fast prng (pseudo-random number generator) with a large period, like the Mersenne Twister: http://www.math.keio.ac.jp/~matumoto/emt.html

by the way, your experiment is already running somewhere on the web, i stumbled once upon it, but i can't remember where.

(offtopic: is it stumble on, or stumble upon, or...? and why? thanks.)

edit: google told me: http://user.tninet.se/~ecf599g/aardasnails/java/Monkey/webpages/
Posted on 2004-09-14 12:22:36 by lifewire
(offtopic: is it stumble on, or stumble upon, or...? and why? thanks.)

I think it's upon in this case. On gives more of a litterally stumbling over your shoelaces image... :wink:

Anyway, at the moment, I'm using NaN/bitRAKE's nrand algorithm from masm32lib and i'm using the low dword of rdtsc as the seed as shown above. This probably still isn't as random as it could be but it's ok for now. I will have a look at implementing the Mersenne Twister algorithm later.

But now another thing is bothering me. In that link you gave, the Java program seems to generate around 10^30 pages of random text per second. I find this pretty unbelievable to be honest. My monkeys can sometimes match my 6 letter word, but certainly not 17 letters as the Java program does. Also the Java monkeys have the whole ascii alphabet to play with whereas mine only uses lower case a-z. On average my program will generate and compare about 2.5 million words per second but this is miles away from 10^30. How can that Java applet manage to so much?
Posted on 2004-09-14 13:52:40 by DeX