64 Bit * 64 Bit = 128 Bit
Author Message
64 Bit * 64 Bit = 128 Bit

Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
Bit calculation for both signed and unsigned numbers.

Scott

Sun, 25 Jan 2004 21:42:13 GMT
64 Bit * 64 Bit = 128 Bit

Quote:

> Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> Bit calculation for both signed and unsigned numbers.

We are not comp.sources.wanted.

However, this is relatively trivial if you remember your own long
multiplication.

Richard

Sun, 25 Jan 2004 21:35:27 GMT
64 Bit * 64 Bit = 128 Bit

Quote:

> Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> Bit calculation for both signed and unsigned numbers.

Think about it. You do it just like you first learned multiplication
back in first grade, except that you work in base-(2**64) instead of
base-10:

15
* 12
----
30
15
----
180

--
Clark S. Cox III

Mon, 26 Jan 2004 13:22:09 GMT
64 Bit * 64 Bit = 128 Bit

Quote:
> Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> Bit calculation for both signed and unsigned numbers.

Assuming a 64-bit integer is the largest supported by your compiler, you
will have to de-compose the operands into arrays of 32-bit integers. The
macros LOW_HALF() and HIGH_HALF() extract the low and high halves of a
"DIGIT".

For unsigned values:

typedef unsigned long long DIGIT;    // C99 code

void mul(
DIGIT *a,
DIGIT  b,
DIGIT  c
)
/*
** calculates b * c
*/
{
DIGIT bHigh = HIGH_HALF(b),
bLow  = LOW_HALF(b),
cHigh = HIGH_HALF(c),
cLow  = LOW_HALF(c);
DIGIT t = bLow * cHigh,
u = bHigh * cLow;

a[0] = bLow * cLow;
a[1] = bHigh * cHigh;

t += u;
if (t < u)
a[1] += TO_HIGH_HALF(1);
u = TO_HIGH_HALF(t);

a[0] += u;
if (a[0] < u)
++a[1];
a[1] += HIGH_HALF (t);

Quote:
}

Signed values should be multiplied as if they were unsigned values, and then

void imul(
DIGIT *a,
DIGIT  b,
DIGIT  c
)
/*
** calculates b * c by treating them as unsigned numbers, then adding (or
** subtracting) the appropriate twos-complement adjustment.
*/
{
unsigned int bNegative = DIGIT_MSB(b),
cNegative = DIGIT_MSB(c);

mul(a,b,c);

if (bNegative && cNegative) {
a[1] -= b;
a[1] -= c;
}
else {
if (bNegative)
a[1] += b;
if (cNegative)
a[1] += c;
}

Quote:
}

Hope this helps,

Daniel Pfeffer

Mon, 26 Jan 2004 15:52:17 GMT
64 Bit * 64 Bit = 128 Bit

Quote:

> > Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> > Bit calculation for both signed and unsigned numbers.

I discovered a bug in my imul() function (comes from writing code from
memory). The correct code is as follows:

void imul(
DIGIT *a,
DIGIT  b,
DIGIT  c
)
/*
** calculates b * c by treating them as unsigned numbers, then adding (or
** subtracting) the appropriate twos-complement adjustment.
*/
{
unsigned int bNegative = DIGIT_MSB(b),
cNegative = DIGIT_MSB(c);

mul(a,b,c);

if (bNegative)
a[1] -= c;    // CORRECT
if (cNegative)
a[1] -= b;    // CORRECT

Quote:
}

Apologies to all,

Daniel Pfeffer

Mon, 26 Jan 2004 22:57:58 GMT
64 Bit * 64 Bit = 128 Bit
Quote:

> > Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> > Bit calculation for both signed and unsigned numbers.

> Assuming a 64-bit integer is the largest supported by your compiler, you
> will have to de-compose the operands into arrays of 32-bit integers. The
> macros LOW_HALF() and HIGH_HALF() extract the low and high halves of a
> "DIGIT".

... snip ...

A more efficient way is to depend on (using ^ for exponentiation)

(2^n*a + b) * (2^n*c + d) =   2^2n * a * c
+ 2^n  * ((a * d) + (c * b))
+ b * d

and replacing the middle term by:

