大整數和雙整數

我用gmp管理一些大的（128〜256bits）整數。它已經來了一個點，我想他們的倍增接近1（0.1 <雙< 10），結果仍然是一個近似的整數。我需要做的工作的一個很好的例子是：大整數和雙整數

int i = 1000000000000000000 * 1.23456789

我搜索了GMP文件中，但我沒有找到這個功能，所以我結束了寫這個代碼似乎運作良好：

mpz_mult_d(mpz_class & r, const mpz_class & i, double d, int prec=10) { 
    if (prec > 15) prec=15; //avoids overflows 
    uint_fast64_t m = (uint_fast64_t) floor(d); 
    r = i * m; 
    uint_fast64_t pos=1; 
    for (uint_fast8_t j=0; j<prec; j++) { 
    const double posd = (double) pos; 
    m = ((uint_fast64_t) floor(d * posd * 10.)) - 
     ((uint_fast64_t) floor(d * posd)) * 10; 
    pos*=10; 
    r += (i * m) /pos; 
    } 
}

你能告訴我你的想法是什麼嗎？你有任何建議讓它更強大或更快？

來源

2013-05-27 DarioP

這是一個問題r [代碼審查]（http://codereview.stackexchange.com/），不適用於StackOverflow :) – Morwenn

哦，對不起，我不知道那個分支。然而，這只是我解決一個非常精確的問題。請考慮回答一般問題，最終只對代碼發表評論。謝謝！ – DarioP

如果您需要近似值，爲什麼不將大整數轉換爲double？ –

這是你想要什麼：

// BYTE lint[_N] ... lint[0]=MSB, lint[_N-1]=LSB 
void mul(BYTE *c,BYTE *a,double b) // c[_N]=a[_N]*b 
    { 
    int i; DWORD cc; 
    double q[_N+1],aa,bb; 
    for (q[0]=0.0,i=0;i<_N;)  // mul,carry down 
     { 
     bb=double(a[i])*b; aa=floor(bb); bb-=aa; 
     q[i]+=aa; i++; 
     q[i]=bb*256.0; 
     } 
    cc=0; if (q[_N]>127.0) cc=1.0; // round 
    for (i=_N-1;i>=0;i--)   // carry up 
     { 
     double aa,bb; 
     cc+=q[i]; 
     c[i]=cc&255; 
     cc>>=8; 
     } 
    }

_N是位/ 8％大整型數，大int是_N字節數組，其中第一個字節是MSB（最顯著字節）和最後一個字節LSB （最低有效BYTE）函數不處理signum，但它只有一個，如果和一些xor/inc添加。

麻煩的是，即使對於您的號碼1.23456789 !!!雙倍有低精度！由於精度損失的結果不是確切的應該是什麼（1234387129122386944，而不是1234567890000000000）我認爲我的代碼更快，甚至比你更精確，因爲我不需要mul/mod/div數字10，而是我使用可能的位移，而不是10位而是256位（8位）。如果你需要比使用長算術更高的精度。你可以通過使用更大的數字來加速這個代碼（16,32，... bit）

我精確的天文計算的長運算通常是固定點256.256位數字包含2 * 8的DWORD + signum，當然速度慢得多，一些測角函數實現起來很難，但如果你只需要基本功能而不是代碼，那麼你自己的算術運算並不難。

此外，如果你想以可讀的形式往往有一個數字是很好的速度/大小之間的妥協，並考慮不使用二進制編碼的數字，但我不是那麼熟悉或者C++或GMP BCD編碼的數字

來源

2013-08-04 17:50:08 Spektre

什麼我可以建議沒有語法錯誤的源代碼，但是你正在做的事情比它應該更復雜，可能會引入不必要的近似。

相反，我建議你寫函數mpz_mult_d()這樣的：

mpz_mult_d(mpz_class & r, const mpz_class & i, double d) { 
    d = ldexp(d, 52); /* exact, no overflow because 1 <= d <= 10 */ 
    unsigned long long l = d; /* exact because d is an integer */ 
    p = l * i; /* exact, in GMP */ 
    (quotient, remainder) = p/2^52; /* in GMP */

而且現在的下一步取決於那種圓你希望的。如果希望將d乘以i的結果給出-inf的四捨五入結果，則僅返回quotient作爲該函數的結果。如果你想四捨五入到最接近的整數的結果，你必須看看remainder：

assert(0 <= remainder); /* proper Euclidean division */ 
assert(remainder < 2^52); 
if (remainder < 2^51) return quotient; 
if (remainder > 2^51) return quotient + 1; /* in GMP */ 
if (remainder == 2^51) return quotient + (quotient & 1); /* in GMP, round to 「even」 */

PS：我發現你的問題通過隨機瀏覽，但如果你已經標記爲「浮點」，人們更勝於我本可以迅速回答。

來源

2013-08-05 07:54:41

嘗試這種策略：

轉換整數值大的浮動
轉換雙重價值大浮
使產品

結果轉換爲整數

mpf_set_z(...) 
mpf_set_d(...) 
mpf_mul(...) 
mpz_set_f(...)

來源

2018-01-25 08:34:50 GeScript

大整數和雙整數

回答

相關問題