## Evaluating polynomials

05/05/2020

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 $n!$ (and its logarithm) keep showing up in the analysis of algorithm. Unfortunately, it’s very often unwieldy, and we use approximations of $n!$ (or $\log n!$) to simplify things. Let’s examine a few! ## 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.

## Mœud deux

07/08/2018

Pairing 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/2018

Pairing 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/2018

Last 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/2018

In Graphics Gems , Paeth proposes a fast (but quite approximate) method for the rapid computation of hypotenuse, $\displaystyle h=\sqrt{x^2+y^2}$.

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