64位定點乘法錯誤

我在C＃中實現了一個64位定點簽名的31.32數值類型，基於long。到目前爲止，加法和減法都非常好。然而，乘法有一個惱人的情況，我試圖解決。64位定點乘法錯誤

我的當前算法由每個操作數分裂成其最高和最低顯著32位，進行4次乘法成4個多頭，添加這些多頭的相關比特。這裏是代碼：

public static Fix64 operator *(Fix64 x, Fix64 y) { 

    var xl = x.m_rawValue; // underlying long of x 
    var yl = y.m_rawValue; // underlying long of y 

    var xlow = xl & 0x00000000FFFFFFFF; // take the 32 lowest bits of x 
    var xhigh = xl >> 32; // take the 32 highest bits of x 
    var ylow = yl & 0x00000000FFFFFFFF; // take the 32 lowest bits of y 
    var yhigh = yl >> 32; // take the 32 highest bits of y 

    // perform multiplications 
    var lowlow = xlow * ylow; 
    var lowhigh = xlow * yhigh; 
    var highlow = xhigh * ylow; 
    var highhigh = xhigh * yhigh; 

    // take the highest bits of lowlow and the lowest of highhigh 
    var loResult = lowlow >> 32; 
    var midResult1 = lowhigh; 
    var midResult2 = highlow; 
    var hiResult = highhigh << 32; 

    // add everything together and build result 
    var finalResult = loResult + midResult1 + midResult2 + hiResult; 
    return new Fix64(finalResult); // this constructor just copies the parameter into m_rawValue 
}

這在一般情況下工作，但在許多情況下失敗。也就是說，結果是1.0（十進制值），對於操作數的極小值或大值通常是這樣。下面是我的單元測試的一些結果（FromRaw（）被直接從長值建立一個Fix64不轉移它的方法）：

Failed for FromRaw(-1) * FromRaw(-1): expected 0 but got -1 
Failed for FromRaw(-4) * FromRaw(6791302811978701836): expected -1.4726290525868535041809082031 but got -2,4726290525868535041809082031 
Failed for FromRaw(2265950765) * FromRaw(17179869183): expected 2.1103311001788824796676635742 but got 1,1103311001788824796676635742

我想在紙上計算出的這個邏輯但我有點卡住了。我怎樣才能解決這個問題？

來源

2012-12-24 Asik

你在做什麼進位？另外，我不完全理解翻譯......「2265950765」的等效數值是多少？ – mellamokb

是的，進位位呢？ –

我不熟悉C＃的整數升級規則 - 值是lowlow等32位還是32x32乘法會自動給出64位結果？ – hobbs

該算法看起來很合理，並且它在「紙上」工作並且看起來正確。這裏是我制定了筆記FromRaw(2265950765) * FromRaw(17179869183)（0.52758277510292828083038330078125 * 3.99999999976716935634613037109375 = 2.11033110017888247966766357421875）

x1 = 2265950765 
y1 = 17179869183 

xlow = 2265950765 
xhigh = 0 
ylow = 4294967295 
yhigh = 3 

lowlow = 9732184427755230675 
lowhigh = 6797852295 
highlow = 0 
highhigh = 0 

loResult = 2265950764 
midResult1 = 6797852295 
midResult2 = 0 
hiResult = 0 

finalResult = 9063803059

現在，這裏就是我懷疑正在發生的事情：lowlow需求是用於存放結果的ulong出來的權利，但我認爲，你得到的是一個有符號的值。解釋爲有符號，lowlow結束爲-8714559645954320941（太低2^64），loResult結果爲-2029016532（太低2^32），finalResult結果爲4768835763（也低得2^32），以及結果得到的值是1.11033110017888247966766357421875，這比您預期的要小1。

一般來說你的價值觀應該被視爲有署名「上半部」和無符號的「下半部」。 highhigh已簽名* signed = signed; lowhigh和highlow已簽名* unsigned = signed;但lowlow是無符號*無符號=無符號。

來源

2012-12-24 22:47:52 hobbs

沒錯，低項需要無符號。 –

@StephenCanon哈！很高興在這裏見到你。我不知道你是否記得，但幾年前你幫了我一個非常類似的問題，這就是爲什麼我現在明白了:) – hobbs

如果xlow和ylow是無符號的，我必須插入一個轉換來執行xlow * yhigh和xhigh * ylow，因爲C＃不會讓我將有符號和無符號長整數相乘。我應該將高值轉換爲無符號值，然後將結果轉換爲帶符號？這讓我困惑。 – Asik

我不明白，爲什麼FromRaw(-1) * FromRaw(-1)應該返回0？它應該返回+1

一般關於算法：不分割，只是乘以long s。

假設你乘以2.3*4.5。您將獲得10.35。但是，如果您乘以23*45，您將獲得1035。

數字是一樣的！

所以，乘以你的號碼，你應該乘m_rawValue秒，然後轉向右邊位。

來源

2012-12-24 22:19:21 Dims

不，交叉乘法算法是正確的。如果您「換乘並換檔」，則在換檔前溢出，結果不正確。要獲得64x64 = 64的乘法，需要將其分解爲四個32x32 = 64的乘法運算。 – hobbs

原始值-1表示-0.00 ... 0024東西，這是我的類型可以表示的最小負值。所以如果你自己乘以它，它會給出的結果太小而不能表示，因此應該四捨五入爲0. – Asik

64位定點乘法錯誤

回答

相關問題