0
$\begingroup$

I have a struct like this:

struct UInt128 {
    UInt64 s1;
    UInt64 s2;
}

In this struct, s1 represents the highest 64-bits of my 128 bit integer, and s2 represents the lowest 64-bits of my 128 bit integer.

I'm attempting to implement a method that produces the product of two UInt128's.

My current thought process is that the solution is similar to FOIL, the technique used to expand brackets in algebra e.g. $(a+b)(c+d)$ where we give the result as $ac + ad + bc + ad$, but my issue comes from the fact that I don't understand how to break the result back into two UInt64's.

How can I compute the product of two UInt128's as defined by the struct above?

$\endgroup$
1
$\begingroup$

It depends what operations are available to you for 64 bit integers.

The product of two 64 bit integers is a 128 bit integer. Many programming languages don't provide such a product, for example in C you will likely have an operation that produces the 64 bit (x * y) modulo $2^{64}$, but not an operation that produces the 128 bit number x * y.

On the other hand, given two 64 bit numbers x, y, many processors have instructions that produce 64 bit integers a and b such that mathematically x * y = a * $2^{64}$ + b.

If such an operation is available to you, you would calculate the 128 bit product x.s2 * y.s2, and the two 64 bit products x.s1 * y.s2 and x.s2 * y.s1 and use these to calculate the 128 bit product. If you want a 256 bit product, then you need to calculate four 128 bit products.

If you have no easy means to calculate the 128 bit product of two 64 bit numbers, then hopefully you can calculate the 64 bit product of two 32 bit integers, so you can use the same operations with half the number of bits.

$\endgroup$
0
$\begingroup$

The numbers are $s1\times f+s2$ where $f = 2^{64}$

This means that the product is:

$(a\times f+b)(c\times f+d) = ac\times f^2+(ad+bc)\times f+bd$

So if you don't mind dropping all the overflowing high bits then all you need to do is split up $bd$ into 2 64 bit parts using divide and remainder (or shift and mask because $f$ is a power of 2) and you'll get the result:

$$( (ad+bc \mod f )+\lfloor \frac{bd}{f}\rfloor)f+(bd \mod f)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.