64-Bit-Festkomma-Multiplikationsfehler

Question

Ich implementiere einen 64-Bit-Festkomma-31,32-Zahlentyp in C#, basierend auf long. So weit, so gut für Addition und Subtraktion. Multiplikation hat jedoch einen ärgerlichen Fall, den ich versuche zu lösen.

Mein aktueller Algorithmus besteht darin, jeden Operanden in seine höchstwertigen und niedrigstwertigen 32 Bits aufzuteilen, 4 Multiplikationen in 4 Longs durchzuführen und die relevanten Bits dieser Longs hinzuzufügen. Hier ist es in Code:

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 
} 

Dies funktioniert im allgemeinen Fall, aber scheitert in einer Reihe von Szenarien. Das Ergebnis ist nämlich um 1.0 (Dezimalwert) ausgeschaltet, oft für extrem kleine oder große Werte der Operanden. Hier sind einige Ergebnisse aus meinen Unit-Tests (FromRaw() sind eine Methode, die eine Fix64 direkt von einem Long-Wert aufbaut, ohne es zu verschieben):

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 

Ich versuche, die Logik dieses auf dem Papier zu arbeiten, aber ich bin ein bisschen fest. Wie kann ich das beheben?

Answer 1

Der Algorithmus sieht gut aus, und es hat "auf dem Papier" funktioniert und es scheint richtig. Hier sind meine erarbeitet Noten für 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 

Jetzt ist hier, was ich vermute, geschieht: lowlowBedürfnisse eine ulong für das Ergebnis richtig sein zu kommen, aber ich denke, Was Sie bekommen, ist ein signierter Wert. Interpretiert als unterzeichnet, lowlow endet -8714559645954320941 (zu niedrig von 2^64), loResult endet -2029016532 (zu niedrig von 2^32), finalResult endet als 4768835763 (auch zu niedrig von 2^32), und Der resultierende Wert ist dann 1,11033110017888247966766357421875 was genau 1 weniger ist, als Sie erwarten.

Im Allgemeinen sollten Ihre Werte so behandelt werden, dass sie eine "obere Hälfte" und eine "untere Hälfte" haben. highhigh ist signiert * signiert = signiert; lowhigh und highlow sind signiert * unsigned = signed; aber lowlow ist vorzeichenlos * unsigned = unsigned.

Answer 2

Ich verstehe nicht, warum FromRaw(-1) * FromRaw(-1)0 zurückgeben sollte? Es sollte +1

Allgemein über Algorithmus: nicht teilen, einfach multiplizieren long s.

Angenommen, Sie multiplizieren 2.3*4.5. Sie erhalten 10.35. Aber wenn Sie 23*45 multiplizieren, erhalten Sie 1035.

Die Zahlen sind gleich!

Also, um Ihre Zahlen zu multiplizieren, sollten Sie multiplizieren m_rawValue s und dann Bits nach rechts verschieben.