algorithmrandomcalculatortexas-instrumentsti-basic

TI-84 Plus Random Number Generator Algorithm


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.


Solution

  • 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.

    L'Ecuyer's Algorithm

    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:

    Ti-83 Screenshot

    This matches what my implementation produces

    My computer

    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.