Bignum 遅い原因分かった

GMP は算術など演算は速い。ただ結果を格納するバッファを allocate するのが遅い。reallocation を防ぐために大きめにバッファを取るそうな。整数ならば mpz_init が allocate する関数。
mpz_init はサイズ指定できないのだが mpz_init2 ではできる。これを利用して allocate するメモリサイズを適切に設定すれば多少は速くなりそう。
例えば Bignum 同士の足し算であれば結果のサイズはある程度計算する事が出来るし。というわけでやってみる。

追記

いまいち速度には効かないようだ。いわゆる計算途中経過オブジェクトを専用スタックに取るとかしないといけないのかな。
GMP を Bignum のバックエンドに使っている言語処理系って何があったっけ。みなどうやって対処しているんだろう。
mpz_init と mpz_init2 の速度差や、allocation が結構重い件は以下のコードで体験できる。

#include <gmp.h>
#include <stdlib.h>
int main() {
    mpz_t a;
    mpz_init(a);
    mpz_set_si(a, 500000);
    mpz_mul(a, a, a);

    mpz_t b;
    mpz_init(b);
    mpz_set_si(b, 500000);
    mpz_mul(b, b, b);
    mpz_t ret;

    for (int i = 0; i < 10000000; i++) {
//        mpz_init2(ret, 128);
        mpz_init(ret);
        mpz_add(ret, a, b);
    }
    printf("%d %d %d\n", mpz_size(a), mpz_size(b), mpz_size(ret) * mp_bits_per_limb);
    return 0;
}