On Overflow of Unsigned Integer Multiplication

Yue LI

Date: May 7, 2023

The x86 unsigned multiplication instruction MUL multiplies RAX with some quadword and stores the result in RDX:RAX. The overflow flag OF and carry flag CF are set if the high-order bits of the result, which are stored in RDX, are non-zero. The notion of overflow applicable to the MUL instruction is therefore that multiplication of two $n$-bit (unsigned) integers has a result that is longer than $n$ bits. Taking into account that MUL actually uses $2n$ bits to store the result of multiplication of two $n$-bit numbers, in this blog we ask and answer a different overflow question: is it possible that multiplying two n-bit unsigned integers and the result is longer than 2n bits?

We shall answer negatively, and prove the following Proposition.

Proposition 1   For all $n=1,2,3,\ldots$, the result of multiplication of two unsigned n-bit integers has at most $2n$ bits.

Since an all-ones, like 11111111111, is the largest $n$-bit unsigned integer for every $n$, if we can show that two $n$-bit all-ones multiply and the result is no more than $2n$ bits, then the Proposition easily follows.

Lemma 1   For all $n=1,2,3,\ldots$, the square of the largest n-bit unsigned integer has at most $2n$ bits.

Our proof for the Lemma is inductive, but before examining the formal arguments, let's warm up by looking at some particular cases.

Pattern Discovery for Induction

Below we show that the Lemma holds for $1\leq n\leq 6$. We shall use sum of powers of 2 to denote an unsigned binary integer, then e.g. 1111 is $2^3+2^2+2^1+2^0$. Equation 1 shows that $1^2$ has 1 bit.

$$(2^0)^2=2^0$$ (1)

Next, when building Equation 2 we use Equation 1 (as underlined).

$$(2^1+2^0)^2$$

$$=\ (2^1)^2+2\cdot2^1\cdot2^0+\underline{(2^0)^2}$$

$$=\ (2^2+2^2)+\underline{2^0}_{\mbox{ by (\ref{eq0})}}$$

$$=\ 2^3+2^0$$ (2)

Equation 2 shows that $11^2$ has 4 bits. Next, when building Equation 3 we use Equation 2.

$$(2^2+2^1+2^0)^2$$

$$=\ (2^2)^2+2\cdot2^2(2^1+2^0)+\underline{(2^1+2^0)^2}$$

$$=\ 2^4+2^3(2^1+2^0)+\underline{2^3+2^0}_{\mbox{ by (\ref{eq1})}}$$

$$=\ (2^4+2^4)+(2^3+2^3)+2^0$$

$$=\ 2^5+2^4+2^0$$ (3)

Equation 3 shows that $111^2$ has 6 bits. Next, when building Equation 4 we use Equation 3.

$$(2^3+2^2+2^1+2^0)^2$$

$$=\ (2^3)^2+2\cdot2^3(2^2+2^1+2^0)+\underline{(2^2+2^1+2^0)^2}$$

$$=\ 2^6+2^4(2^2+2^1+2^0)+\underline{2^5+2^4+2^0}_{\mbox{ by (\ref{eq2})}}$$

$$=\ (2^6+2^6)+(2^5+2^4)+(2^5+2^4)+2^0$$

$$=\ 2^7+2^6+2^5+2^0$$ (4)

Equation 4 shows that $1111^2$ has 8 bits. Next, when building Equation 5 we use Equation 4.

$$(2^4+2^3+2^2+2^1+2^0)^2$$

$$=\ (2^4)^2+2\cdot2^4(2^3+2^2+2^1+2^0)+\underline{(2^3+2^2+2^1+2^0)^2}$$

$$=\ 2^8+2^5(2^3+2^2+2^1+2^0)+\underline{2^7+2^6+2^5+2^0}_{\mbox{ by (\ref{eq3})}}$$

$$=\ (2^8+2^8)+(2^7+2^6+2^5)+(2^7+2^6+2^5)+2^0$$

$$=\ 2^9+2^8+2^7+2^6+2^0$$ (5)

Equation 5 shows that $11111^2$ has 10 bits. Next, when building Equation 6 we use Equation 5.

$$(2^5+2^4+2^3+2^2+2^1+2^0)^2$$

$$=\ (2^5)^2+2\cdot2^5(2^4+2^3+2^2+2^1+2^0)+\underline{(2^4+2^3+2^2+2^1+2^0)^2}$$

$$=\ 2^{10}+2^6(2^4+2^3+2^2+2^1+2^0)+\underline{2^9+2^8+2^7+2^6+2^0}_{\mbox{ by (\ref{eq4})}}$$

$$=\ (2^{10}+2^{10})+(2^9+2^8+2^7+2^6)+(2^9+2^8+2^7+2^6)+2^0$$

$$=\ 2^{11}+2^{10}+2^9+2^8+2^7+2^0$$ (6)

Equation 6 shows that $111111^2$ has 12 bits.

Formal Inductive Proof

Based on Equations 1–6, it is reasonable to conjecture that for all $n=0,1,2,3,\ldots$,

$$(2^n+2^{n-1}+\cdots+2^0)^2=2^{2n+1}+2^{2n}+\cdots+2^{n+2}+2^0.$$ (7)

Note that on both sides of Equation 7 the powers of 2 are in descending order, so that the right hand side is instantiated by $2^0$ when $n=0$, by $2^3+2^0$ when $n=1$ and by $2^5+2^4+2^0$ when $n=2$, and so on.

Based on how we progress from Equation 1 to 6, we have the following scheme of progression from the square of sum up to $n$-th power of 2, to the square of sum up to $(n+1)$-th power of 2.

$$(2^{n+1}+2^n+\cdots+2^0)^2$$

$$=\ (2^{n+1})^2+2\cdot2^{n+1}(2^n+2^{n-1}+\cdots+2^0)+\underline{(2^n+2^{n-1}+\cdots+2^0)^2}$$

$$=\ 2^{2(n+1)}+2^{n+2}(2^n+2^{n-1}+\cdots+2^0)+\underline{2^{2n+1}+2^{2n}\cdots+2^{n+2}+2^0}_{\mbox{ by (\ref{eq6})}}$$

$$=\ \left(2^{2(n+1)}+2^{2(n+1)}\right)+(2^{2n+1}+\cdots+2^{n+2})+(2^{2n+1}+\cdots+2^{n+2})+2^0$$

$$=\ 2^{2(n+1)+1}+2^{2(n+1)}+\cdots+2^{(n+1)+2}+2^0$$ (8)

Based on the facts that Equation 1 holds, and that for all $n=0,1,2,3,\ldots$, if Equation 7 holds then Equation 8 holds, we can justly conclude that our conjecture that for all $n=0,1,2,3,\ldots$ Equation 7 holds, is true. This proves our Lemma. Then the Proposition follows.

About this document ...

On Overflow of Unsigned Integer Multiplication

This document was generated using the LaTeX2HTML translator Version 2019.2 (Released June 5, 2019)

The command line arguments were:
latex2html -no_navigation -split 0 MUL.tex

The translation was initiated on 2023-05-07