Evaluating polynomials

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

(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

Quite 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

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

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)

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)

In 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:

Random Points on a Sphere (Generating Random Sequences III, Revisited)

While searching for old notes—that I haven’t found anyway—I returned to an old blog entry and I thought I was kind of unsatisfactory, with be best part being swept under the carpet with a bit a faery dust, and very handwavingly.

So let’s work-out how to uniformly distribute points on a sphere in a more satisfactory fashion.

Square roots (Part VI)

I’ve discussed algorithms for computing square roots a couple of times already, and then some. While sorting notes, I’ve came across something interesting: Archytas’ method for computing square roots.

Archytas’ method is basically the old Babylonian method, where you first set

,

,

and iterate

,

,

until desired precision is achieved (or the scribe is exhausted).

Unary numbers.

A positional number system needs a base that is either greater than one, or smaller than minus one—yes, we can have a negative base for a number system. The system, however, seems to break down if the base we chose is base 1.

If the base is 1, then there are no permissible digits since the digits , in a base system, must be . But we can still represent numbers using just 1s. That's the unary numeral system, and numbers are just represented as repeated 1s. 15? Fifteen ones: 111111111111111. Operations? Not very complicated, just… laborious.