The other day, I decided to reverse engineer the TI BASIC pseudo-random number generator. I was curious to see what sort of algorithm it used, and I couldn't find such an analysis elsewhere on the internet. I've read the book TI 99/4A Intern by Heiner Martin (I'd recommend it to any TI enthusiast), and it provides a ton of useful insight into the inner workings of the BASIC ROMs. However, I wanted to reverse engineer the algorithm myself, without the comments from the book.

Below is an explanation of the exact routines:

The GPL RAND command is the core of the TI BASIC PRNG (comments added):

By the above code, you can already see that this is a simple linear congruential generator with a twist. The GPL code above implements the recurrence relation:

Given: a = 0x6fe5, c = 0x7ab9, m = value passed into function (0x64 when called from TI BASIC)

X_n+1 = aX_n + c

and yields an 8-bit integer N by:

N = (X_byte[0] <--> X_byte[1]) mod m

This equates to the following simple C code:

However, there's more to TI BASIC's PRNG than this one simple calculation. The actual BASIC RND function is implemented in GPL as follows: (comments added)

This generates a set of seven 8-bit pseudo-random numbers. These number are all used as part of a larger, 14-precision fixed-point number. However, the PRINT command truncates these 14-precision numbers down to 10 by way of simple rounding. The original representation is only used internally.

When generating the first number, if the GPL RAND function returns zero 63 times, then the number returned is simply zero. This appears to have been written this way to guard against a broken RAND implementation. Back then programmers really knew how to think ahead. :-P

In C, I have crafted an implementation of the above as follows:

This analysis is proven by my implementation as shown below:

tim@tim-laptop:~/code$ gcc -o ti-prng ti-prng.c
tim@tim-laptop:~/code$ ./ti-prng
RAND:
    Iteration: 01, Modulus: 52 (0x34), Seed: 0xe8dc [PASS]
    Iteration: 02, Modulus: 91 (0x5b), Seed: 0x2b85 [PASS]
    Iteration: 03, Modulus: 87 (0x57), Seed: 0x13b2 [PASS]
    Iteration: 04, Modulus: 78 (0x4e), Seed: 0x46f3 [PASS]
    Iteration: 05, Modulus: 23 (0x17), Seed: 0x4f18 [PASS]
    Iteration: 06, Modulus: 07 (0x07), Seed: 0xa331 [PASS]
    Iteration: 07, Modulus: 32 (0x20), Seed: 0xb48e [PASS]

Basic RND():
    Iteration: 01, Number: .5291877823 [PASS]
    Iteration: 02, Number: .3913360723 [PASS]
    Iteration: 03, Number: .5343438556 [PASS]
    Iteration: 04, Number: .3894551053 [PASS]
    Iteration: 05, Number: .2555008073 [PASS]
    Iteration: 06, Number: .5621974824 [PASS]
    Iteration: 07, Number: .2553391677 [PASS]
    Iteration: 08, Number: .5882911741 [PASS]
    Iteration: 09, Number: .7000201301 [PASS]
    Iteration: 10, Number: .0010849577 [PASS]

Note: I didn't cover BASIC's RANDOMIZE, because it's not pertinent to the algorithm itself. When you call RANDOMIZE without arguments in BASIC, the low byte of the seed is set to the last random number generated by RAND.

If you want to see how RANDOMIZE sets the seed, view the code. :-P