演算子の優先順位と整数除算の影響

問題の概要

20×20グリッド上で左上から右下への経路数を計算する際、以下の2種類の式で異なる結果が生成される現象が発生します：

result = result * (x + i) / i;  // 正しい結果
result *= (x + i) / i;         // 誤った結果

計算の目的は中央二項係数（central binomial coefficient）を求めることで、数学的には以下の式で表されます：

(2x)! / (x! * x!)

元のアルゴリズムは次のようなコードで正しく動作します：

public long countRoutes(int x)
{
    long result = 1;
    
    for (int i = 1; i <= x; i++)
    {
        result = result * (x + i) / i;
    }
    
    return result;
}

しかし、result *= (x + i) / i に変更すると結果が不正となります。この現象の原因はC#の演算子の優先順位と整数除算の性質にあります。

原因の詳細分析

演算子の優先順位による計算順序の差異

C#では、代入演算子（*=）は通常の算術演算子（*, /）よりも優先順位が低くなっています。これにより2つの式は異なる順序で計算されます：

// ケース1: result = result * (x + i) / i の実際の解釈
result = (result * (x + i)) / i;

// ケース2: result *= (x + i) / i の実際の解釈
result = result * ((x + i) / i);

整数除算の切り捨てによる影響

C#の整数除算では、商の小数部が切り捨てられます。計算順序の違いがこれにより重大な誤差を生みます：

// 例: x=2, i=2, result=10 の場合

// 正しい計算順序 (乗算→除算)
(10 * (2 + 2)) / 2 → (10 * 4) / 2 → 40 / 2 = 20

// 誤った計算順序 (除算→乗算)
10 * ((2 + 2) / 2) → 10 * (4 / 2) → 10 * 2 = 20 → 正しい

一見同じ結果に見えますが、割り切れない場合に問題が発生します：

// 例: x=3, i=2, result=10

// 正しい計算順序
(10 * (3 + 2)) / 2 → (10 * 5) / 2 → 50 / 2 = 25

// 誤った計算順序
10 * ((3 + 2) / 2) → 10 * (5 / 2) → 10 * 2 = 20 // 5/2=2.5→切り捨てで2

重要な注意点

整数除算の切り捨ては(x+i)/i 単体でも発生しますが、このアルゴリズムでは result * (x + i) が 常にiで割り切れるという数学的特性があります（二項係数の性質）。そのため上記の例は問題を説明するための簡易例です。

数学的背景と動作保証

この経路計算アルゴリズムでは、各ステップでのresult * (x + i) は必ずiで割り切れます。なぜなら：

1. result が二項係数 $\binom{x + i - 1}{i}$ を保持
2. 次の式で計算される値 $\binom{x + i}{i} = \frac{(x+i)!}{i!x!}$ は整数
3. 漸化式：
   $\binom{x + i}{i} = \binom{x + i - 1}{i-1} \times \frac{x + i}{i}$

つまり、result * (x + i) / i の計算途中で余りが発生しないことが数学的に保証されています。誤った順序で計算すると、この性質を無視した整数除算が発生し、値の損失が累積的に蓄積されるのです。

整数演算のベストプラクティス

1. 計算順序の選択

   • 除算の切り捨て誤差を最小化: 乗算→除算の順序を優先
   • 例: a = (b * c) / d が a = b * c / d より安全

2. オーバーフロー対策

   // オーバーフローが懸念される場合
   result = (result / i) * (x + i); // 除算を先行させる

   • 注意: 除算を先に行うには result / i が整数であることが前提

3. データ型の選択

   • 大きな値が予想される場合: long > int
   • 高精度が必要な場合: decimal 型の検討

現実的なアドバイス

1. 算術演算と代入演算子を混在させない
2. 複雑な式は明示的に括弧で優先順位を指定
3. 整数除算の切り捨てを常に意識する
4. 境界値テスト（最小値/最大値）を必ず実施

// 最適化された経路計算メソッド
public long SafeCountRoutes(int gridSize)
{
    long routes = 1;
    
    for (int i = 1; i <= gridSize; i++)
    {
        // 明確な計算順序を保証
        routes = (routes * (gridSize + i)) / i;
    }
    
    return routes;
}

この問題の本質は、言語仕様の理解不足ではなく、演算子優先順位と型の振る舞いの相互作用にあります。適切な計算順序と型選択により、整数演算でも正確な結果を得ることが可能です。