GNU MP Library的GCD計算問題

我有一個關於GNU MP的問題，請問如何解決這個問題。我在Windows上使用「The GNU Multiple Precision Arithmetic Library」版本5.1.1。（MinGW \ gcc + MSYS）GNU MP Library的GCD計算問題

存在一個mpz_gcd函數來計算兩個整數的「gcd」。

void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2);

就我從文檔中得到的，在GNU MP中實現了幾個算法用於計算最大公約數。其中：

二進制GCD
萊默算法
次二次GCD

所使用的算法似乎是自動選擇，基於整數的輸入大小。

目前，二進制算法用於GCD只有當N < 3.

對於除GCD_DC_THRESHOLD較大輸入，GCD經由的hGCD（半GCD）函數作爲一般化到萊默的算法來計算。

所以，我猜有至少三種不同的方法來獲得gcd（a，b）。我的主要問題是：我想指定自己使用哪種算法。我會比較這些算法在隨機大輸入（即10^5位）上的執行時間，以找出一些常見趨勢：使用「Binary GCD」變得比「Lehmer的方法」更糟糕的是「HGCD-萊默爾泛化「比直接勒梅爾等更好。

是否有任何簡單的方法來指定要使用的算法？以任何方式從庫中提取該算法，以任何方式修改一些「#define」變量。沒有庫重新編譯，是否可以像我想要的那樣做一些事情？我只是初學者，我不覺得能夠找出圖書館裏的所有東西。

P.S.可能有人會感興趣會發生什麼。我在github上有一些代碼：https://github.com/int000h/gcd_gcc

來源

2013-02-20 Mikhail Kalashnikov

這是閱讀源代碼的好時機。 GMP是開源的 - 利用它！

在mpn/generic/gcd.c，你會發現它選擇GCD算法的功能（這其實是一種公共職能，它出現在文檔中）：

mp_size_t 
mpn_gcd (mp_ptr gp, mp_ptr up, mp_size_t usize, mp_ptr vp, mp_size_t n) 
{ 
    ... 
    if (ABOVE_THRESHOLD (n, GCD_DC_THRESHOLD)) { 
     ...

你可以看到有三個主要分支的功能，每個以return語句結尾。每個分支對應於不同的GCD算法。您可以將代碼複製並粘貼到您自己的應用程序中並對其進行修改，以便您可以精確指定您想要的算法。提示：

你可以擺脫#ifdefs。假設TUNE_GCD_P未定義。
這是一個mpn_*函數，而不是mpz_*函數。它是較低級別的：例如，您必須爲輸出明確分配空間。您也可能希望從上級功能mpz_gcd()複製代碼。
您需要提取內部函數的原型，如mpn_hgcd_matrix_adjust()。只需將原型從GMP源代碼中複製出來即可。別擔心，內部函數似乎是從共享庫中導出的（它們通常不應該是，但它們是，所以你很好）。

沒有必要重新編譯庫，但您需要在這裏做一些工作。

來源

2013-02-20 01:05:04

我試着去調查。我只是立即感到困惑，爲什麼這個定義放在「mpn /」下，而不是「mpz /」和其他許多東西。至少現在我知道這是可能的，所以我會繼續尋找。謝謝！ – 2013-02-20 01:11:21

GNU MP Library的GCD計算問題

回答

相關問題