商和餘數除法大整數的由一個大的整數

Question

long long signed A, B, C; 

或

long long unsigned A, B, C; 

我需要計算商和餘數爲表達A * B/C，其中A，B，C是大的整數，所以產品該產品A * B會導致溢出並A < C和B < C。禁止使用浮點數和使用第三方庫。如何做到這一點？

Answer 1

我認爲一個好的開始應該是使用c/C++和gmp。 gmp是一個任意的精度庫，其所有這些操作都是以任意精度實現的。它適用於整數和浮點數。

編輯：（沒有第三方庫）

我的第二個，雖然它（GMP後）爲質數分解。你需要一個算法。您可以創建一個具有Afactorization，Bfactorization和Cfactorization的矢量，它們具有分解的素數列表。然後你用C中的素數對A/B的素數進行測試，並開始擦除它們的A/B和C矢量。在所有這些測試之後，您將所有向量的成員相乘並進行正常分割。

Answer 2

剩餘的A*B/C等於剩餘的A/C和B/C模C的乘積。

//編輯：Ups，沒有看到條件A<C，B<C。在這種情況下，嘗試這樣的：

tmp = A; 
for (var i = 1; i<=B; i++) 
{ 
    if (tmp + A == overflow || tmp + A >= C) 
     tmp -= C; 
    tmp += A; 
} 

產生的tmp應該是你尋求剩餘部分。只要所有的投入都是積極的，我們正在簽署的情況下這樣做。也許它也適用於未簽名，但沒有檢查它。

當然你需要一些奇特的功能來檢查oveflow的情況。

至於商，你可以只評估A/C，然後乘以B，不是嗎？

Answer 3

對於沒有64位算術的乘法32位數，有Schrage的方法。也許你可以把它擴展到64位乘法。

Answer 4

使用任意大整數進行乘法其實非常簡單：您完全像您在學習時使用的那樣完成，並且通過紙張手動完成。但不是在基數10中使用小數，而是使用字節或整數。

例如：

A = 12340; 
B = 56789; 
aa = new byte[] { A/256, A%256 }; 
bb = new byte[] { B/256, B%256 }; 

現在，您可以循環在陣列上，並做小步驟的乘法。

Answer 5

你有A和B分成了上，下32位部分

A = Au * (1<<32) + Al 
B = Bu * (1<<32) + Bl 

（計算爲Au=A>>32; Al=A&(1<<(32)-1;），並分別考慮這些部件的產品：

A*B = Au*Bu * (1<<64) + (Au*Bl+Al*Bu) * (1<<32) + Al*Bl 

下一個你必須把這些術語中的每一個都由C和累加商和餘數（小心避免溢出！）。特別是，由於您的初始要求，Au * Bu> C是不可能的。

Answer 6

例如是這樣的：A * B的

typedef long long ll; 

const ll base = 1000*1000*1000; // 10^9 for example, could be also 1<<32 
       // or smth convenient, the goal is to store 
       // the numbers and a result in 'base'-based numerical system 
       // to avoid overflow 

pair<ll, ll> p1 = make_pair(A/base, A%base); // store the numbers in 
pair<ll, ll> p2 = make_pair(B/base, B%base); // 'base'-based numerical system 

vector<ll> v1(4); 
v1[ 0 ] = p1.second * p2.second; 
v1[ 1 ] = p1.first * p2.second + v1[ 0 ]/base; v1[ 0 ] %= base; 
v1[ 2 ] = v1[ 1 ]/base; v1[ 1 ] %= base; 

vector<ll> v2(4); 
v2[ 1 ] = p1.second * p2.first; 
v2[ 2 ] = p1.first * p2.first + v2[ 1 ]/base; v2[ 1 ] %= base; 
v2[ 3 ] = v2[ 1 ]/base; v2[ 2 ] %= base; 

ll tmp = 0; 
for(i = 0; i < 4; ++i) 
{ 
    v1[ i ] = v1[ i ] + v2[ i ] + tmp; 
    tmp = v1[ i ]/base; 
    v1[ i ] %= base; 
} 

現在V1存儲值表示在基座10^9。其餘的是仔細執行它對C的劃分，這是一個相當容易的數學挑戰:)