Friday, October 19, 2007

An Improvement to Random

Recently, I stumbled upon another PRNG (pseudo-random number generator) which had some very unique properties. Not only does the generator score high on tests, but functionally the operations transfer easily into a compact set of instructions - making it very fast. Based on a rather large cellular automata, I didn't think it would be faster than Steven Wolfram's Rule 30 (used in Mathematica for RandomInteger[]); but the byte granularity of the 1D automata reduces to three loads, an add, and a store for each byte. No multiply, division, long dependancy chain, nor multiple passes. Furthermore, if a large random list is updated only when all the values have been used further speed is gained.

I created a macro in MASM to ease direct access to the random array:

    mov ebp, PRNG_CA_Pasqualoni_StateWidth / 4
_0: PRNG_CA_Pasqualoni eax, ebp
; (do somthing with random data)
jXX _0 ; until exit condition reached
Here the random data is stored in EAX, and EBP indexes into the array. If using a register to index into the array seems like a bad idea then try to write a function with less overhead than load/storing a register. The intent is to churn through a massive number of random integers.

The features of MASM have been used to encapsulate the routine within an object module. Although the code is not lengthy it demonstrates coding techniques which make code reusable and easy to understand. The interface is described in a concise way within the include file - there is no need to look at the code to use the functions. Following the defined interface allows the code to operate in a transparent way. Within the assembly file all the nuances are explained making modification in the future less error prone. The file is small enough to fit on a couple screens of text and be quickly comprehended.

(Below is my MASM conversion.)


Rasser said...

Hi bitRAKE

I saw you comment on the Steven Pinker, Robert Wright interview.

And I know you from your posts on Project Euler.

Small digital world.

Glad to see you have started a blog.

I will be sure to follow it!

Rickey Bowers Jr. said...

My 1.6Ghz Dothan does 167 million random 32-bit numbers per second!

Anonymous said...
This comment has been removed by a blog administrator.