大數的分區

我需要一些可以處理大整數（128位）的除法算法。我已經問過如何通過位移操作符來完成它。不過，我目前的實現似乎要求一個更好的辦法大數的分區

基本上，我店數爲兩個long long unsigned int的格式

A * 2^64 + B與B < 2^64。

這個數字是可以被24整除，我想除以24。

我目前的做法是像

A * 2^64 + B  A    B 
-------------- = ---- * 2^64 + ---- 
     24   24   24 

      A    A mod 24     B   B mod 24 
= floor(----) * 2^64 + ---------- * 2^64 + floor(----) + ---------- 
      24    24.0      24   24.0

改造它。然而，這是越野車。

（注意，地板是A/24並且mod是A % 24，正常分裂被存儲在long double，整數被存儲在long long unsigned int。

由於24等於二進制11000，所述第二被加數不應該在第四個加數的範圍內改變一些東西，因爲它向左移動64位

因此，如果A * 2^64 + B可以被24整除，而B不是，那麼它很容易發現它的錯誤，因爲它返回一些非整數號碼

我的實現中有什麼錯誤？

來源

2009-11-27 Etan

位移法的問題是什麼？ – 2009-11-27 13:15:54

當你已經能夠劃分int64的 – Etan 2009-11-27 15:12:37

我能想到的最簡單的方法是將128位數字視爲四個32位數字：

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

然後執行長除以24：

E = A/24 (with remainder Q) 
F = Q_B/24 (with remainder R) 
G = R_C/24 (with remainder S) 
H = S_D/24 (with remainder T)

凡X_Y意味着X*2^32 + Y。然後，答案是E_F_G_H，其餘爲T。在任何時候，你只需要劃分64位數字，所以這隻適用於整數運算。

來源

2009-11-27 13:12:09 interjay

它不會阻止你的算法工作，但F，G和H每個都可以大於2^32。我很難與E_F_G_H表示看起來像串聯這一事實相一致，但一旦理解了這一點，這是一個非常好的算法。 – 2009-11-27 13:36:16

實際上，F，G和H將小於2^32，因爲Q，R和S都小於24.所以E_F_G_H表示法*是串聯的。 – interjay 2009-11-27 13:51:14

對！我忘記了我的鉛筆和紙張部門...我記得有一個不愉快的猜測部分，但那是除數的數字太多。只要除數本身足夠短以至落入原始分割工作的範圍內（這裏就是這種情況），在應用鉛筆和紙張分割算法時從不需要猜測。對困惑感到抱歉。 – 2009-11-27 14:34:37

你不應該使用long double作爲你的「正常部門」，而是那裏的整數。 long double沒有足夠的有效數字來得到答案（無論如何，整個問題的關鍵是用整數運算來做到這一點，對嗎？）。

來源

2009-11-27 12:31:39

時，它似乎是過度殺傷性的，它的全部點是將128位int除以24，這導致史詩般的失敗。長雙有64位的尾數，所以這不應該成爲一個問題。還是呢？ – Etan 2009-11-27 12:36:57

Etan應該鏈接到eir原始問題。看來，目標不是用整數來完成，而是要做到這一點。此外，「long double」可以小到64位雙倍，但也可以更大（例如10個字節的擴展雙倍，但是任何東西，實際上...... IEEE 754主要是參考比特大小）。因此它*可能*可能具有必要的精度（我並不是說使用浮點運算來完成像128位整數運算那樣簡單的操作是個好主意）。 – 2009-11-27 12:39:17

如何分割而不用長雙？ – Etan 2009-11-27 12:40:05

由於24等於11000的二進制數，所以第二個加數不應該改變第四個加數的範圍內的內容，因爲它將64位向左移位。

你的公式是用實數寫成的。（A mod 24）/ 24可以有任意數量的小數（例如，1/24爲0.041666666 ...），因此可能會干擾分解中的第四項，即使乘以2^64也是如此。

Y * 2^64不干擾較低權重二進制數字的屬性僅在Y是整數時起作用。

來源

2009-11-27 12:32:32

它會干擾小數，因爲您無法將它們準確地寫在那裏。在二進制中，它有一個有限的實現，因爲1/24可以寫入數字的結尾。 – Etan 2009-11-27 12:39:01

@Etan真的嗎？需要多少位數字才能用二進制表示1/24呢？（如果這個問題太難了，以二進制數字的個數開始，它代表1/3） – 2009-11-27 12:47:48

1/24 =二進制0.00001010101010101 ...序列永遠持續。 – dave4420 2009-11-27 12:51:16

不要。

去抓一個圖書館來做這個東西 - 你會非常感謝你選擇調試奇怪的錯誤。

片段。org前段時間在它的網站上有一個C/C++ BigInt庫，Google也發佈了以下內容：http://mattmccutchen.net/bigint/

來源

2009-11-27 12:49:04

我必須手動完成它，因爲它是針對ACM ICPC問題的。 – Etan 2009-11-27 12:50:26

這可能用反乘法來解決嗎？要注意的第一件事是24 == 8 * 3所以

a/24 == (a >> 3)/3

結果讓x = (a >> 3)然後分工的結果是8 * (x/3)。現在仍然可以找到x/3的值。

模塊化算術狀態，存在一個n，使得n * 3 == 1 (mod 2^128)。這給出：

x/3 = (x * n)/(n * 3) = x * n

它仍然是找到常數n。有關於如何在wikipedia上執行此操作的解釋。你還必須實現功能來乘以128位數字。

希望這會有所幫助。

/A.B。

來源

2009-11-27 13:45:46

回答

相關問題