GoでGMPスタイルのパフォーマンスで大きな数字を扱う

Question

私はGoを学習しています。math/bigパッケージを使用して任意の長さの整数を処理し始めました。

Iはn番目のフィボナッチ数を計算し、このプログラムを書いた：（import秒削除）：

int main(int argc, char** argv) 
{ 
    int imax = atoi(argv[1]); 

    mpz_t a, b, c; 
    mpz_inits(a, b, c, NULL); 
    mpz_set_ui(a, 0); 
    mpz_set_ui(b, 1); 

    int i = 0; 
    for (i = 0; i < imax; i++) { 
     mpz_swap(a, b); 
     mpz_add(b, a, b); 
    } 

    char* astr = NULL; 
    astr = mpz_get_str(NULL, 10, a); 
    printf("%s\n", astr); 

    return EXIT_SUCCESS; 
} 

囲碁プログラムを計算：

func main() { 
    imax, _ := strconv.Atoi(os.Args[1]) 
    var a, b, c big.Int 
    a.SetUint64(0) 
    b.SetUint64(1) 
    for i := 0; i < imax; i++ { 
     c.Set(&b) 
     b.Add(&b, &a) 
     a.Set(&c) 
    } 
    fmt.Println(a.String()) 
} 

ここでCプログラムのためのコードですGMP libを使用した場合のCの等価物は0.04秒でのみ実行されます。それは2倍遅いです。

私のGoプログラムで同じパフォーマンスを得る方法はありますか？

Answer 1

stdoutに印刷しないでください。遅いです。このコードの結果はどうなりますか？

package main 

import (
    "math/big" 
    "os" 
    "strconv" 
) 

func main() { 
    max, err := strconv.Atoi(os.Args[1]) 
    if err != nil { 
     panic(err) 
    } 
    a, b := big.NewInt(0), big.NewInt(1) 
    for i := 0; i < max; i++ { 
     a.Add(a, b) 
     a, b = b, a 
    } 
} 

手作りのアセンブラコードではありません。

100,000という値は、信頼性の高いベンチマークには小さすぎます。少なくとも10秒間実行される1,000,000または別の値を使用します。

Answer 2

一般に、GMPはパフォーマンスの面で優れているため、高速です。このフードの下では、関数の呼び出しのオーバーヘッドを減らし、ADXのようなCPU命令を利用することができるアセンブリで部分的に書かれていることがわかります。

パフォーマンスが気になる場合は、mpz_fib_uiルーティンを使用することができます。これは、数学的なトリッキーから得られるので、さらに高速になります。

あなたの質問への直接の答えはおそらくGMPのためのいくつかのGoのバインディングを使用することです。