64-bitowy błąd mnożenia stałoprzecinkowego

Question

Wprowadzam 64-bitowy stały numerowany 31.32 numeryczny w C#, na podstawie long. Do tej pory tak dobre dla dodawania i odejmowania. Mnożenie ma jednak irytującą sprawę, którą próbuję rozwiązać.

Mój aktualny algorytm polega na podzieleniu każdego operandu na jego najbardziej i najmniej znaczące 32 bity, wykonaniu 4 multiplikacji na 4 długie i dodaniu odpowiednich bitów tych długich. Tutaj jest w kodzie:

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 
} 

Działa to w ogólnym przypadku, ale kończy się niepowodzeniem w wielu scenariuszach. Mianowicie, wynik jest wyłączony o 1,0 (wartość dziesiętna), często dla bardzo małych lub dużych wartości operandów. Oto niektóre wyniki moich testów jednostkowych (FromRaw() jest metodą, która buduje Fix64 bezpośrednio z dużej wartości, bez przesuwania go):

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 

Staram się wypracować z logiką tego na papierze ale trochę utknąłem. Jak mogę to naprawić?

Answer 1

Algorytm wygląda na dźwięk i wyszło z niego "na papierze" i wydaje się słuszne. Oto moje wypracowane nuty dla 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 

Teraz oto co podejrzewam dzieje: lowlowpotrzeb się być ulong za rezultat wyjdzie prawo, ale myślę, że to, co otrzymujesz, to podpisana wartość. Interpretowana jako podpisana, lowlow kończy się na -8714559645954320941 (zbyt niska przez 2^64), loResult kończy się na -2029016532 (za niska przez 2^32), finalResult kończy się na (również za niska przez 2^32), oraz wynikowa wartość to 1,11033110017888247966766357421875, czyli dokładnie o 1 mniej niż można się spodziewać.

Generalnie twoje wartości powinny być traktowane jako oznaczone "górną połówką" i niepodpisaną "dolną połówką". highhigh jest podpisane * signed = signed; lowhigh i highlow są podpisane * unsigned = signed; ale lowlow jest bez znaku * unsigned = unsigned.

Answer 2

Nie rozumiem, dlaczego FromRaw(-1) * FromRaw(-1) powinien zwrócić 0? Powinien on zwrócić +1

Ogólnie o algorytmie: nie dziel, po prostu mnożenie long s.

Załóżmy, że pomnożysz 2.3*4.5. Otrzymasz 10.35. Ale jeśli pomnożysz 23*45, otrzymasz 1035.

Liczby są takie same!

Aby pomnożyć liczby, należy pomnożyć liczbę m_rawValue s, a następnie przesunąć bity w prawo.