## Fast Exponentiation, revisited

12/11/2019

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.

## Fast Recurrences

02/01/2018

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.

## Horner’s Method

25/10/2016

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

$a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n$.

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

## Fast exponentiation

24/12/2013

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.