# Reverse Engineering the TI BASIC PRNG

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