Unsigned 32x32 bit multiplication

Download C source code (24 kb)

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 216) and the lower 16 bits.
Having a value va, we can write it as:
va = ha * 216 + la

Example:

The value 0x12345678 can be written as: 0x1234 * 216 + 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:

va * vb
= ((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:

uint64_t mymul32x32(uint32_t a, uint32_t b)
{
  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:

Example: Multiply the values 0x00011111 (decimal: 69905) and 0x33445566 (decimal: 860116326), result is 0x36AF469B71C6 (60126431769030)

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