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

http://www.whereismyhead.com/clark/



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
adjusted 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 && 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
and some additions, since a*c and b*d are already calculated.

--

   (Remove "XXXX" from reply address. yahoo works unmodified)



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.
Otherwise, your head would explode. :-)

--
Clark S. Cox III

http://www.whereismyhead.com/clark/



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
> 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.

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
exercise for the reader to detect overflow in the additional
computations, and make the necessary carries.

--

   (Remove "XXXX" from reply address. yahoo works unmodified)



Sat, 31 Jan 2004 00:25:49 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. 128 bit pointers (re: 64 bit pointers?)

2. Help: porting 32-bit app to 64-bit Dec Alpha

3. 64-bit integer on a 32-bit machine

4. Calling 64 bit lib. from 32 bit program

5. emulating a 64 bit divide with 2 32 bit registers in ansi c

6. converting signed 64 bit - 32 bit

7. 64 bit operation on 32 bit PC

8. 64-bit chips, 32-bit compatibility?

9. REQUEST: 64-bit integer math on 32-bit processor

10. Accessing 32-bit com componet from 64-bit application

11. top 32 bits of 64-bit product of two 32-bit integers

12. 32-bit vs 64-bit

 

 
Powered by phpBB® Forum Software