Magical Algorithms 01 -- Multiplication

An algorithm in mathematics and computer science refers to a finite sequence of mathematically rigorously defined operations, usually used to execute certain operations or to perform some computational tasks. Among them, I think many algorithms are very fun and worth sharing. This series aims to introduce some very interesting algorithms to everyone in the most understandable language, for the reference of interested students.

Simple Algorithm Analysis

Analysis of algorithms refers to the complexity analysis of a certain algorithm, usually including time complexity and space complexity. Complexity refers to the growth trend of an algorithm’s consumption of a certain resource as the size of the input grows.

For example:

• If the time complexity of an algorithm is linear, we can assume that when the size of input doubles, the running time of the algorithm will also roughly double.
• If the time complexity of an algorithm is quadratic, we can assume that when the size of input doubles, the running time of the algorithm will roughly quadruple ($(2n)^2 = 4n^2$).

To precisely describe the complexity of an algorithm, we can define the following notations. First, we define two functions $f, g$:

• If $f = O(g)$, then $\exists C, \text{s.t. } f <= C\cdot g$
• If $f = o(g)$, then $\lim_{n \to \infty}\frac{f(n)}{g(n)} = 0$
• If $f = \Omega(g)$, then $g = O(f)$
• If $f = \omega(g)$, then $g = o(f)$
• If $f = \Theta(g)$, then $f = O(g)$ and $f = \Omega(g)$

Intuitively speaking:

• $f = O(g)$ means the growth rate of $f$ is less than or equal to $g$
• $f = o(g)$ means $f < g$
• $f = \Omega(g)$ means $f \ge g$
• $f = \omega(g)$ means $f > g$
• $f = \Theta(g)$ means $f = g$

Multiplication

Now, let’s discuss an algorithm that we are all very familiar with – Multiplication. The multiplication we discuss here refers to the multiplication between two $n$-digit decimal integers, assuming the multiplication complexity between two single-digit numbers is $O(1)$, and the addition complexity between two $n$-digit numbers is $O(n)$.

Algorithm I

Let’s first discuss the simplest multiplication algorithm: the product $C$ of two $n$-digit integers $A \times B$ equals the sum of $B$ anounts of $A$. The pseudocode is as follows:

def mul(A, B): 
  C = 0
  for i in range(B):
    C = C + A
  return C

Let’s analyze the time complexity of this algorithm! Firstly, $C$ won’t exceed a $2n$-digit integer at its maximum, so C + A can be seen as an algorithm with $O(2n)$ time complexity. And $O(2n) = O(n)$ (constants don’t affect the growth rate, so from now on, constants can be ignored when calculating time complexity).

Meanwhile, $B < 10^n$, so the overall time complexity of this algorithm is $O(10^n \cdot n)$

This also means that if the input size $n$ doubles, the required time approximately multiplies by $200$. Omggg! This algorithm is so junk!

Algorithm II

Obviously, the multiplication algorithm we learned in elementary school, vertical calculation, is much more convenient than this.

      1234
 *    5678
 ---------
      9872 <-- O(n)
     8638  <-- O(n)
    7404   <-- O(n)
 + 6170    <-- O(n)
 ---------
   7006652 <-- O(n)

From this, the algorithm’s time complexity is $O(n^2 + n)$. Since the term $n$ has a smaller growth rate than $n^2$, therefore

From now on, when considering complexity, we only need to consider the largest term.

Can we do better?

Algorithm III

Of course, we can! Next, we’re going to do something seemingly weird: divide $A, B$ into two equal parts in length

Therefore

What did we find?

We converted the product of an $n$-digit number into the sum of four products of $\frac{n}{2}$-digit numbers! Thus:

At the same time, $T\left(\frac{n}{2}\right)$ can be further decomposed, forming a recursive structure. Isn’t this just a sequence problem!

Where $k = \log_2 n$

????? This algorithm is still $O(n^2)$? Was all that analysis for nothing?

But, we actually don’t need the sum of four products. Because what we need is $A_{hi}B_{lo} + A_{lo}B_{hi}$, and we don’t need to find out their respective values!

Therefore, we only need to secure:

• $P_1 = A_{hi}B_{hi}$
• $P_2 = A_{lo}B_{lo}$
• $P_3 = (A_{hi} + A_{lo})(B_{hi} + B_{lo})$

And $A_{hi}B_{lo} + A_{lo}B_{hi} = P_3 - P_2 - P_1$

Therefore! The recurrence formula transforms into

Ultimately yielding

The pseudocode is as follows:

 def mul(A, B, n):
     if n == 1: 
         return A * B # O(1)
     else: 
         Ahi, Alo = A // 10 ** (n/2), A % 10 ** (n/2) # O(n)
         Bhi, Blo = B // 10 ** (n/2), B % 10 ** (n/2) # O(n)
 
         P1 = mul(Ahi, Bhi, n/2) # T(n/2)
         P2 = mul(Alo, Blo, n/2) # T(n/2)
        P3 = mul(Ahi + Alo, Bhi + Blo, n/2) # T(n/2)

        return P1 * 10 ** n + (P3 - P1 - P2) * 10 **(n/2) + P2 # O(n), because multiplying or dividing by 10 is very easy to calculate 

Final Words

This is my first attempt at writing an article like this, feel free to private message me your thoughts, and I will listen to your advice attentively. Thanks again for your support.