Long multiplication of a pair of uint64 values

Question

How can I multiply a pair of uint64 values safely in order to get the result as a pair of LSB and MSB of the same type?

typedef struct uint128 {
    uint64 lsb;
    uint64 msb;
};

uint128 mul(uint64 x, uint64 y)
{
    uint128 z = {0, 0};
    z.lsb = x * y;
    if (z.lsb / x != y)
    {
        z.msb = ?
    }
    return z;
}

Am I computing the LSB correctly?
How can I compute the MSB correctly?

It's awkward to do in portable C, you basically would need to recreate grade-school "long multiplication" which requires four separate multiplies and several adds. However, most 64-bit compilers will provide, as an extension to standard C, either a 128-bit integer type with restricted functionality (e.g. gcc's `unsigned __int128`) or else an intrinsic to access the widening multiply instruction which most machines provide. — Nate Eldredge, Oct 02 '20 at 19:21
@NateEldredge: Yeah, it's exactly what I'm doing now, splitting each one of the input values into a pair of `uint32`. Was hoping to get something off the shelf here. Thank you. — goodvibration, Oct 02 '20 at 19:22
Are you willing to use something compiler-specific? If so, say what compiler you are using. — Nate Eldredge, Oct 02 '20 at 19:23
There must be thousands of tutorials on how to do arithmetic operations like these, all over the Internet. Did you figure out the algorithm you show in the code yourself? Or did you use or adapt something you found? If you found it, where did you find it? What did the resource you were using tell you about it? What makes you doubt it? What makes you wonder about your own solution? Have you tested it? Does it work for your tests? If it's a school or book assignment/exercise, does it work with the tests of your school or book? — Some programmer dude, Oct 02 '20 at 19:23
@NateEldredge: Solidity. And the actual types are `uint256`. I posted the question and in C, because I was hoping to get a quick answer. I posted it without specifying platform, because I am looking for a pure arithmetic solution (because I obviously cannot rely on any HW and/or compiler). — goodvibration, Oct 02 '20 at 19:26
@Someprogrammerdude: Sure, but I couldn't find a way to phrase it in a simple Google query, hence I posted it here (hoping to get a 'duplicate' suggestion, to be honest). And for all it matters, it is not for school (Solidity was born some 20 years after I had already finished high school). — goodvibration, Oct 02 '20 at 19:27
I see, that's an important difference. Honestly I think the most common solution is "use [GMP](https://gmplib.org/)" or something similar instead of reinventing the wheel. — Nate Eldredge, Oct 02 '20 at 19:29
I agree with @NateEldredge, use whatever libraries are available. Unless, of course, this is a school assignment in which case it should have been covered in class. :) — Some programmer dude, Oct 02 '20 at 19:34
I do seem to recall a fairly recent question about multiplying 256-bit integers but I can't find it. — Nate Eldredge, Oct 02 '20 at 19:36
Tip: Split them into 32 bit numbers, multiply 2 32 bit numbers and split the 64 bit result into 2 32 bit numbers. Do the same as in early school without a calculator but instant of single digits use a 32 bit number as a digit. — 12431234123412341234123, Oct 02 '20 at 20:27
It's strange to reinvent the wheel. I believe there will be many of ready-to-use libraries on github (especially in C++, that you can port to C). I found [this](https://github.com/abseil/abseil-cpp/blob/master/absl/numeric/int128.h#L919), [this](https://gist.github.com/pmj/2660790), [this](https://github.com/flang-compiler/flang/blob/master/lib/scutil/int128.c#L373). — KamilCuk, Oct 02 '20 at 20:49

score 0 · Answer 1 · answered Oct 02 '20 at 21:01

As said in the comments, the best solution would probably using a library which does that for you. But i will explain how you can do it without a library, because i think you asked to learn something. It is probably not a very efficient way but it works.

When we where in school and we had to multiply 2 numbers without a calculator, we multiplied 2 digits, had a result with 1-2 digits, and wrote them down and in the end we added them all up. We spited the multiplication up so we only had to calculate a single digit multiplication at once. A similar thing is possible with higher numbers on a CPU. But there we do not use decimal digits, we use half of the register size as digit. With that, we can multiply 2 digits and become 2 digits, in one register. In decimal 13*42 can be calculated as:

  3* 2 =     0 6
 10* 2 =     2 0
  3*40 =   1 2 0
 10*40 = 0 4 0 0
        --------
         0 5 4 6

A similar thing can be done with integers. To make it simple, i multiply 2 8 bit numbers to a 16 bit number on a 8 bit CPU, for that i only multiple 4 bit with 4 bit at a time. Lets multiply 0x73 with 0x4F.

0x03*0x0F = 0x002D
0x70*0x0F = 0x0690 
0x03*0x40 = 0x00C0 
0x70*0x40 = 0x1C00
            -------
            0x22BD

You basically create an array with 4 elements, in your case each element has the type uint32_t, store or add the result of a single multiplication in the right element(s) of the array, if the result of a single multiplication is too large for a single element, store the higher bits in the higher element. If an addition overflows carry 1 to the next element. In the end you can combine 2 elements of the array, in your case to two uint64_t.

Long multiplication of a pair of uint64 values

1 Answers1