Алгоритм генератора случайных чисел TI-84 Plus

Используемый алгоритм взят из статьи П. Л'Экюйе Эффективные и портативные комбинированные генераторы случайных чисел.

Документ можно найти здесь и бесплатно загрузить с сайта здесь.

Алгоритм, используемый калькуляторами Ti, находится на правой стороне стр. 747. Я включил изображение.

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

Я только что увеличил точность вывода в своей реализации и получил следующие результаты:

0.9435973904
0.9083188494
0.1466878273
0.5147019439
0.4058096366
0.7338123019
0.04399198693
0.3393625207

Обратите внимание, что они расходятся с результатами Ти в менее значащих цифрах. Это может быть различием в том, как два процессора (Ti Z80 по сравнению с моим X86) выполняют вычисления с плавающей запятой. Если да, то решить эту проблему будет сложно. Тем не менее, случайные числа по-прежнему будут генерироваться в той же последовательности (с оговоркой ниже), поскольку последовательность зависит только от целочисленной математики, которая является точной.

Я также использовал тип long для хранения промежуточных значений. Существует некоторый риск того, что реализация Ti полагается на целочисленное переполнение (я не слишком внимательно читал статью L'Ecuyer), и в этом случае вам придется настроить на int32_t или аналогичный тип, чтобы эмулировать это поведение. Предполагая, опять же, что процессоры работают одинаково.

Изменить

На этом сайте представлена ​​следующая реализация кода на Ti-Basic:

: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

Я перевел это на C++ для тестирования:

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

Это дало следующие результаты:

0.9435974025
0.908318861
0.1466878292
0.5147019502
0.405809642
0.7338123114
0.04399198747
0.3393625248
0.9954663411
0.2003402617

которые соответствуют тем, которые были достигнуты при реализации, основанной на исходной статье.

Я реализовал rand, randInt, randM и randBin на Python. Спасибо Ричарду за код C. Все реализованные команды работают как положено. Вы также можете найти его в этой сути.

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))

Алгоритм, используемый командой TI-Basic rand, представляет собой алгоритм Л'Экюйе в соответствии с TIBasicDev.

rand генерирует равномерно распределенное псевдослучайное число (на этой и других страницах псевдо-префикс иногда опускается для простоты) между 0 и 1. rand(n) генерирует список из n равномерно распределенных псевдослучайных чисел между 0 и 1. seed→rand инициализирует (инициализирует) встроенный генератор псевдослучайных чисел. Начальное значение по умолчанию — 0.

Алгоритм Экюйера используется калькуляторами TI для генерации псевдослучайных чисел.

К сожалению, мне не удалось найти какой-либо источник, опубликованный Texas Instruments, подтверждающий это утверждение, поэтому я не могу с уверенностью утверждать, что используется именно этот алгоритм. Я также не уверен, на что именно ссылается алгоритм Л'Экюйе.