Binary Multiplication Result Size Length

Question

I am trying to understand why multiplying two binary numbers of size L gives a resulting sized number of O(2L),

Is it becuase the 'worst case'/maximum size possible is 2L ? Which is when the two numbers are the same ? Or is that not the worst case ?

Thank you

Answer 1

Here is an answer based on the use of logarithm (base $2$).

Let us introduce first notations :

• 1) $lg$ for "binary logarithm",

• 2) $\verb|#|(x)$ for the number of binary digits (bits) of $x$.

• 3) $\lfloor ... \rfloor$ for "function "floor" or "integer part", the largest integer less or equal to $...$ (for example $\lfloor 2.7 \rfloor=2, \ \ \lfloor 3 \rfloor = 3, \ \ \lfloor 3.1 \rfloor=3$). We have in particular the following inequalities :

$$\lfloor x \rfloor + \lfloor y \rfloor \ \ \leq \ \ \lfloor x+y \rfloor \ \ \leq \ \ \lfloor x \rfloor + \lfloor y \rfloor + 1 \tag{1}$$

(see (https://en.wikipedia.org/wiki/Floor_and_ceiling_functions)).

We can write double inequality (1) under the following form :

$$\lfloor x+y \rfloor \ \ = \ \ \lfloor x \rfloor + \lfloor y \rfloor + c \ \ \text{with} \ c = 0 \ \text{or} \ 1. \tag{2}$$

The basic result we use is :

$\verb|#|(A) \ = \ \lfloor lg(A) \rfloor + 1 \tag{3}$

(I am indebted to Daniel Fischer for this closed form expression ; I had previously this one : $\verb|#|(A) \ = \ \lceil lg(A) \rceil$ which is almost the same but for numbers of the form $2^n, \ n \in \mathbb{N}$.)

With words : the number of binary digits (before the point) of the binary decomposition of a real number $A$ is equal to the integer part of its binary logarithm + one.

Example :

$$\begin{cases}lg(1023)&=&9.9985..., \\ lg(1024)&=&lg(2^{10})=10, \\ lg(1025)&=&10.0014...\end{cases}$$

or, in its binary version :

$$\begin{cases}lg(\underbrace{111111111}_{10 \ binary \ digits}.0)&=&9.9985..., \\ lg(\underbrace{1000000000}_{11 \ binary \ digits}.0)&=&10.0000 \ = \ lg(2^{10}), \\ lg(\underbrace{1000000001}_{11 \ binary \ digits}.0)&=&10.0014...\end{cases}$$

Now consider 2 numbers $A$ and $B$ and their logarithms ; using (2) and adding 1 : $$\lfloor \underbrace{lg(A)+lg(B)}_{lg(A \times B)} \rfloor + 1 \ \ = \ \ (\lfloor lg(A) \rfloor + 1) + (\lfloor lg(B) \rfloor + 1) + c-1 \ \ \text{with} \ c = 0 \ \text{or} \ 1. \tag{4}$$

Which can be interpreted, using (3), in the following manner :

$$\verb|#|(A \times B) = \verb|#|(A) + \verb|#|(B) + d \ \ \ \text{where} \ \ d =-1 \ \text{or} \ 0.$$

If the number of digits of $A$ and $B$ is the same, equal to $n$, we can write:

$$\verb|#|(A \times B) \ = \ 2n-1 \ \text{or} \ 2n$$

In both cases, it is a $2 \times O(n)$ (space) complexity.

Here is a graphical representation showing intuitively why 2 numbers with $n$ digits add up to a number of either $2n-1$ digits (case of triangle $SPQ$) or $2n$ digits (case of triangle $QRS$):

We use for that a logarithmic scale adapted to base $2$; Let us consider the case of $n=3$, i.e., when we add up integer numbers $A$ and $B$, each one having 3 binary digits = 3 bits. This is the meaning of the arrows : for $A$, considered as being on the axis of abscissas, we choose one of the four numbers

$$4 = '100', \ \ \ 5='101', \ \ \ 6 = '110' \ \ or \ \ 7='111' ;$$

The same for B on the axis of ordinates.

Then, if point with coordinates $(A,B)$

• is situated into triangle $SPQ$ (example '101' \times '101'= '11110') we have a result with $2n-1 = 5$ bits, whereas if it

• is situated into triangle $QRS$ (example '111' \times '101'= '100011') we have a result with $2n = 6$ bits.

(all this is easily explainable by interpreting the stripes as locii of results that have such and such number of digits in the product of coordinates)

Fig(1).

Fig. 1 should be understood as a transformation of multiplication tables in which can be seen families of hyperbolas with equation $xy=k, \ k$ constant (see Fig. 8.5 of this interesting document, transformed into straight lines with equation $X+Y=lg(k)$ in logarithmic coordinates $X=lg(x), \ Y=lg(y)$.

Answer 2

The worst case occurs when both of the two binary numbers consist of $L$ $1$'s in the binary expansion (and no zeroes). For example,

$$(1111)_{2} \cdot (1111)_{2} = (11100001)_{2}. $$

Note that both of the numbers start with $4$ digits, but we end up with a number that has $8$ digits.

Answer 3

If you are using unsigned binary, the largest number that fits in $L$ bits is $2^L-1$, for $L \geq 1$. If you square that, you get $2^{2L}-2^{L+1}+1$, which has $2L$ bits. The smallest number that requires $L$ bits is $2^{L-1}$. If you square that, you get $2^{2L-2} = 2^{(2L - 1) -1}$, which requires $2L-1$ bits. In the usual use of big O notation, either one would be $O(L)$ because the multiplicative constant of $2$ is ignored.