Evaluating polynomials is not a thing I do very often. When I do, it’s for interpolation and splines; and traditionally those are done with relatively low degree polynomials—cubic at most. There are a few rather simple tricks you can use to evaluate them efficiently, and we’ll have a look at them.

## Factorial Approximations

31/03/2020(and its logarithm) keep showing up in the analysis of algorithm. Unfortunately, it’s very often unwieldy, and we use approximations of (or ) to simplify things. Let’s examine a few!

## Fast Exponentiation, revisited

12/11/2019Quite a while ago, I presented a fast exponentiation algorithm that uses the binary decomposition of the exponent to perform products to compute .

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.

## Mœud deux

07/08/2018Pairing functions are fun. Last week, we had a look at the Cantor/Hopcroft and Ullman function, and this week, we’ll have a look at the Rosenberg-Strong function—and we’ll modify it a bit.

## Mœud

31/07/2018Pairing functions are used to reversibly map a pair of number onto a single number—think of a number-theoretical version of `std::pair`. Cantor was the first (or so I think) to propose one such function. His goal wasn’t data compression but to show that there are as many rationals as natural numbers.

Cantor’s function associates pairs (i,j) with a single number:

…but that’s not the only way of doing this. A much more fun—and spatially coherent—is the boustrophedonic pairing function.

## The Well-Tempered Palette (Part 2)

17/07/2018Last week, we’ve had a look at how to distribute maximally different colors on the RGB cube. But I also remarked that we could use some other color space, say HSV. How do we distribute colors uniformly in HSV space?

## Paeth’s Method (Square Roots, Part VII)

13/03/2018In *Graphics Gems* [1], Paeth proposes a fast (but quite approximate) method for the rapid computation of hypotenuse,

.

The goal here is to get rid of the big bad because it is deemed “too expensive”—I wonder if that’s still actually true. First, he transforms the above equation: