Department of Computer Science | Institute of Theoretical Computer Science

In [7]:

```
// collapsed code block to import library
import java.text.MessageFormat
```

You can open an interactive version of this document by logging into

https://and2022.jupyter.inf.ethz.ch/

You can use your nethz account to log into this server (same account as for your email at ETH).

The interactive document `notebooks_AD21-01_karatsuba.ipynb`

is hosted in the directory `/and2022/`

, which is shared with all students. You can run the code in the document and edit the document, but you cannot save it in this shared directory.

The material in this document is completely optional and not considered to be part of the course “Algorithmen und Datenstrukturen”. The aim of this document is to give you an idea how to translate high-level algorithmic ideas discussed in class to actual Java code. This Java code may use programming concepts that have not yet been covered in the course “Einführung in die Programmierung” at this time. The slides and recorded lectures for the “Vorkus” may serve as a useful reference.

At the above URL, you can interact with this Java code by modifying the inputs, running the code, and potentially modifying the code. You can always return to the original version of the document by closing the document, confirming that you wish to discard your changes, and opening the document again.

This document contains several hidden code cells. The code in these cells can safely be ignored.

If you view the interactive version of this document at the above URL, you first need to run all code cells before you can interact with the document.
In order to run all code cells invoke the command `Run -> Run All Cells`

in the menu bar.

input | output | operations |
---|---|---|

integers $a,b\in\mathbb N$ | product $c=a\cdot b$ | add / multiply digits |

The grade-school algorithm for integer multiplication proceeds in two steps:

- compute partial products by multiplying every digit of $a$ with every digit of $b$,
- sum up these partial products moved to the appropriate decimal position.

The following table illustrates for a concrete example how these two steps work.

$$ \begin{array}{rrrrr|l} a_1 & a_0 & & b_1 & b_0 \\ 6 & 5 & \cdot & 2 & 1 \\ \hline & & & & 5 & a_0 \cdot b_0 \\ & & & 6 & & a_1 \cdot b_0 \\ & & 1 & 0 & & a_0 \cdot b_1\\ & 1 & 2 & & & a_1 \cdot b_1\\ \hline & 1 & 3 & 6 & 5 & \end{array} $$

Can we do better?

What does it even mean for an algorithm to do better for this problem?

For starters, we will count the number of single-digit multiplications performed by the algorithm.

For the above example, we perform 4 single-digit multiplications (one operation for every partial product).

How many single-digit multiplications would this algorithm perform to multiply two 4-digit numbers?

**Answer**: 16 (again one operation for every partial product)

How many single-digit multiplications would the algorithm carry out to multiply two $n$-digit numbers?

**Answer**: $n^2$ (there are $n^2$ partial products because there are $n$ choices of digits for $a$ and $n$ choices of digits for $b$).

Is there a way to multiply two n-digit numbers with (significantly) fewer than $n^2$ single-digit multiplications?

Let us first consider the case $n=2$.

If we look at the mathematical identity that we used to justify the correctness of the grade-school algorithm, we see that we only need to know the following three numbers $$ a_0\cdot b_0, \quad a_1 \cdot b_1, \quad (a_0\cdot b_1 + a_1 \cdot b_0) $$

Naively, it takes two single-digit multiplications to compute the third number.

Could we compute the third number using just one single-digit multiplication?

In 1960, the Russian mathematician Anatoly Karatsuba discovered an algorithm to achieve that feat. His algorithm works by negating numbers and reusing the previously computed single-digit multiplications $a_0\cdot b_0$ and $a_1\cdot b_1$.

The following table illustrates how Karatsuba’s algorithm multiplies two 2-digit numbers using just three single-digit multiplications.

$$
\begin{array}{rrrrr|l}
a_1 & a_0 & & b_1 & b_0 \\
6&5& \cdot &2&1\\
\hline
& & & & 5 & a_0 \cdot b_0 \\
& 1 & 2 & & & a_1 \cdot b_1\\
& & 1 & 7 & & a_1\cdot b_1 + a_0 \cdot b_0\\
& & &-1 & & -(a_1-a_0)\cdot (b_1-b_0)\\
\hline
& 1 & 3 & 6 & 5 &
\end{array}
$$

This computation carries out exactly three single-digit multiplications, namely $$ a_0\cdot b_0, \quad a_1\cdot b_1, \quad (a_1-a_0)\cdot (b_1-b_0) \,. $$

Similarly to the grade-school algorithm, we can illustrate the correctness of this computation by a mathematical identity. Let us call the above products $u$, $v$, and $w$ (so that $u=a_0\cdot b_0$, $v=a_1\cdot b_1$, and $w=(a_1-a_0)\cdot (b_1-b_0)$). Then, the following mathematical identity illustrates the correctness of this computation, $$ (10 \cdot a_1 + a_0) \cdot (10\cdot b_1 + b_0) = u + (u+v-w)\cdot 10 + v \cdot 100 \,. $$

In [8]:

