Errore di moltiplicazione a virgola fissa a 64 bit

Question

Sto implementando un tipo numerico 31.32 con segno fisso a 64 bit in C#, basato su long. Fin qui tutto bene per l'aggiunta e la sottrazione. La moltiplicazione ha tuttavia un caso fastidioso che sto cercando di risolvere.

Il mio algoritmo attuale consiste nel suddividere ciascun operando nei suoi 32 bit più o meno significativi, eseguendo 4 moltiplicazioni in 4 long e aggiungendo i bit rilevanti di questi long. Qui è nel codice:

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 
} 

Questo funziona nel caso generale, ma non riesce in un numero di scenari. Vale a dire, il risultato è disattivato di 1,0 (valore decimale), spesso per valori estremamente piccoli o grandi degli operandi. Qui ci sono alcuni risultati dal mio test di unità (FromRaw() è un metodo che costruisce una Fix64 direttamente da un lungo valore, senza spostare di esso):

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 

Sto cercando di capire la logica di questo su carta ma sono un po 'bloccato. Come posso risolvere questo?

Answer 1

L'algoritmo sembra valido e ha funzionato "sulla carta" e sembra giusto. Qui ci sono i miei appunti elaborati per 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 

Ora qui è quello che ho il sospetto che sta accadendo: lowlowesigenze essere un ulong per il risultato a venire fuori bene, ma penso che quello che ottieni è un valore firmato. Interpretato come firmato, lowlow termina con -8714559645954320941 (troppo basso di 2^64), loResult termina con -2029016532 (troppo basso di 2^32), finalResult termina con 4768835763 (anche troppo basso di 2^32) e il valore risultante è quindi 1.11033110017888247966766357421875 che è esattamente 1 in meno di quanto previsto.

In generale i tuoi valori devono essere considerati come aventi una "metà superiore" e una "metà inferiore" senza segno. highhigh è firmato * firmato = firmato; lowhigh e highlow sono firmati * non firmati = firmati; ma lowlow non è firmato * unsigned = unsigned.

Answer 2

Non capisco, perché FromRaw(-1) * FromRaw(-1) deve restituire 0? Dovrebbe restituire +1

Generalmente su algoritmo: non dividere, solo moltiplicare long s.

Supponiamo di moltiplicare 2.3*4.5. Otterrete 10.35. Ma se moltiplichi 23*45, otterrai 1035.

Le cifre sono le stesse!

Quindi, per moltiplicare i numeri, è necessario moltiplicare m_rawValue s e quindi spostare i bit a destra.