Karatsuba Multiplication

When we were kids, teachers taught us how to multiply. My generation probably was taught the standard multiplication algorithm. That is, take the first digit, multiply out the second number's digits one by one with carry, then repeat for every digit of the first number, and remembering to shift correctly.

On a side note, the "newer" younger math generation are sometimes taught weird things. The logic behind it is giving a chance for the kids to develop a sense of "why" of how the multiplication algorithm works, and make it easier for more kids to understand. I think it's retarded. Kids don't give a shit why this works, except young Gauss and other great ones. Anyways...

We are so familiar with multiplication, having done it for years and years before having access to the calculator at school, that we don't really think about: is there a faster way? What if we had two numbers with a 1024 digits each?

Multiplying it out with the standard algorithm, we would have to carry $1024^2$ multiplications, and then another $1024^2$ digit additions.

So can you think of a better way to multiply? Well, Komolgorov, a prominent mathematician, a pioneer of computational complexity, analysis and probability theory, conjectured (yes conjectured, because he was so convinced) in 1952 that there is no way of doing considerably better than that simple algorithm (meaning better than $\mathcal{O}(n^2)$ digit operations). In 1960, he announced his conjecture in a seminar on computational complexity, and a few days later, a student by the name of Karatsuba came up with an algorithm that was strictly better than standard multiplication. Needless to say, it was quite an embarrassing event for Komolgorov.

Curiously enough, this algorithm is extremely simple. The idea goes as follows:

Given a multiplication $a\cdot b$, we can rewrite $a = a_110^m + a_0$ and $b = b_110^m + b_0$ where we choose an $m$ that will cut the digits of $a$ and $b$ in the middle more or less. Now we notice that $a\cdot b = a_1b_110^{2m} + (a_1b_0 + a_0b_1)10^m + a_0b_0$. Now we still haven't done anything new. This is still what standard multiplication is doing. Karatsuba noticed that we can find $(a_1b_0 + a_0b_1)$ in not 2, but 1 multiplication step. The trick, $(a_1b_0 + a_0b_1) = (a_1+a_0)(b_1+b_0) - a_1b_1 - a_0b_0$. Since we already computed $a_1b_1$ and $a_0b_0$, we only have to multiply out the first term.

Ok, how is this so much better than standard multiplication? Informally, if we recursively apply this trick to compute $(a_1+a_0)(b_1+b_0)$, $a_1b_1$ and $a_0b_0$, we get a "multiplication tree" of depth $\mathcal{O}(\log(n))$ with each node branching into 3 subnodes. Standard multiplication has an extra multiplication step, so each node branches into 4 subnodes. This extra subnode obviously compounds rapidly at every layer.

Returning to our first example, multiplying two numbers with 1024 digits with this method takes $3^{10} = 59049$ digit multiplications instead of $1024^2 = 4^{10} = 1048576$.

What about the extra addition steps? Well, you can convince yourself that the addition steps from having more multiplication steps will blow up anyways.

Conclusion: Karatsuba Multiplication takes order $\mathcal{O}(n^{\log_23})$ digit multiplications, and should be used to multiply numbers with more than around 200 digits.

For more recent developments, algorithms have been found to do even better than Karatsuba's, but they involve much heavier mathematical artillery such as Fast Fourier Transforms.

Happy Halloween!

[DM]

First math post: Interpolation

This post really is to test out LaTeX formatting, but I found interpolation somewhat slightly interesting.

So, the motivation for interpolation goes: How do you fit a n-degree polynomial to a set of n+1 data points?... Ok, it's not very motivating... I actually can't think of a reason to fit a n-degree polynomial to anything... except the Taylor fitting, and the Least-Square fit, but those are different. Anyways.

Proposition: Given a set of $n+1$ data points$(x_i, f(x_i))$, such that$x_i \neq x_j$ for $i \neq j$there exists a unique polynomial $p(x) = \sum_{i=0}^n a_ix^i$ of degree $n$ such that $p(x_i) = f(x_i)$ for $i = 0\ldots n$.

Proof: Exercise for the reader.

