In C multiplication overflow is ignored. If one multiplies two 32-bit numbers, and the result is larger than 32-bits the upper bits go into the bit bucket. As long as the result will fit into 32-bits, nothing is lost. If the result will be larger than 32-bits, one must use 64-bit data types. However, as of 2011 the C standard has no integer data types larger than 64-bit. So if larger numbers are desired one either has to use floating-point, or make their own multiply. At work this month I ran into a problem where I needed to multiply two 64-bit numbers that would overflow a 64-bit result. After the work day was complete, I wrote a simple function to do this, and we will examine how it works in this article.
When doing multiplication of binary numbers, the result will never be larger than twice the number of bits of the data types used. That is, two 32-bit numbers multiplied together will never have a result larger than 64-bits. The reason can be expressed mathematically.
Where n is the number of bits.
So when multiplying two 64-bit values it is known the result will always fit into a 128-bit. We can construct this result using two 64-bit values—an upper word and a lower word.
Doing the multiplication one has to think back to their grade school days and long multiplication. Let us first solve a simple problem doing long multiplication to solve 12x34.
|
1 |
2 |
|
|
3 |
4 |
|
|
4 |
8 |
|
|
3 |
6 |
0 |
|
4 |
0 |
8 |
The steps are to first multiply the least-significant digits of the 34 by the least-significant digit of 12 (in this case 4 and 2) and place the result in the left most column. Then the most-significant digits of 34 by the least-significant digit of 12 (3 and 2) and place that in the second column from the left. Next is the most-significant digit of 34 by the least-significant of 12 (3 and 2) which is stored in the second column from the left, and lastly the most-significant digit of 34 by the most-significant digit of 12 (3 and 1) which is stored in the third column from the left. Sum the two results with carries and we have our end result.
These steps are precisely what is needed in order to multiply two 64-bit numbers. But rather than digits, each column will represent 32-bits. If you still think of each column as a digit, the following chart is an algebraic representation of the above. To change to 32-bits just consider that rather than each column counting from 0 to 9 before carrying the digit to the next column, it counts from 0 to 232 – 1 before carrying to the next column.
|
au |
al |
|
|
bu |
bl |
|
|
bl*au |
bl*al |
|
|
bu*au |
bu*al |
0 |
Here au is the upper 32-bits of the first word (a), and al is the lower 32-bits. The only problem with looking at the setup this way is that it does not show the word sizes. So let us arrange things like this:
|
au |
al |
||
|
bu |
bl |
||
|
bl*al |
|||
|
bl*au |
|||
|
bu*al |
|||
|
bu*au |
|||
Now we can see that the results of the multiplications are twice the width of the two values being multiplied, and how that lines up with the other values in the finial summation. Again, each column is 32-bits and the four total columns means we have a 128-bit result. We split the input into two 32-bit numbers so that each individual multiplication never has a result larger than 64-bits. This way there is never an overflow. The trade off is that we now have to do 4 multiplications and several additions.
So here is the source code for doing the multiplication.
// Name: mult128.h
// Uses: 128-bit multiplication using 64-bit input.
// Date: 2013/12/08
// Author: Andrew Que (http://www.DrQue.net/)
// Compiler: C99 compliant.
// Revision:
// 1.0 - 2013/12/08 - Creation.
//
// Public domain
//******************************************************************************
#ifndef MULT128_H
#define MULT128_H
#include <stdint.h>
// 128-bit unsigned integer.
typedef struct
{
uint64_t upper;
uint64_t lower;
} UINT128;
//------------------------------------------------------------------------------
// USES:
// Multiply two 64-bit unsigned integers to form valueA 128-bit result.
// INPUT:
// valueA - First multiplicand.
// valueB - Second multiplicand.
// OUTPUT:
// 128-bit unsigned integer of multiply.
//------------------------------------------------------------------------------
static inline UINT128 multiply_uint128( uint64_t valueA, uint64_t valueB )
{
int const SHIFT = 32;
uint64_t const MASK = 0xFFFFFFFF;
UINT128 result;
uint64_t product[ 4 ];
uint64_t multiply;
//
// Product is taken by dividing each 64-bit word into two 32-bit, and doing
// multiplication on the parts.
// a b <- Upper/lower word of 'ValueA'
// * c d <- Upper/lower word of 'ValueB'
//
// The complete multiply is then the sum of each of the parts. Each
// multiplication spans two words of the result as such:
// [3] [2] [1] [0] <- Resulting full product, held in 'product'.
// [b * d]
// [a * d]
// [b * c]
// [a * c]
//
// b * d
multiply = ( valueA & MASK ) * ( valueB & MASK );
product[ 0 ] = ( multiply & MASK );
// a * d
multiply = ( valueA >> SHIFT ) * ( valueB & MASK ) + ( multiply >> SHIFT );
product[ 1 ] = ( multiply & MASK );
product[ 2 ] = ( multiply >> SHIFT );
// b * c
multiply = product[ 1 ] + ( valueA & MASK ) * ( valueB >> SHIFT );
product[ 1 ] = ( multiply & MASK );
// a * c
multiply = product[ 2 ] + ( valueA >> SHIFT ) * ( valueB >> SHIFT ) + ( multiply >> SHIFT );
product[ 2 ] = ( multiply & MASK );
product[ 3 ] = ( multiply >> SHIFT );
// Store result.
result.upper = ( product[ 3 ] << SHIFT ) | product[ 2 ];
result.lower = ( product[ 1 ] << SHIFT ) | product[ 0 ];
return result;
}
#endif // MULT128_H
There you have it. The code is easily adapted to other integer sizes. By changing the types to uint32_t, and the mask and shift values this function could produce a 64-bit result. C already has built in support for 64-bit types, but it could be done nonetheless.
The source code is here.