Idiom: Calculating Power of 10 using pow Function in Integer Arithmetic

今日参加したコンテストで有効な電話番号の組み合わせ数を求める問題が出題されました。実装ではlong longの大きな値、例えば\(10^{17}\)から小さな値、例えば10や1を引く演算を行う必要がありました。

powを使って10の冪乗を計算する解法も少なくなかったのですが、おそらくそのほとんどはテスト時に落ちてしまいました。どうやら計算誤差が原因のようです。

これは自分にとっても大きな驚きでした。xが整数である場合、pow(10, x)がきっちりと10の冪乗を返すことを知っていたからです。

  long long x = 1;
  
  for (int i = 0; i < 18; i ++, x *= 10)
    assert(pow(10, i) == x);            // pow(10, i)は問題なし

どこで計算誤差が出ているかを考えるために以下のような実装を用意しました。\(10^{17} - (10^0 + 10^1 + 10^2)\)を計算する実装です。期待している答えは末尾が...,999,889となるはずです。

long long c = pow(10, 17);

assert(c == 100000000000000000LL); // ここは問題なし

std::vector<int> a = {0, 1, 2};

for (const auto& i : a)
  c -= pow(10, i);

assert(c == 99999999999999889LL);  // ここでアサーションエラー!

変数cの内容をチェックしました。期待とは異なり、99,999,999,999,999,888でした。

さて、以下は期待通り...,999,889を返します。

long long c = pow(10, 17);

assert(c == 100000000000000000LL);      // ここは問題なし

astd::vector<int> a = {0, 1, 2};

for (const auto& i : a)
  c -= static_cast<long long>(pow(10, i));

assert(c == 99999999999999889LL);       // ここも問題なし!

どうも自分はこれまで、-=演算子は左側の変数の型で演算される、と思い込んでいたようです。つまり右辺の値がまずlong longにキャストされると考えていました。実際には二項の加減算演算子の振る舞いと同様に、doubleにキャストされてから計算され、改めてlong longにキャストされるようです。

これまで挙動を正確に把握していなかったこともあり、pow関数を使って10の冪乗を計算しないようにしていましたが、次のようなイディオムとして今後積極的に使っていきたいな、と考えています。またこの知見を大好きなハックにも役立てたいです。

long long y = static_cast<long long>(pow(10, x));

最後になりますが、TLで気さくに質問に答えてくださった@n_vipさん、ありがとうございました。

追記

これは実装依存の挙動だそうです。一般的に、pow(x, y)のyが整数のときはpowを使うべきではないとのこと。naoya_tさんにご指摘いただきました。どうもありがとうございます)。

参考: c++ - Definitions of sqrt, sin, cos, pow etc. in cmath - Stack Overflow