Okay then :)

There are many ways to make a Pseudo-Random Number Generator (PRNG). Because truly random numbers are, by definition, without a pattern, any sequence could show up, theoretically. For example, {1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9} could really show up in a random number sequence, just as likely as {9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9}. Because of this, we can't really test randomness. However, what we can test is how chaotic a sequence is. Those two were not at all chaotic, but {2,5,2,1,5,3,8,0,4} is fairly chaotic. This is something that we can mathematically test and that we can use our intuition to judge, too. I am going to describe one fairly common technique and leave it up to the reader to browse the internet for more (Wikipedia is an excellent resource for math and programming).

A Linear Congruential Generator (LCG) is generated by a formula of the form *ax+b* mod *c*→x where a,b, and c are chosen in a specific manner, x is what is known as a seed. In case you are not familiar with the modulo function, it can be thought of as the remainder after a division. For example, **7 mod 3=1** , **24 mod 23=1**, **12 mod 6=0**. There are branches of math such as abstract algebra and group theory that deal with this sort of thing, but programming is where I learned it and where I have learned the neat tricks I know. So now as an example, let's do the function *5x+3* mod *7*→x. We first note that this only generates integers on [0,6]. If we start X at 0:

- 5*0+3 mod 7 = 3
- 5*3+3 mod 7 = 18 mod 7 = 4
- 5*4+3 mod 7 = 23 mod 7 = 2
- 5*2+3 mod 7 = 13 mod 7 = 6
- 5*6+3 mod 7 = 33 mod 7 = 5
- 5*5+3 mod 7 = 28 mod 7 = 0

Now after this, it will repeat the same sequence {3,4,2,6,5,0}. We notice that the only value it never returned was 1. If you seed with 1, it just keeps returning 1. Now let's look at another formula: *6x+2* mod *10*→x. Without running it, we can see that it only returns even integers. Seeding with 0 again:

- 6*0+2 mod 10 = 2
- 6*2+2 mod 10 = 14 mod 10 = 4
- 6*4+2 mod 10 = 26 mod 10 = 6
- 6*6+2 mod 10 = 38 mod 10 = 8
- 6*8+2 mod 10 = 50 mod 10 = 0

So it never reaches the odd integers. In fact, let's start with 1:

- 6*1+2 mod 10 = 8 mod 10 = 8

And so we know it just enters the loop {8,0,2,4,6}. We can see, then, that some numbers provide better results than others. Something that you would learn from Group Theory or Ring Theory is the concept of **Z**_{n}. This is basically a set of integers modulo n where you can perform addition, inverse addition (subtraction) and multiplication, 1 is a multiplicative identity (anything times 1 is itself, just like in typical math on the integers) and 0 is the additive identity. Note that nothing is guaranteed about division. Division is different here. If you perform 2/3 in **Z**_{8}, we basically mean "What value of x satisfies x*3 mod 8 = 2?" We can arrive to 6, since 6*3 mod 8 = 18 mod 8 = 2:

- 2/3 mod 8 = x mod 8
- 2 mod 8 = x*3 mod 8
- 2 mod 8 = 6*3 mod 8

So 2/3=6 in **Z**_{8}. Now here is where it might be interesting— in some of these "Rings" this could have no solution. For example, 3/6 mod 8 has no solution. This is because **Z**_{8} has "Zero divisors". Essentially, 2*4 = 0 mod 8, or 6*4 = 0 mod 8, for example. So because of this, we cannot properly divide in **Z**_{8}. In fact, any time *n* is composite for **Z**_{n}, we get these zero divisors (just multiply the factors of n). If it is prime, there are no zero-divisors and we can actually divide any numbers in **Z**_{p}, (except divide by 0) making it a Field.

This is a pretty complicated subject, but let's make an easy observation:

- 3
^{2} mod 8 = 9 mod 8 = 1
- 3
^{3} mod 8 = 3*3^{2} mod 8 = 3*1 mod 8 = 3
- 3
^{4} mod 8 = 1
- 3
^{5} mod 8 = 3

As we can see, it cycles. This means 3 is a 2-cycle number in **Z**_{8}. Now let's try **Z**_{7}:

- 3
^{2} mod 7 = 3*3 mod 7 = 2
- 3
^{3} mod 7 = 3*2 mod 7 = 6
- 3
^{4} mod 7 = 3*6 mod 7 = 4
- 3
^{5} mod 7 = 3*4 mod 7 = 5
- 3
^{6} mod 7 = 3*5 mod 7 = 1
- 3
^{7} mod 7 = 3*1 mod 7 = 3
- 3
^{8} mod 7 = 3*3 mod 7 = 2

And now it repeats again. Notice that it hits every value (except 0) in **Z**_{7}. 3 is then a generator of **Z**_{7}.

What the calculator does, is it actually generates two LCGs of different period length by subtracting one output from the other. This makes it take a lot longer to repeat. For example, if one LCG had a period of 10 and the other of 6, then their periods coincide at every lcm(10,6)=30 iterations. There are much larger numbers at work for the calculator. Here is one I wrote in assembly, translated to TI-BASIC:

```
; seed1*243+83 mod 65519 -> seed1
; seed2*251+43 mod 65521 -> seed2
; Output (seed1*seed2 mod 16777259) mod 65536
remainder({243,251}LSEED+{83,43},{65519,65521→SEED
remainder(remainder(prod(Ans),16777259),65536
```

It uses a 2-element list named SEED as input, it updates it at every iteration, and it outputs the product of the new seeds, mod a large prime, 16777259, then by 65536 (2

^{16}) since the Z80 is a 16-bit processor and I was working in assembly. It has a pretty big period of over 2 billion (>2 000 000 000).

I'm starting to run out of things to say, but hopefully some of it was interesting. Check out Wikipedia and try to make some of your own!

http://en.wikipedia.org/wiki/Linear_congruential_generator