Computing die hohe Bits einer Multiplikation in C#

Question

Ich versuche, eine Open-Source-Bibliothek von .Net 4,0-3,5 zu konvertieren und kann den folgenden langen Multiplikation Code nicht leicht umwandeln:

/// <summary> 
    /// Calculate the most significant 64 bits of the 128-bit 
     product x * y, where x and y are 64-bit integers. 
    /// </summary> 
    /// <returns>Returns the most significant 64 bits of the product x * y.</returns> 
    public static long mul64hi(long x, long y) 
    { 
#if !NET35 
     BigInteger product = BigInteger.Multiply(x, y); 
     product = product >> 64; 
     long l = (long)product; 
     return l; 
#else 
     throw new NotSupportedException(); //TODO! 
#endif 
    } 

Wie Sie das sehen Autor hat keinen Weg gefunden, dies zu tun. BigInteger ist in .NET 3.5 nicht vorhanden.

Wie kann ich die hohen Bits 64 Bits einer 64 * 64 Multiplikation auf .NET 3.5 berechnen?

Answer 1

Sie können einen 2N-Bit-Multiplikator aus mehreren N-Bit-Multiplikatoren erstellen.

public static ulong mul64hi(ulong x, ulong y) 
{ 
    ulong accum = ((ulong)(uint)x) * ((ulong)(uint)y); 
    accum >>= 32; 
    accum += (x >> 32) * ((ulong)(uint)y); 
    accum += (y >> 32) * ((ulong)(uint)x); 
    accum >>= 32; 
    accum += (x >> 32) * (y >> 32); 
    return accum; 
} 

Es ist nur Grundschule Multiplikation, wirklich.

Mit vorzeichenbehafteten Nummern ist es etwas schwieriger, denn wenn Zwischenergebnisse in das Vorzeichen-Bit übertragen werden, läuft alles schief. Ein long kann nicht das Ergebnis einer 32-Bit von 32-Bit-Multiplikations ohne dass das passiert halten, so haben wir es in kleinere Stücke zu tun:

public static long mul64hi(long x, long y) 
{ 
    const long thirtybitmask = 0x3FFFFFFF; 
    const long fourbitmask = 0x0F; 
    long accum = (x & thirtybitmask) * (y & thirtybitmask); 
    accum >>= 30; 
    accum += ((x >> 30) & thirtybitmask) * (y & thirtybitmask); 
    accum += ((y >> 30) & thirtybitmask) * (x & thirtybitmask); 
    accum >>= 30; 
    accum += ((x >> 30) & thirtybitmask) * ((y >> 30) & thirtybitmask); 
    accum += (x >> 60) * (y & fourbitmask); 
    accum += (y >> 60) * (x & fourbitmask); 
    accum >>= 4; 
    accum += (x >> 60) * (y >> 4); 
    accum += (y >> 60) * (x >> 4); 
    return accum; 
} 

Inspiriert von Harolds Kommentar über Hacker Delight, die signierte Version kann genauso effizient wie die anderen gemacht werden, indem man sorgfältig gesteuert wird, ob Zwischenergebnisse oder nicht angemeldet sind:

public static long mul64hi(long x, long y) 
{ 
    ulong u = ((ulong)(uint)x) * ((ulong)(uint)y); 
    long s = u >> 32; 
    s += (x >> 32) * ((long)(uint)y); 
    s += (y >> 32) * ((long)(uint)x); 
    s >>= 32; 
    s += (x >> 32) * (y >> 32); 
    return s; 
}