So how do you find that polynomial? There is the simple straightforward way of doing it by writing out a set of n+1 equations, and solving it by some variation of Gaussian Elimination. In matrix form...

$$\begin{pmatrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\1&x_2&x_2^2&\cdots&x_2^n\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&\cdots&x_n^n\end{pmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\\vdots\\a_n\end{pmatrix}=\begin{pmatrix}f(x_0)\\f(x_1)\\f(x_2)\\\vdots\\f(x_n)\end{pmatrix}$$

But solving such system with Gaussian Elimination is quite expensive. In fact, it takes order $\mathcal{O}(n^3)$ number of operations.

Fortunately, there is a clever way around solving such a big system to get our polynomial.

The trick is something called the Lagrange polynomial. Consider the i-th Lagrange basis polynomial:

$$l_i(x) = \prod_{k=0, k\neq i}^n \frac{(x-x_k)}{(x_i - x_k)}$$

Clearly, $l_i(x_j) = \delta_{ij}$. So now, all is left is to correctly sum the basis polynomials.

$$L(x) = \sum_{i=0}^n f(x_i)l_i(x) = p(x)$$

The sum of a n-th degree polynomial is also of degree n, and there is a unique polynomial of degree n that interpolates the data points. So since this Lagrange polynomial satisfies $L(x_i) = f(x_i)$ for $i = 0\ldots n$, it must be the only one.

At first, it seems that computing the Lagrange polynomial also requires $\mathcal{O}(n^3)$ operations, but there are simple tricks one may employ to reduce the number of needed operations to $\mathcal{O}(n^2)$. I leave it for the reader to see that this is the case, and see how much cheaper it is to find the interpolant this way instead of naive Gaussian Elimination.

[DM]

First Step

This blog will hopefully follow my academic endeavors for the years to come. I heard that it is good practice to write down things that one might learn along a journey, since reading back might bring further advances. So, now, there is nothing else but to lay out my brief current status, no background, just a snapshot, like a corporate balance sheet.

I am currently enrolled in my 4th undergraduate semester (out of 8 study semesters) at the University of Waterloo, studying Mathematics. My current interests lie in some intersection of mathematics, finance, and computational mathematics. Of course this will probably evolve over time, as it radically did over the past three years. But that is another story.

My current major plan is Mathematical Finance with a Computational Mathematics minor. I chose this because it is a great alternative to Applied Math, which focuses more on the mathematics of physics. I am also enrolled in Waterloo's co-operative work program, but that will be an issue dealt with later...

The plan is to graduate in Winter 2012, but there's a slim chance I decide to cram the final study term earlier, ditch co-op, and graduate in Spring 2011. I might ditch co-op anyways... and find stuff on my own.

Current Courses (Fall '09)

MATH 247 Calculus 3 (adv)

MATH 239 Intro to Combinatorics

CS 371 Intro to Computational Mathematics

CS 241 Foundations to Sequential Programs

STAT 231 Statistics

Spring '09

Worked full-time as Junior Economist at Industry Canada

ECON 201 Microeconomic Theory (U. of Guelph)

SOA-FM Financial Mathematics (exam)

Winter '09

MATH 235 Linear Algebra 2

CS 136 Elementary Algorithm/Data design

ACTSC 231 Mathematics of Finance

ECON 140 Intro to Macroeconomics (Wilfrid-Laurier U.)

BUS 121 Functional Areas of Organization (Wilfrid-Laurier U.)

SOA-P Probability (exam)

Fall '09

MATH 145 Algebra (adv)

STAT 230 Probability

CS 135 Designing Functional Programs

ECON 120 Intro to Microeconomics (Wilfrid-Laurier U.)

BUS 111 Intro to Business Organization (Wilfrid-Laurier U.)

Transfered Credits (from Quebec CEGEP)

MATH 136 Linear Algebra 1

MATH 137 Calculus 1

MATH 138 Calculus 2

SCI XXX Science credit

SCI XXX Science credit

I don't feel posting my marks would be of much benefit to this blog. If some readers would like to know them for a reason (such as thinking about graduate school), I might provide them.

Following posts will be more interesting. Promise.

[DM]