Q3: Divide and conquer for multiplication

Consider the representation of an $n$ -digit decimal number using an array of $n$ elements, with one digit stored in each array element. For example, 512 is stored in an array $a$ with: $a[2] = 5, a[1] = 1, a[0] = 2$ . (Note that the least significant digit is stored in $a[0]$ .)

Here is a divide and conquer strategy for multiplying two numbers stored in $a$ and $b$ .

1. Input: Two arrays $a$ and $b$ of size $n$ representing two integers.
2. If $n = 1$ multiply the digits and return the value.
3. $(a_L,a_R)$ = (leftmost $\lceil n/2 \rceil$ ,rightmost $\lfloor n/2 \rfloor$ ) digits of $a$ .
   $(b_L,b_R)$ = (leftmost $\lceil n/2 \rceil$ ,rightmost $\lfloor n/2 \rfloor$ ) digits of $b$ .
   
4. $P1 = multiply(a_L,b_L)$
5. $P2 = multiply(a_R,b_R)$
6. $P3 = multiply(a_L+a_R,b_L+b_R)$
7. return $P1*10^n + (P3-P1-P2)*10^{n/2} + P2$

Show that the above strategy requires $O(n^{\log{3}})$ steps. Write an imperative program based on the above idea.

You may write the program in any language of your choice. However it may be simplest to complete this Python program template.