Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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

1 Answer 1

Probably not what you meant, but also an answer to your question. Fast integer multiplication uses algorithms altogether different than the "high school" algorithm. You can find a description of some of these algorithms on Wikipedia or in the documentation of GMP, which is a library for fast exact arithmetic.

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.