```
// collapsed code block to define a function to diplay the input, output, and intermediate values for Karatsuba's algorithm applied to 2-digit numbers
io.github.spencerpark.jupyter.kernel.display.DisplayData displayKaratsuba(int a0, int a1, int b0, int b1, int u, int v, int w, int c0, int c1, int c2, int carry0, int carry1, int carry2, int carry3, int d0, int d1, int d2, int d3) {
String s = """
<!-- parse as markdown -->
$$
'\\begin{array}{l|rrrr}'
& 3 & 2 & 1 & 0 \\\\
\\hline
a & & &{1}&{0}\\\\
b & & &{3}&{2}\\\\
\\hline
u & & & &{4}\\\\
v & &{5}& & \\\\
u & & &{6} & \\\\
v & & &{7} & \\\\
-w & & &{8}& \\\\
\\hline
c & &{11}&{10}&{9}\\\\
'\\mathtt{carry}' &{15}&{14}&{13}&{12}\\\\
d &{19}&{18}&{17}&{16}\\\\
'\\end{array}'
$$
""";
String m = MessageFormat.format(s,a0,a1,b0,b1,u,v,u,v,-w,c0,c1,c2,carry0,carry1,carry2,carry3,d0,d1,d2,d3);
return render(m,"text/markdown");
}
```

In [9]:

```
// Karatsuba's algorithm for n=2
// input values (feel free to change these values to any other valid input values)
int a1 = 6; int a0 = 5;
int b1 = 2; int b0 = 1;
// perform single digit multiplications
int u = a0 * b0;
int v = a1 * b1;
int w = (a1 - a0) * (b1 - b0);
// compute c0,c1,c2 such that a*b = c0 + 10*c1 + 100*c2
int c0 = u;
int c1 = u + v - w;
int c2 = v;
// extract decimal digits of c0 + 10*c1 + 100*c2
int carry0 = 0;
int d0 = (c0 + carry0)%10; int carry1 = (c0 + carry0)/10;
int d1 = (c1 + carry1)%10; int carry2 = (c1 + carry1)/10;
int d2 = (c2 + carry2)%10; int carry3 = (c2 + carry2)/10;
int d3 = carry3;
// display table with all input values, intermediate values, and output values
// (this code is just for illustration and not part of the algorithm)
displayKaratsuba(a0,a1,b0,b1,u,v,w,c0,c1,c2,carry0,carry1,carry2,carry3,d0,d1,d2,d3);
```

Out[9]:

$$ \begin{array}{l|rrrr} & 3 & 2 & 1 & 0 \\ \hline a & & &6&5\\ b & & &2&1\\ \hline u & & & &5\\ v & &12& & \\ u & & &5 & \\ v & & &12 & \\ -w & & &-1& \\ \hline c & &12&16&5\\ \mathtt{carry} &1&1&0&0\\ d &1&3&6&5\\ \end{array} $$

The following Java code serves to illustrate how Karatsuba’s algorithm works for inputs with more than 2 digits. We emphasize that this Java code is not a proper implementation of Karatsuba’s algorithm. In fact, this Java code turns out to be limited to inputs with at most 8 digits.

In [10]:

```
// collapsed code block to define a function to compute integer powers
// simple implementation to compute powers of integers
// caution: implementation doesn't terminate for negative values of n
long power(long a, long n) {
if (n == 0) {
return 1;
}
else {
return a*power(a,n-1);
}
}
```

In [11]:

```
// partial implementation of Karatsuba's algorithm for illustration purposes
long Karatsuba(long a,long b,long k, int depth) {
// assertion: the decimal representations of a and b each have at most 2^k digits
// print the values of a and b;
// indentation indicates depth of recursion
System.out.printf("%s%d*%d\n"," ".repeat(depth),a,b);
// base case: a and b are single-digit numbers
if (k==0) {
return a*b;
}
// compute p = 10^{2^{k-1}}
long p = power(10,power(2,k-1));
// compute highest 2^{k-1} digits of a and b
long a1 = a / p; long b1 = b / p;
// compute lowest 2^{k-1} digits of a and b
long a0 = a % p; long b0 = b % p;
// recursively compute the products a0*b0, a1*b1, (a1-a0)*(b1-b0)
long u = Karatsuba(a0,b0,k-1,depth+1);
long v = Karatsuba(a1,b1,k-1,depth+1);
long w = Karatsuba(a1 - a0,b1 - b0,k-1,depth+1);
// combine the results to obtain the product a*b
return u + p*(u+v-w) + p*p*v;
}
```

In [12]:

```
// illustration of Karatsuba's algorithm
// inputs (limite to 8 digit numbers)
long a = 67223345L;
long b = 84343592L;
// number of digits of inputs
long n = (long)Math.ceil(Math.max(Math.log10(a),Math.log10(b)));
// smallest integer k such that both a and b have at most 2^k digits
long k = (long)(Math.log(n)/Math.log(2));
// run Karatsuba's algorithm to multiply a and b
long result = Karatsuba(a,b,k,0);
System.out.printf("Output of Karatsuba's algorithm: %d\n", result);
System.out.println("Check standard multiplication has same output:");
result == a*b;
```

67223345*84343592 3345*3592 45*92 5*2 4*9 -1*7 33*35 3*5 3*3 0*-2 -12*-57 -2*-7 -1*-5 1*2 6722*8434 22*34 2*4 2*3 0*-1 67*84 7*4 6*8 -1*4 45*50 5*0 4*5 -1*5 3377*4842 77*42 7*2 7*4 0*2 33*48 3*8 3*4 0*-4 -44*6 -4*6 -4*0 0*-6 Output of Karatsuba's algorithm: 5669858383555240 Check standard multiplication has same output:

Out[12]:

true