2^n * ( (a + b) * (c + d) - (a * c) - (b * d) )

which reduces the operation to three (not four) multiplications

--

Tue, 27 Jan 2004 06:05:27 GMT
64 Bit * 64 Bit = 128 Bit

Quote:

> > Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> > Bit calculation for both signed and unsigned numbers.

>     Think about it. You do it just like you first learned multiplication
> back in first grade, except that you work in base-(2**64) instead of
> base-10:

<snip>

base 2**64, now if '**' is the exponentiation operator I reckon you're telling
him to use something like base 10**19. wow. what do your digits look like?

:-)

Tue, 27 Jan 2004 21:00:58 GMT
64 Bit * 64 Bit = 128 Bit

Quote:

> > > Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> > > Bit calculation for both signed and unsigned numbers.

> >     Think about it. You do it just like you first learned multiplication
> > back in first grade, except that you work in base-(2**64) instead of
> > base-10:
> <snip>

> base 2**64, now if '**' is the exponentiation operator I reckon you're telling
> him to use something like base 10**19.

Yes. Multiplying two 64-bit numbers is just like multiplying two
single digit, base-10 numbers, except that each digit is a 64-bit
number. Basically, you're working in base-18446744073709551616.

Quote:
>wow. what do your digits look like?

Well, as long as you don't *look* at them, you'll be fine.

--
Clark S. Cox III

Tue, 27 Jan 2004 23:16:05 GMT
64 Bit * 64 Bit = 128 Bit

Quote:

> > > Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> > > Bit calculation for both signed and unsigned numbers.

> > Assuming a 64-bit integer is the largest supported by your compiler, you
> > will have to de-compose the operands into arrays of 32-bit integers. The
> > macros LOW_HALF() and HIGH_HALF() extract the low and high halves of a
> > "DIGIT".

> ... snip ...

> A more efficient way is to depend on (using ^ for exponentiation)

>    (2^n*a + b) * (2^n*c + d) =   2^2n * a * c
>                                + 2^n  * ((a * d) + (c * b))
>                                + b * d

> and replacing the middle term by:

>      2^n * ( (a + b) * (c + d) - (a * c) - (b * d) )

> which reduces the operation to three (not four) multiplications

From a mathematical perspective - you are right. The problem is that we are
trying to perform double-precision multiplication with registers no wider
than '2n' bits. In the worst case:

a+b    requires n+1 bits
c+d    requires n+1 bits
(a+b)*(c+d) requires 2n+2 bits, i.e. we must use double-precision to
calculate it.

This defeats the purpose of the exercise.

More efficient algorithms exist for multiple-precision multiplication, but
they typically have too much overhead to be used for the double-precision
case.

Daniel Pfeffer

Fri, 30 Jan 2004 17:18:36 GMT
64 Bit * 64 Bit = 128 Bit

Quote:

> > > > Does anyone have any C code that carries out a 64 Bit x 64 Bit = 128
> > > > Bit calculation for both signed and unsigned numbers.

> > > Assuming a 64-bit integer is the largest supported by your compiler, you
> > > will have to de-compose the operands into arrays of 32-bit integers. The
> > > macros LOW_HALF() and HIGH_HALF() extract the low and high halves of a
> > > "DIGIT".

> > ... snip ...

> > A more efficient way is to depend on (using ^ for exponentiation)

> >    (2^n*a + b) * (2^n*c + d) =   2^2n * a * c
> >                                + 2^n  * ((a * d) + (c * b))
> >                                + b * d

> > and replacing the middle term by:

> >      2^n * ( (a + b) * (c + d) - (a * c) - (b * d) )

> > which reduces the operation to three (not four) multiplications
> > and some additions, since a*c and b*d are already calculated.

> From a mathematical perspective - you are right. The problem is that we are
> trying to perform double-precision multiplication with registers no wider
> than '2n' bits. In the worst case:

>     a+b    requires n+1 bits
>     c+d    requires n+1 bits
>     (a+b)*(c+d) requires 2n+2 bits, i.e. we must use double-precision to
> calculate it.

> This defeats the purpose of the exercise.

You can do everything in unsigned quantities, with an initial
determination of the final sign to be applied.  It is left as an
computations, and make the necessary carries.

--