10^k (mod M)の値を保持した配列を高速で求めたい

Question

実現したいこと

10^k (mod M)の値を保持した配列を高速で求めたい

考えたこと

• 10^k = 10^(k-1) * 10
• 10^(k-1) * 10 (mod M) ≡ (10^(k-1) (mod M)) * (10 (mod M)) (mod M)

上式を使ってk=0から求めていける

const int MAX_DIGIT = 100;       // 桁数の上限
vector<int> a(MAX_DIGIT);        // 10^k (mod M)の値を保持する配列
a[0] = 1;
for (int k = 1; k < MAX_DIGIT; k++) {
  a[k] = a[k-1] * 10;
  a[k] %= M;                     // 10^k (mod M)
}

発生している問題

先ほどのコードで構築した配列aと実際の答えが異なる

具体的には...

(long long int)pow(10, k) % Mが10^k (mod M)の値

for (int k = 0; k < 15; k++) {         // 試験的にとりあえずk=0...14をやる
  cout << (a[k] == (long long int)pow(10, k) % M) << endl;
}

この出力が全て1と出るはずなのだが、そうはならなかった

---

この原因が分かる方がいらっしゃいましたら、ご回答をお願いいたします。

Answer 1

ついこの間も同じような問題を見かけたのですが、powの返り値はdouble型なので大きな値を入れた場合に、たとえそれが整数演算であっても浮動小数点誤差が発生します。
powを使うのはやめましょう。

ついでですが、10^kを計算するときにkを半分に割って行った方が計算は速いでしょう。
端数は上手いことやってください。

Comments

[pifacela]

ご回答ありがとうございます。
これにはまって、3時間くらい溶かしてました。
大人しく、その方法で実装してたものを使います。。。

[退会済みユーザー]

なまじ整数の計算だから結構引っかかってしまうようで...
doubleの精度は2進数53桁、10進数換算で15桁強だそうです(10^kならk=16から誤差が出るはず)

[pifacela]

ありがとうございます。
これでやっと寝れる...！

Answer 2

こちら側の確認不足でした。
おおよその原因はわかりました。ただ、詳細は分かりかねますが。。。

std::powは浮動小数点の型（float,double,long doubleとか）で値を返すようです。
コードでは、それをlong long int、つまり整数型にキャストしました。
そのキャスト時に、ビットの関係で値に誤差が出たと思われます。（あってるのかなぁ。。。）

Answer 3

ごめんなさい、kは15未満でした…

誤った回答

桁あふれしているということはないですか？
long long intは64ビットのため、19桁程度が限界です。
20桁以上、つまりkが19以上だと桁あふれし、マイナスの値になっているなどにより、その後の剰余算が正しく計算されていない可能性があります。

Comments

[pifacela]

こちら側の確認不足でした。
おおよその原因はわかりました。ただ、詳細は分かりかねますが。。。
pow(10, k)がバグっているようです。