大きな数の最初の10桁を求める

大きな数の最初の10桁を効率的に計算しないといけないような問題に遭遇した。

下n桁を求めるのは剰余で出来るけど、上n桁ってどうやるのだろう。
logを使うとうまく出来そうだ。ということでやってみた。
とりあえず2のべき乗の上10桁を求めてみた。

プログラム

#include <iostream>
#include <cmath>

using namespace std;

const double EPS = 1e-6;

// return the first 10 digits of 2^k
long long calc(int k) {
    double x = k * log(2);
    int d = x / log(10);
    x -= d * log(10);
    x += 9 * log(10);
    return exp(x) + EPS;
}


int main(int argc, char **argv) {
    
    cout << calc(1000) << endl;
    cout << calc(10000) << endl;
    cout << calc(100000) << endl;

    return 0;
}

結果確認

プログラムの実行結果。

1071508607
1995063116
9990020930

Pythonで2^kを実際に計算して検算してみた。正しく計算出来ていた。

$ python -c "print str(2**1000)[:10]"
1071508607
$ python -c "print str(2**10000)[:10]"
1995063116
$ python -c "print str(2**100000)[:10]"
9990020930