TI-84 Plus Algoritmo generatore di numeri casuali

Question

Modifica: la mia domanda principale è che voglio replicare l'algoritmo TI-84 plus RNG sul mio computer, così posso scrivere in un linguaggio come Javascript o Lua, per testare è più veloce.

Ho provato a utilizzare un emulatore, ma si è rivelato più lento della calcolatrice.

Solo per le persone interessate: C'è un altro question come questo, ma risposta a questa domanda dice solo come trasferire i numeri già generati verso il computer. Non voglio questo. Ho già provato qualcosa del genere, ma ho dovuto lasciare la calcolatrice in esecuzione tutto il fine settimana, e ancora non è stato fatto.

Answer 1

L'algoritmo utilizzato proviene dalla carta Generatori di numeri casuali combinati efficienti e portatili di P. L'Ecuyer.

È possibile trovare la carta here e scaricarla gratuitamente da here.

L'algoritmo utilizzato dai calcolatori Ti è sul lato RHS di p. 747. Ho incluso una foto.

Ho tradotto questo in un programma C++

#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; 
} 

Nota che i semi iniziali sono s1 = 12345 e s2 = 67890.

e abbiamo ottenuto un output da un TI-83 (mi dispiace, non ho potuto trovare un ROM-84 Ti) emulatore:

Questo corrisponde ciò che la mia realizzazione produce

Ho appena aumentato la precisione di uscita sulla mia implementazione e ottenere i seguenti risultati:

0.9435973904 
0.9083188494 
0.1466878273 
0.5147019439 
0.4058096366 
0.7338123019 
0.04399198693 
0.3393625207 

Si noti che si discostano dai risultati di Ti nelle cifre meno significative. Questa potrebbe essere una differenza nel modo in cui i due processori (Ti's Z80 versus my X86) eseguono calcoli in virgola mobile. Se è così, sarà difficile superare questo problema. Tuttavia, i numeri casuali continueranno a generare nella stessa sequenza (con l'avvertenza di seguito) poiché la sequenza si basa solo sulla matematica intera, che sono esatti.

Ho anche utilizzato il tipo long per memorizzare valori intermedi. C'è il rischio che l'implementazione di Ti si basi sull'intero overflow (non ho letto troppo attentamente il documento di L'Ecuyer), nel qual caso dovresti adeguarti a int32_t o un tipo simile per emulare questo comportamento. Supponendo, di nuovo, che i processori si comportino allo stesso modo.

Modifica

This site fornisce un'implementazione Ti-base del codice come segue:

: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 

Ho tradotto questo in C++ per il test:

#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; 
} 

Questo ha dato il seguente Risultati:

0.9435974025 
0.908318861 
0.1466878292 
0.5147019502 
0.405809642 
0.7338123114 
0.04399198747 
0.3393625248 
0.9954663411 
0.2003402617 

che corrispondono a quelli ottenuti con l'implementazione basata sulla carta originale.

Answer 2

L'algoritmo utilizzato dal comando TI-Basic rand è l'algoritmo di L'Ecuyer in base a TIBasicDev.

rand genera un numero pseudocasuale uniformemente distribuita (questa pagina e altri talvolta cadere il prefisso pseudo per semplicità) tra 0 e 1. rand (n) genera un elenco di n uniformemente distribuita pseudocasuale numeri tra 0 e 1. seed → rand seeds (inizializza) il generatore di numeri pseudocasuali incorporato. Il valore predefinito di fabbrica è 0.

L'algoritmo di L'Ecuyer viene utilizzato dalle calcolatrici TI per generare numeri pseudocasuali di .

Purtroppo non sono stato in grado di trovare alcuna fonte pubblicata da Texas Instruments a sostegno di questa affermazione, quindi non posso con certezza che questo sia l'algorthm usato. Sono anche incerto su cosa si riferisca esattamente dall'algoritmo di L'Ecuyer.

Answer 3

Ho implementato rand, randInt, randM e randBin in Python. Grazie Richard per il codice C. Tutti i comandi implementati funzionano come previsto. Puoi anche trovarlo 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))