Author 
Message 
Scott O'Nei #1 / 10

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 


Richard B #2 / 10

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 


Clark S. Cox I #3 / 10

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 base10: 15 * 12  30 15  180  Clark S. Cox III
http://www.whereismyhead.com/clark/

Mon, 26 Jan 2004 13:22:09 GMT 


Daniel Pfeffe #4 / 10

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 64bit integer is the largest supported by your compiler, you will have to decompose the operands into arrays of 32bit 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 twoscomplement 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 


Daniel Pfeffe #5 / 10

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


CBFalcone #6 / 10

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 64bit integer is the largest supported by your compiler, you > will have to decompose the operands into arrays of 32bit 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 


Nick Keighl #7 / 10

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 > base10:
<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 


Clark S. Cox I #8 / 10

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 > > base10: > <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 64bit numbers is just like multiplying two single digit, base10 numbers, except that each digit is a 64bit number. Basically, you're working in base18446744073709551616. 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 


Daniel Pfeffe #9 / 10

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 64bit integer is the largest supported by your compiler, you > > will have to decompose the operands into arrays of 32bit 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 doubleprecision 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 doubleprecision to calculate it. This defeats the purpose of the exercise. More efficient algorithms exist for multipleprecision multiplication, but they typically have too much overhead to be used for the doubleprecision case. Daniel Pfeffer

Fri, 30 Jan 2004 17:18:36 GMT 


CBFalcone #10 / 10

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 64bit integer is the largest supported by your compiler, you > > > will have to decompose the operands into arrays of 32bit 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 doubleprecision 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 doubleprecision 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 

