O(1)で任意個数先のseedを計算

O(n)の実装

#define A 0x41c64e6d
#define B 0x6073

uint step_seed_A(uint seed, uint n) {
	uint i;
	for (i = 0; i < n; i ++) {
		seed = seed * A + B;
	}
	return seed;
}

次のseedを求める式をn回実行する。簡単。*1

徘徊位置の記事で考えたことの延長でO(1)で任意個数先のseedを計算できそうだなと思った。
seed[n+2], seed[n+4], seed[n+8], seed[n+16], ... , seed[n+2^31] をseed[n]から計算するそれぞれの値をあらかじめ求めておいてそれを使って計算する。

#define NUM_BITS 32

typedef struct {
	uint a;
	uint b;
} CONSTANT;

CONSTANT const_table[NUM_BITS] = {{A, B},/*...*/};

void init_table(void) {
	int i;
	for (i = 1; i < NUM_BITS; i ++) {
		uint a = const_table[i - 1].a;
		uint b = const_table[i - 1].b;
		const_table[i].a = a * a;
		const_table[i].b = a * b + b;
	}
}

uint step_seed_B(uint seed, uint n) {
	int i = 0;
	while (n) {
		if (n & 1) {
			seed = seed * const_table[i].a + const_table[i].b;
		}
		i ++;
		n >>= 1;
	}
	return seed;
}

1bitごと処理していってbitが立っていたら対応する値で演算するという仕組み。最大32回の演算で済む。

さらに踏み込んで高速化してみる。
seed[n+1]からseed[n+0xff]までを計算する値をあらかじめ計算しておく。
同様にseed[n+0x100], seed[n+0x200], seed[n+0x300] ..., seed[n+0xff00]も。seed[n+0x10000]からseed[n+0xff0000]とseed[n+0x1000000]からseed[n+0xff000000]も。

#define NUM_BYTES 4
#define CACHE_SIZE 256

CONSTANT cache[NUM_BYTE][CACHE_SIZE];

void init_cache(void) {
	int i;
	for (i = 0; i < NUM_BYTES; i ++) {
		int j;
		CONSTANT c = const_table[i * 8];
		cache[i][0].a = 1;
		cache[i][0].b = 0;
		cache[i][1] = c;
		for (j = 2; j < CACHE_SIZE; j ++) {
			uint a = cache[i][j - 1].a;
			uint b = cache[i][j - 1].b;
			cache[i][j].a = a * c.a;
			cache[i][j].b = b * c.a + c.b;
		}
	}
}

uint step_seed_C(uint seed, uint n) {
	int i;
	for (i = 0; i < NUM_BYTES; i ++) {
		CONSTANT c = cache[i][(n >> (i * 8)) & 0xff];
		seed = seed * c.a + c.b;
	}
	return seed;
}

*1:最大2^32-1回ですむんだからO(1)といえるんじゃないかという考え方もできそうだが…どうなんだろう