2026-10-29
steps.c
#include <stdint.h>
#include <stdio.h>
static int steps(uint64_t a) {
uint64_t x = a;
int n = 0;
while (a * x != 1) {
x *= 2 - a * x;
n++;
}
return n;
}
int main(void) {
printf("%d %d %d\n", steps(3), steps(255), steps(65537));
}
これは何を出力するでしょうか?
Answer
5 3 2 です。
uint64_t の計算は264で割った余りで行われるので、ループは a * x を264で割った余りが1になったところで止まります。x *= 2 - a * x は、a の逆数 1 / a に近づけるための Newton法1の式です。ただ、x の値を1回ずつ追うのは、64ビットの掛け算が続くので手では無理です。
追うのは x ではなく、ずれ e = 1 - a * x のほうです。1回の更新で a * x は a * x * (2 - a * x) になり、これは (1 - e) * (1 + e) = 1 - e * e です。つまり更新のたびに e は e * e に置き換わり、k 回後には最初の e の2k乗になります。264で割った余りの世界でもこの式は崩れません。ループが止まるのは、この値が264で割り切れたときです。
初期値は x = a なので、最初の e は 1 - a * a = -(a - 1)(a + 1) です。最初の e が2で m 回割り切れるなら、2k乗した k 回後の e は2で m × 2k 回割り切れ、この回数が64以上になったときにだけ264で割り切れます。a が奇数だと a - 1 と a + 1 は続いた2つの偶数なので、m は少なくとも3です。
a = 3 では 2 * 4 で m は3です。3 × 16 = 48 は64に届かず、3 × 32 = 96 で届くので、5回です。a = 255 では 254 * 256 が2を1回と8回含み、m は9になって、9 × 8 = 72 の3回で止まります。a = 65537 では 65536 * 65538 が2を16回と1回含み、m は17なので、17 × 4 = 68 の2回です。
「Newton法は1回ごとに正しい桁数が倍になる」とだけ考え、奇数の2乗を8で割ると1余ることから最初は3ビット正しいとすると、3、6、12、24、48、96と数えて 5 5 5 と答えてしまいます。255 と 65537 は、初期値の時点で a - 1 と a + 1 が2を多く含むぶん、早く止まります。
- Newton法(ニュートン法、Newton's method)は、関数
fの値が0になる点を求めるために、いまの点での接線が横軸と交わる点へ移る操作を繰り返す方法です。f(x) = 1/x - aに当てはめると、更新の式はx(2 - a x)になります。この式は割り算を使わないので、2のべき乗を法とする逆元を求めるのにも使えます。コンパイラは、定数で割る計算を掛け算に置き換えるときにこの逆元を使います。