Finding the Seed of the rand() Function TI

2018-06-24 06:51:46

I've done a lot of research on that TI-84 rand() function. It uses the L'Ecuyer's algorithm to generate pseudorandom numbers. I have an interesting case however.

If the rand() function is given the proper seed, it will always generate the same numbers. So, given the first random number that the rand() function generates, is it possible to find the seed of the function?

Let the variable X represent the unknown seed.

    X->rand
    rand->D
    Disp D

Output:

    0.114820491

Based off this information, is it possible to calculate the seed of the rand() function? Can you work backwards somehow from the TI-84's rand() algorithm?

No, empirically it is not possible to calculate the seed based on just the first generated random number because it is not unique. The following code will do a brute force search for a seed given the first random number:

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <stdlib.h>

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

void Seed(int64_t 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(int argc, char **argv){
  double x = 0.114820491; // Mattkx4's value
  double r;
  int64_t n;
  int i;

  if (argc > 2) {
    printf("USAGE: %s <1st generated random number>n", argv[0]);
    return 1;
  } else if (argc == 2) {
    x = atof(argv[1]);
    printf("[Looking for seed generating %.10f]n", x);
  } else {
    printf("[Looking for seed generating default value of %.10f]n", x);
  }

  for (n=0; n<= 2147483647; n++) {
    Seed(n);
    r = Generate();
    if (fabs(r-x) < 10e-10) {
      printf("HIT: seed is %ld; G()=%.10f, G()-x=%.12fn", (long) n, r, r-x);
      for (i=0; i<5; i++) {
        printf("  G() = %.10fn", Generate());
      }
    }
  }

  return 0;
}

In the case of the OPs first random number, it gives the following output:

$ time ./a.out
[Looking for seed generating default value of 0.1148204910]
HIT: seed is 41817; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.1928098124
  G() = 0.8785866698
  G() = 0.7541802051
  G() = 0.3236799652
  G() = 0.2698472063
HIT: seed is 196206349; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.7255189385
  G() = 0.3079613984
  G() = 0.8041985209
  G() = 0.0959226401
  G() = 0.7729820570
HIT: seed is 392370881; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.2582281409
  G() = 0.7373361269
  G() = 0.8542168367
  G() = 0.8681653150
  G() = 0.2761169842
HIT: seed is 588535413; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.7909372669
  G() = 0.1667108555
  G() = 0.9042350761
  G() = 0.6404079899
  G() = 0.7792519113
HIT: seed is 1869313916; G()=0.1148204919, G()-x=0.000000000876
  G() = 0.9421831845
  G() = 0.2660259263
  G() = 0.9001868100
  G() = 0.3563914254
  G() = 0.3884731955
HIT: seed is 2065478448; G()=0.1148204919, G()-x=0.000000000876
  G() = 0.4748923105
  G() = 0.6954006549
  G() = 0.9502050494
  G() = 0.1286341003
  G() = 0.8916080463

real    1m24.132s
user    1m24.179s
sys 0m0.000s

In answering this, I am standing on the shoulders of giants by using the code provided by @richard in an answer to this stackoverflow question. If there is a better way to provide attribution, please let me know or simply edit this answer.

I found one solution, but I wouldn't consider it the most effective system. The following was the program I used to exhaustively search for a match to the rand number.

0→C

Repeat X=0.114820491
Disp C
C→rand
rand→X
C+1→C
End

Disp "Done!"

This program tests every seed for the rand function until it eventually finds the seed that produces the desired random number.

The problem with this system is that there is an insanely large number of possibilities. In this case, the program only had to run a little over 40,000 times, but in some cases this program would have be run millions and millions of times before finding a matching seed. However, this works if the seed is relatively small.

It's not the best solution, but it is a solution.

See @JimD.'s answer for a more precise method.

链接地址: http://www.djcxy.com/p/68040.html

上一篇: 使用srand和rand的并行gem令人惊讶的输出

下一篇: 寻找rand（）函数的种子TI