This short article shows how to implement the multiplication of two unsigned 32 bit values (resulting in an unsigned 64bit value) using 16 bit multiplication, type casts and shift operations.
Beside the fact that it's interesting, this could be really handy on some low power microcontrollers that do not support this multiplication instruction in hardware.
The main idea is to split a 32bit unsigned value into two parts: the upper 16 bits (value with base 216) and the lower 16 bits.
Having a value va, we can write it as:
va = ha * 216 + la
The value 0x12345678 can be written as: 0x1234 * 216 + 0x5678 = 0x1234 < <16 + 0x5678.
So here ha = 0x1234 and la = 0x5678.
So having two values va = ha << 16 + la and vb = hb << 16 + lb, the multiplication is derived as follows:
= ((ha << 16) + la) * ((hb << 16) + lb)
= (ha << 16) * (hb << 16) + (ha << 16) * lb + la *(hb << 16) + la * lb
= ((ha * hb) << 32) + (ha << 16) * lb + la *(hb << 16) + la * lb
Remember that left-shift by 16 is the same as the multiplication by 216 so (ha << 16) * (hb << 16) = ha * 216 * hb * 216 = ha * hb * 232 = (ha * hb) << 32.
Note that here only 16x16 multiplications (resulting in 32bit values) and shifts are used, but no native 32x32 multiplication.
Here a straight-forward implementation in C:
uint16_t va_high = (a >> 16) & 0xFFFF;
uint16_t va_low = a & 0xFFFF;
uint16_t vb_high = (b >> 16) & 0xFFFF;
uint16_t vb_low = b & 0xFFFF;
uint64_t mul_high_high = (uint64_t)((uint32_t)(va_high * vb_high))<< 32;
uint64_t mul_high_low = (uint64_t)((uint32_t)(va_high << 16)) * vb_low;
uint64_t mul_low_high = (uint64_t)((uint32_t)(vb_high << 16)) * va_low;
uint32_t mul_low_low = (uint32_t)(va_low * vb_low);
uint64_t res = 0;
res = mul_high_high;
res += mul_high_low;
res += mul_low_high;
res += mul_low_low;
Here an example to calculate it manually:
va_high = 0x00011111 >> 16 = 0x0001
va_low = 0x00011111 & 0xFFFF = 0x1111
vb_high = 0x33445566 >> 16 = 0x3344
vb_low = 0x33445566 & 0xFFFF = 0x5566
mul_high_high = (0x0001 * 0x3344) << 32 = 0x334400000000
mul_high_low = (0x0001 << 16) * 0x5566 = 0x00010000 * 0x5566 = 0x55660000
mul_low_high = (0x3344 << 16) * 0x1111 = 0x33440000 * 0x1111 = 0x36AEB840000
mul_low_low = 0x1111 * 0x5566 = 0x5B171C6
result = 0x334400000000 + 0x55660000 + 0x36AEB840000 + 0x5B171C6 = 36AF469B71C6
Sunshine, November 2017