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.

## Theory

The main idea is to split a 32bit unsigned value into two parts: the upper 16 bits (value with base 2^{16}) and the lower 16 bits.

Having a value *va*, we can write it as:

va = ha * 2^{16} + la

The value 0x12345678 can be written as: 0x1234 * 2^{16} + 0x5678 = 0x1234 < <16 + 0x5678.

So here ha = 0x1234 and la = 0x5678.

## Algorithm

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 2^{16} so (ha << 16) * (hb << 16) = ha * 2^{16} * hb * 2^{16} = ha * hb * 2^{32} = (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;

return res;

}

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