TI-84 Plus Random Number Generator Algorithm

Question

Edit: my main question is that I want to replicate the TI-84 plus RNG algorithm on my computer, so I can write it in a language like Javascript or Lua, to test it faster.

I tried using an emulator, but it turned out to be slower than the calculator.

Just for the people concerned: There is another question like this, but answer to that question just says how to transfer already-generated numbers over to the computer. I don't want this. I already tried something like it, but I had to leave the calculator running all weekend, and it still wasn't done.

Answer 1

The algorithm being used is from the paper Efficient and portable combined random number generators by P. L'Ecuyer.

You can find the paper here and download it for free from here.

The algorithm used by the Ti calculators is on the RHS side of p. 747. I've included a picture.

I've translated this into a C++ program

#include <iostream>
#include <iomanip>
using namespace std;

long s1,s2;

double Uniform(){
  long Z,k;
  k  = s1 / 53668;
  s1 = 40014*(s1-k*53668)-k*12211;
  if(s1<0)
    s1 = s1+2147483563;

  k  = s2/52774;
  s2 = 40692*(s2-k*52774)-k*3791;
  if(s2<0)
    s2 = s2+2147483399;

  Z=s1-s2;
  if(Z<1)
    Z = Z+2147483562;

  return Z*(4.656613e-10);
}

int main(){
  s1 = 12345; //Gotta love these seed values!
  s2 = 67890;
  for(int i=0;i<10;i++)
    cout<<std::setprecision(10)<<Uniform()<<endl;
}

Note that the initial seeds are s1 = 12345 and s2 = 67890.

And got an output from a Ti-83 (sorry, I couldn't find a Ti-84 ROM) emulator:

This matches what my implementation produces

I've just cranked the output precision on my implementation and get the following results:

0.9435973904
0.9083188494
0.1466878273
0.5147019439
0.4058096366
0.7338123019
0.04399198693
0.3393625207

Note that they diverge from Ti's results in the less significant digits. This may be a difference in the way the two processors (Ti's Z80 versus my X86) perform floating point calculations. If so, it will be hard to overcome this issue. Nonetheless, the random numbers will still generate in the same sequence (with the caveat below) since the sequence relies on only integer mathematics, which are exact.

