calc_index.c

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

typedef uint32_t u32;

/* x[0] = 0, x[n+1] = (a * x[n] + b) mod 2^k
   で与えられる数列{x[n]}において、x[n] = sを満たすnを求める
   ただし数列の周期は2^kになっていなければならない */
u32 calc_index(u32 a, u32 b, u32 s, u32 k) {
	if (k == 0) {
		return 0;
	} else if ((s & 1) == 0) {
		return calc_index(a * a, (a + 1) * b / 2, s / 2, k - 1) * 2;
	} else {
		return calc_index(a * a, (a + 1) * b / 2, (a * s + b) / 2, k - 1) * 2 - 1;
	}
}

int main(void) {
	u32 A = 0x41c64e6d;
	u32 B = 0x6073;

	printf("%.8x\n", calc_index(A, B, 0, 32));
	printf("%.8x\n", calc_index(A, B, B, 32));
	printf("%.8x\n", calc_index(A, B, A * B + B, 32));
	printf("%.8x\n", calc_index(A, B, A * A * B + A * B + B, 32));
	return 0;
}

calc_index2.c

/*
再帰がよくわからない人向けに書きなおしたもの
要するにcalc_index(a, b, s, 0)は0と定義し、整数k>0に対して(a,b,s)3変数の関数calc_index(a, b, s, k)はcalc_index(a, b, s, k - 1)を用いて定義するという数学でいうただの帰納的定義です。
*/

u32 calc_index_0(u32 a, u32 b, u32 s) {
	return 0;
}

u32 calc_index_1(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_0(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_0(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_2(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_1(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_1(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_3(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_2(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_2(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_4(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_3(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_3(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_5(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_4(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_4(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_6(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_5(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_5(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_7(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_6(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_6(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_8(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_7(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_7(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_9(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_8(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_8(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_10(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_9(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_9(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_11(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_10(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_10(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_12(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_11(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_11(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_13(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_12(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_12(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_14(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_13(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_13(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_15(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_14(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_14(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_16(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_15(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_15(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_17(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_16(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_16(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_18(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_17(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_17(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_19(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_18(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_18(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_20(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_19(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_19(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_21(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_20(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_20(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_22(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_21(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_21(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_23(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_22(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_22(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_24(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_23(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_23(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_25(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_24(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_24(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_26(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_25(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_25(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_27(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_26(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_26(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_28(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_27(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_27(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_29(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_28(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_28(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_30(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_29(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_29(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_31(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_30(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_30(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}

u32 calc_index_32(u32 a, u32 b, u32 s) {
	if ((s & 1) == 0) {
		return calc_index_31(a * a, (a + 1) * b / 2, s / 2) * 2;
	} else {
		return calc_index_31(a * a, (a + 1) * b / 2, (a * s + b) / 2) * 2 - 1;
	}
}