# Re: How multiply two __int64 ...

Discussion in 'C Programming' started by BartC, Nov 1, 2010.

1. ### BartCGuest

"Kappa" <_NO_SPAM> wrote in message
news:4ccd3833\$0\$40004\$...
> Hi,
>
> I was wondering if someone has already written a routine to multiply two
> __int64 for obtain a __int128.
>
> Can someone help me ?

Google? There must be some code out there.

If you want to do this yourself, as C code where 64-bit multiply is
available, but not 128-bit, then it's quite tricky:

* Even using 64-bits, you will need access to the top half of the 128-bit
product, which leaves you almost where you started. C will not give you
this.

awkward with C.

* You also need to consider that a general 128-bit multiply will have a
256-bit result (you might choose to ignore this).

An attempt at trying to use 64-bit multiplies might look as follows:

If you define one *unsigned* 128-bit int as (a*m + b), where a and b are
high and low 64-bit halves, and m is a scale factor (2**64), and another as
(c*m+d), then the product will be (I think, as I haven't tried it):

(a*b*m*m + a*d*m + b*c*m + b*d)

But each product as I said could overflow into 128-bits, and the additions
and shifts (*m) must be 128-bits too. (Actually the shifts aren't too
difficult.)

You could do it with a *lot* of 32-bit arithmetic inside 64-bit types (and
it would be very slow), but I think the way to go, if you have to do this
yourself, is to drop into assembler (either inline, or as an external
function).

--
Bartc

BartC, Nov 1, 2010