Computing the high bits of a multiplication in C#

Question

I'm trying to convert an open source library from .Net 4.0 to 3.5 and cannot easily convert the following long multiplication code:

    /// <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
    }

As you can see the author didn't find a way to do this. BigInteger does not exist in .NET 3.5.

How can I compute the high bits 64 bits of a 64*64 multiplication on .NET 3.5?

Thank you for the link, using the J# Library I might get this to work! I'm trying it out now... — Seneral, Apr 18 '15 at 20:12
hm no not working for me, [MDSN](https://msdn.microsoft.com/de-de/library/7xsxf8e2%28v=vs.90%29.aspx) says it's only avaiable in VS 5 or less, and I need to use VS2010 for the other problems (default parameters) — Seneral, Apr 18 '15 at 20:16
Since you are asking for a well known problem (high bits of multiplication) there are existing solutions: http://stackoverflow.com/questions/28868367/getting-the-high-part-of-64-bit-integer-multiplication I did not find a C# solution but the C code should work as is. — usr, Apr 18 '15 at 20:18
@usr Thank you, I'll take a look into that one, currently following a solution wich uses the System.Numeric namespace from the Mono source code [Answer](http://blogs.windwardreports.com/davidt/2011/02/calling-j-code-from-net-40.html) It looks very promising:) — Seneral, Apr 18 '15 at 20:23

Ben Voigt · Accepted Answer · 2019-04-22T13:17:26.967

9

You can build a 2N-bit multiplier from multiple N-bit multipliers.

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

It's just elementary-school long multiplication, really.

With signed numbers, it's a bit harder, because if intermediate results carry into the sign bit everything goes wrong. A long can't hold the result of a 32-bit by 32-bit multiply without that happening, so we have to do it in smaller chunks:

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;
}

Inspired by harold's comment about Hacker's Delight, the signed version can be made just as efficient as the other, by carefully controlling whether intermediate results are or are not signed:

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;
}

edited Apr 22 '19 at 13:17

answered Apr 18 '15 at 20:21

Ben Voigt

277,958
43
419
720

1

Oh, to be honest I didn't expect this to work;) And I can't really control the solution, its somewhat of 4trillion (9 trillion is the max value?) Thank you so much!! – Seneral Apr 18 '15 at 20:28
@Seneral: Make sure to run a bunch of unit tests. Because you have signed numbers, some of the intermediate results can carry into the sign bits, I'm not sure if that will corrupt the final result. – Ben Voigt Apr 18 '15 at 20:29
@Seneral: I think I have a version that should work on negative numbers also. Added it. – Ben Voigt Apr 18 '15 at 20:40
1

Could the signed version be improved by using the " High-Order Product Signed from/to Unsigned"-thing from Hacker's Delight or wouldn't that be any better? – harold Apr 18 '15 at 21:18
@harold: That section doesn't help, but the note above it about using a mixture of signed and unsigned for the intermediate results would. – Ben Voigt Apr 18 '15 at 21:24
`mul64hi` fails when multiplying very large numbers - for example, `UInt64.MaxValue * UInt64.MaxValue`. `System.Numerics.BigInteger` says the result should be `18446744073709551614`, but this calculates `18446744069414584318` – Cocowalla Apr 22 '19 at 11:11
@Cocowalla: Thanks for noticing that, now fixed at least the unsigned version. – Ben Voigt Apr 22 '19 at 13:17
@BenVoigt thank was fast, and it seems to work perfectly now! – Cocowalla Apr 22 '19 at 13:56

Computing the high bits of a multiplication in C#

1 Answers1