2026-10-21
binom.zig
const std = @import("std");
var memo: [32]u64 = @splat(0);
fn binom(n: u5, k: u5) u64 {
if (k == 0 or k == n) return 1;
if (@inComptime()) return binom(n - 1, k - 1) + binom(n - 1, k);
if (memo[n] == 0) memo[n] = binom(n - 1, k - 1) + binom(n - 1, k);
return memo[n];
}
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var stdout_writer = std.Io.File.stdout().writer(init.io, &buf);
const stdout = &stdout_writer.interface;
try stdout.print("{d} {d} {d}\n", .{ comptime binom(4, 2), binom(4, 1), binom(4, 2) });
try stdout.flush();
}
binom(n, k) は、異なる n 個から k 個を選ぶ組合せの数、二項係数(binomial coefficient)nCk を返すつもりの関数です。実行時は一度計算した値をグローバル変数の memo に覚えて再計算を省き、memo を読み書きできないコンパイル時は、そのまま再帰で計算します。main は 4C2 をコンパイル時に計算した値と、4C1、4C2 を実行時に計算した値を並べます。いまは 6 4 4 と出力されます。本来の出力は 6 4 6 です。
Answer
Wrong
var memo: [32]u64 = @splat(0);
if (memo[n] == 0) memo[n] = binom(n - 1, k - 1) + binom(n - 1, k);
return memo[n];
binom の値は n と k の2つで決まるのに、memo は n だけを添字にしています。先に呼ばれる binom(4, 1) は、nCk = n-1Ck-1 + n-1Ck(パスカルの三角形の関係)で binom(3, 1)、binom(2, 1) とたどり、memo[2] に2、memo[3] に3、memo[4] に4を書きます。続く実行時の binom(4, 2) は memo[4] が0でないので計算せず、k が違うのに4を返します。
同じ binom(4, 2) でも、comptime を付けた1つ目は正しく6になります。コンパイル時の呼び出しでは @inComptime() が true になり、再帰の途中も含めて memo を使う行に一度も届かないからです。コンパイル時の結果だけを見て関数を確かめると、実行時の経路の誤りは同じ関数の中にあっても見つかりません。
Right
var memo: [32][32]u64 = @splat(@splat(0));
if (memo[n][k] == 0) memo[n][k] = binom(n - 1, k - 1) + binom(n - 1, k);
return memo[n][k];
memo を n と k の2次元にすれば、binom(4, 1) の4は memo[4][1] に入り、binom(4, 2) は空の memo[4][2] を見て計算し直すので6を返します。二項係数は1以上なので、0を「まだ計算していない」の印に使えます。@inComptime で経路を分けた関数は、コンパイル時と実行時の両方で呼んで確かめる必要があります1。
@inComptimeの枝を消して両方の経路を1つにすると、comptime binom(4, 2)はmemoを読むところで「unable to evaluate comptime expression」というコンパイルエラーになります。グローバルなvarは実行時の値なので、コンパイル時には読めません。