# Integer multiplication without intermediary values

I'm making a programming project for learning purposes, in which I try to calculate powers of very large numbers in as short of a time as possible.

One thing I could do is to try to do multiplication of two numbers without using any intermediary values. I would suppose such an algorithm would traverse the digits from the most significant to the least.

What is a good algorithm for multiplying two integers without using any intermediary values?

(Note: I also posted this question, in a more programming oriented form, over at Stack Overflow: http://stackoverflow.com/questions/8408139/in-place-integer-multiplication)

-
What's the point of not using intermediate values? Is memory at a premium? You should at least have enough space to store the result, and the conventional way of multiplying uses little more than that (if you're really strained, you could reuse the lower order digits of one multiplicand after it has been taken into account). Your question sound like asking to add up $n$ integers without using an accumulator variable. – Marc van Leeuwen Dec 7 '11 at 8:10

The simplest of these, Karatsuba multiplication, is similar to Strassen's well-known matrix multiplication algorithm. To multiply two numbers $x$ and $y$, first divide both numbers into two roughly equal halves $x = x_H x_L$, $y = y_H y_L$. There's a trick that allows computation of $xy$ given only three multiplications of half-sized numbers, at the cost of having more additions (the trivial algorithm requires four: $x_Hy_H,x_Hy_Lx_Ly_H,x_Ly_L$). When applied recursively, the performance is $O(n^{\log_2 3})$ rather than $O(n^2)$. The idea generalizes to the Toom-Cook algorithm, which splits the numbers into more than two parts.
Tha Karatsuba algorithm is only worthwhile for numbers which are large enough (high school multiplication outperforms it for small numbers). For even larger numbers, FFT methods are used. The idea is to think of integer multiplication as polynomial multiplication (after all, an integer in base $B$ notation is a polynomial in $B$!), and then use FFT for multiplying the polynomials (apply the FFT, multiply the results pointwise, apply the reverse FFT). This improves the asymptotics to $\tilde{O}(n\log n)$.