获得O（1）中rand（）生成的第N个数字

Question

我已经看过this和this。它并不能真正解决我的问题。

标准glibc rand函数的简单实现已提供here。

#include <stdio.h>

#define MAX 1000
#define seed 1

main() {
  int random_numbers[MAX];
  int i;

  random_numbers[0] = seed;
  for (i=1; i<31; i++) {
    random_numbers[i] = (16807LL * random_numbers[i-1]) % 2147483647;
    if (random_numbers[i] < 0) {
      random_numbers[i] += 2147483647;
    }
  }
  for (i=31; i<34; i++) {
    random_numbers[i] = random_numbers[i-31];
  }
  for (i=34; i<344; i++) {
    random_numbers[i] = random_numbers[i-31] + random_numbers[i-3];
  }
  for (i=344; i<MAX; i++) {
    random_numbers[i] = random_numbers[i-31] + random_numbers[i-3];
    printf("%d\n", ((unsigned int)random_numbers[i]) >> 1);
  }
}

该算法是微不足道的：给定种子后，通过将种子乘以2的值取31来生成前31个数字。以下每个数字i是i-31 + i-3的总和。

我需要以某种方式在恒定时间内获得第N个数字的值。这个想法很简单。

n100 = n97 + n69;

n100 = n96 + n66 + n69;

n100 = n96 + 2 * n66 + n38;

...

所以，在某个时候我会得到一个多项式

n100 = ai * ni for i = [0; 31]，其中ai是一些整数系数。

我写了一个为给定索引i返回ai-s的函数：

vector<size_t> GetCoefficients(size_t index) {
    vector<size_t> coeffs(34);
    stack<size_t> indices;

    indices.emplace(index - 31);
    indices.emplace(index - 3);

    while (!indices.empty()) {
        const auto current = indices.top();
        indices.pop();

        if (current < 31) {
            ++coeffs[current];
        } else if (current < 34) {
            ++coeffs[current - 31];
        } else {
            indices.emplace(current - 31);
            indices.emplace(current - 3);
        }
    }

    return coeffs;
}

对于较小的值（最多几百个），它可以正常工作，但是对于较大的索引，它会永远存在。我需要以某种方式分解非常大的索引（1e7），以便可以在给定初始种子的情况下预测第n个输出。有提示吗？

Answer 1

线性同余递归关系的闭式解是：