\documentclass[11pt]{article}
\begin{document}
%%%%% written in LaTeX %%%
\addtolength{\oddsidemargin}{-1.25cm}
\addtolength{\textwidth}{3cm}
\addtolength{\textheight}{4cm}
\addtolength{\topmargin}{-2cm}
\newcommand{\een}{\end{enumerate}}
\newcommand{\noi}{\noindent}
\newcommand{\ra}{\rightarrow}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\hsc}{\hspace*{3cm}}
\newcommand{\sig}{\sigma}
\newcommand{\eps}{\epsilon}
\newcommand{\del}{\delta}
\newcommand{\Del}{\Delta}
\newcommand{\lam}{\lambda}
\newcommand{\ah}{\alpha}
\newcommand{\gam}{\gamma}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bec}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{define}{Definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[theorem]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{guess}[theorem]{Conjecture}
\bec {\bf Karatsuba's Algorithm}\ece
\noi Object: To multiply two (roughly) $n$-digit numbers.
\noi {\tt Numbers:} Numbers are represented as arrays $A[0\cdots N]$ with
$A[I]$ is the $I$-th digit, starting the count at the right with $A[0]$.
Thus $904$ is represented as $A[0]=4$, $A[1]=0$, $A[2]=9$. (We'll do
examples in decimal but in the computer it is usually in binary.)
\noi {\tt Addition:} Given $A[0\cdots N]$, $B[0\cdots N]$ we find their
sum $C[0\cdots (N+1)]$ by the ``standard" method learned at age eight.
\\ CARRY=0 (*initialization*)
\\ FOR I= 0 TO N+1
\\ \hsa C[I]=A[I]+B[I]+CARRY
\\ \hsa IF C[I]$\leq$ 9 do
\\ \hsb CARRY = 0
\\ \hsa ELSE do (*C[I]$\geq$ 10*)
\\ \hsb CARRY =1
\\ \hsb C[I] = C[I] - 100
This takes a single pass and is a $\Theta(n)$ algorithm.
Subtraction (a good exercise!) is similar, and also a
linear time, that is $\Theta(n)$, algorithm.
The idea of Karatsuba's Algorithm is to take two $n$-digit
numbers $\ah,\beta$ and to cut them (thinking of them as
strings of digits) in half, writing (assume $n$ even for
convenience)
\[ \ah = 10^{n/2}x + y \]
\[ \beta = 10^{n/2}z + w \]
We want the product $\gamma=\ah\beta$ and
\[ \gamma = 10^n(xz) + 10^{n/2}(xw+yz)+ yw \]
(Note that multiplying by $10^n$ or $10^{n/2}$ is not ``real"
multiplication but just string manipulation and so is very quick.)
It looks like we want to do four multiplications $xz,xw,yz,yw$ of
$n/2$-digit numbers. But here is the clever idea:
\ben
\item Find $xz$. (multiply two $n/2$-digit numbers)
\item Find $yw$. (multiply two $n/2$-digit numbers)
\item Find $x+y$. (Addition, time $\Theta(n)$.)
\item Find $z+w$. (Addition, time $\Theta(n)$.)
\item Find $(x+y)(z+w)$ (multiply two $n/2$-digit\footnote{maybe one
more digit but that will have negligible affect} numbers)
\item Find $xw+yz = (x+y)(z+w)-xz-yw$ (Two subtractions, time $\Theta(n)$)
\item Put parts together to get $\gamma$ (Two additions, time $\Theta(n)$)
\een
The calls to multiply the smaller numbers are done {\bf recursively}.
Letting $T(n)$ be the time for Karatsuba's algorithm the
key point is that there are only {\em three} recursive calls and
an ``overhead" of $\Theta(n)$. So we have the recursion
\[ T(n) = 3T(n/2)+ \Theta(n) \]
From the Master Theorem
\[ T(n) = \Theta(n^{1.58\cdots}) \]
where the exact exponent is $\frac{\lg 3}{\lg 2}$.
So this is better (of course, in this course by ``better" we mean
faster for $n$ large) than the normal $\Theta(n^2)$ algorithm learned
at age eleven.
\end{document}