I've also used the long type to store intermediate values. There's some risk that the Ti implementation relies on integer overflow (I didn't read L'Ecuyer's paper too carefully), in which case you would have to adjust to int32_t or a similar type to emulate this behaviour. Assuming, again, that the processors perform similarly.

Edit

This site provides a Ti-Basic implementation of the code as follows:

:2147483563?mod1
:2147483399?mod2
:40014?mult1
:40692?mult2

#The RandSeed Algorithm
:abs(int(n))?n
:If n=0 Then
: 12345?seed1
: 67890?seed2
:Else
: mod(mult1*n,mod1)?seed1
: mod(n,mod2)?seed2
:EndIf

#The rand() Algorithm
:Local result
:mod(seed1*mult1,mod1)?seed1
:mod(seed2*mult2,mod2)?seed2
:(seed1-seed2)/mod1?result
:If result<0
: result+1?result
:Return result

I translated this into C++ for testing:

#include <iostream>
#include <iomanip>
using namespace std;

long mod1  = 2147483563;
long mod2  = 2147483399;
long mult1 = 40014;
long mult2 = 40692;
long seed1,seed2;

void Seed(int n){
  if(n<0) //Perform an abs
    n = -n;
  if(n==0){
    seed1 = 12345; //Gotta love these seed values!
    seed2 = 67890;
  } else {
    seed1 = (mult1*n)%mod1;
    seed2 = n%mod2;
  }
}

double Generate(){
  double result;
  seed1  = (seed1*mult1)%mod1;
  seed2  = (seed2*mult2)%mod2;
  result = (double)(seed1-seed2)/(double)mod1;
  if(result<0)
    result = result+1;
  return result;
}

int main(){
  Seed(0);
  for(int i=0;i<10;i++)
    cout<<setprecision(10)<<Generate()<<endl;
}

This gave the following results:

0.9435974025
0.908318861
0.1466878292
0.5147019502
0.405809642
0.7338123114
0.04399198747
0.3393625248
0.9954663411
0.2003402617

which match those achieved with the implementation based on the original paper.

Answer 2

I implemented rand, randInt, randM and randBin in Python. Thanks Richard for the C code. All implemented commands work as expected. You can also find it in this Gist.

import math


class TIprng(object):
    def __init__(self):       
        self.mod1 = 2147483563
        self.mod2 = 2147483399
        self.mult1 = 40014
        self.mult2 = 40692
        self.seed1 = 12345
        self.seed2 = 67890

    def seed(self, n):
        n = math.fabs(math.floor(n))
        if (n == 0):
            self.seed1 = 12345
            self.seed2 = 67890
        else:
            self.seed1 = (self.mult1 * n) % self.mod1
            self.seed2 = (n)% self.mod2

    def rand(self, times = 0):
        # like TI, this will return a list (array in python) if times == 1,
        # or an integer if times isn't specified
        if not(times):
            self.seed1  = (self.seed1 * self.mult1) % self.mod1
            self.seed2  = (self.seed2 * self.mult2)% self.mod2
            result = (self.seed1 - self.seed2)/self.mod1
            if(result<0):
                result = result+1
            return result
        else:
            return [self.rand() for _ in range(times)]

    def randInt(self, minimum, maximum, times = 0):
        # like TI, this will return a list (array in python) if times == 1,
        # or an integer if times isn't specified
        if not(times):
            if (minimum < maximum):
                return (minimum + math.floor((maximum- minimum + 1) * self.rand()))
            else:
                    return (maximum + math.floor((minimum - maximum + 1) * self.rand()))
        else:
            return [self.randInt(minimum, maximum) for _ in range(times)]

    def randBin(self, numtrials, prob, times = 0):
        if not(times):
            return sum([(self.rand() < prob) for _ in range(numtrials)])
        else:
            return [self.randBin(numtrials, prob) for _ in range(times)]

    def randM(self, rows, columns):
        # this will return an array of arrays
        matrixArr = [[0 for x in range(columns)] for x in range(rows)]
        # we go from bottom to top, from right to left
        for row in reversed(range(rows)):
            for column in reversed(range(columns)):
                matrixArr[row][column] = self.randInt(-9, 9)
        return matrixArr

testPRNG = TIprng()    
testPRNG.seed(0)
print(testPRNG.randInt(0,100))
testPRNG.seed(0)
print(testPRNG.randM(3,4))

Answer 3

The algorithm used by the TI-Basic rand command is L'Ecuyer's algorithm according to TIBasicDev.

rand generates a uniformly-distributed pseudorandom number (this page and others will sometimes drop the pseudo- prefix for simplicity) between 0 and 1. rand(n) generates a list of n uniformly-distributed pseudorandom numbers between 0 and 1. seed?rand seeds (initializes) the built-in pseudorandom number generator. The factory default seed is 0.

L'Ecuyer's algorithm is used by TI calculators to generate pseudorandom numbers.

Unfortunately I have not been able to find any source published by Texas Instruments backing up this claim, so I cannot with certainty that this is the algorthm used. I am also uncertain what exactly is referred to by L'Ecuyer's algorithm.

Answer 4

Here is a C++ program that works:    
#include<cmath>
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{

     double seed1 = 12345;
     double seed2 = 67890;
     double mod1 = 2147483563;
     double mod2 = 2147483399;
     double result;
     for(int i=0; i<10; i++)
     {
         seed1 = seed1*40014-mod1*floor((seed1*40014)/mod1);
         seed2 = seed2*40692-mod2*floor((seed2*40692)/mod2);
         result = (seed1 - seed2)/mod1;
         if(result < 0)
            {result = result + 1;}
         cout<<setprecision(10)<<result<<endl;
  }  
return 0;
}