How to get the exceeding part of a product when the multiplication overflows?

[Ttodir]

Hello,

consider int(a) * int(b):

do you know a way to get the value built with the exceeding bits of
the product when the multiplication overflows, WITHOUT using any type
larger than int's to get the value?

 

[gwowen]

Hello,

consider int(a) * int(b):

do you know a way to get the value built with the exceeding bits of
the product when the multiplication overflows, WITHOUT using any type
larger than int's to get the value?

Split a and b into two halves into most significant and least
significant

e.g. I'll it with 16-bit unsigned as the exposition is easier. Dealing
with the sign bit is left as an exercise.

a = [a1|a0] i.e. (256*a1 + a0)
b = [b1|b0] i.e. (256*b1 + b1)

a*b = 2^16 (a1*b1) + 2^8 * (a1*b0 + b1*a0) + a0*b0.

Of these - the overflow parts of (a*b) are (a1*b1) plus most
significant byte of (a1*b0+a0*b1).

So, in general, break your 2N-bit integers into N-bit integers, with
implicit binary exponents

a = [a1|a0] = (2^N)*a1 + a0 ... etc, etc, etc

 

[Ttodir]

Hello,

consider int(a) * int(b):

do you know a way to get the value built with the exceeding bits of
the product when the multiplication overflows, WITHOUT using any type
larger than int's to get the value?

Split a and b into two halves into most significant and least
significant

e.g. I'll it with 16-bit unsigned as the exposition is easier. Dealing
with the sign bit is left as an exercise.

a = [a1|a0] i.e. (256*a1 + a0)
b = [b1|b0] i.e. (256*b1 + b1)

a*b = 2^16 (a1*b1) + 2^8 * (a1*b0 + b1*a0) + a0*b0.

Of these - the overflow parts of (a*b) are (a1*b1) plus most
significant byte of (a1*b0+a0*b1).

So, in general, break your 2N-bit integers into N-bit integers, with
implicit binary exponents

a = [a1|a0] = (2^N)*a1 + a0 ... etc, etc, etc

thanks

 

[Rune Allnor]

Hello,

consider int(a) * int(b):

do you know a way to get the value built with the exceeding bits of
the product when the multiplication overflows, WITHOUT using any type
larger than int's to get the value?

Nope. That's why this is an overflow.

Rune