Fast Exponentiation, revisited


Quite a while ago, I presented a fast exponentiation algorithm that uses the binary decomposition of the exponent n to perform O(\log_2 n) products to compute x^n.

While discussing this algorithm in class, a student asked a very interesting question: what’s special about base 2? Couldn’t we use another base? Well, yes, yes we can.

Read the rest of this entry »

Fast Recurrences


Quite a while ago, I wrote a post on how to compute an arbitrarily large Fibonacci number F_n in essentially O(\log n) steps. Turns out, that technique generalizes to other recurrence relations, and of any order.

Read the rest of this entry »

Horner’s Method


It’s not like evaluating polynomial is something that comes up that frequently in the average programmer’s day. In fact, almost never, but it brings up a number of interesting questions, such as, how do we evaluate it very efficiently and how much of a simplification in the computation is actually a simplification?

The generic polynomial has the form


If we evaluate this naïvely, we end up doing O(n^2) multiply and O(n) additions. Even using the fast exponentiation algorithm, we still use O(n \lg n) multiplies. But we can, very easily, get down to O(n).

Read the rest of this entry »

Fast exponentiation


A while ago, we looked at the computation of the GCD and found that the simplest implementation was, by far, the fastest. This week, we’ll have a look at another numerical problem: fast exponentiation (modulo machine-size integers).


The exponentiation a^b looks like an expensive operation because, at first, we think it needs b multiplications to be computed. Fortunately for us, and because of the arithmetic of exponentiation, we can compute a^b in O(\lg b) steps, which is much, much faster, even when b is smallish. Let’s us see how.

Read the rest of this entry »