November 12, 2019
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.

Read the rest of this entry »

2 Comments | algorithms, Mathematics | Tagged: base 2, binary, fast exponentiation, Mathematica, number theory | Permalink

Posted by Steven Pigeon

August 7, 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.

Read the rest of this entry »

3 Comments | algorithms, data compression, Mathematics | Tagged: Cantor, Hopcroft, pairing function, Rosenberg, Rosenberg-Strong, Strong, Ullman | Permalink

Posted by Steven Pigeon

July 31, 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.

Read the rest of this entry »

1 Comment | algorithms, data compression, Mathematics | Tagged: boustrophedonic, Cantor, Integer, ox, pairing function, plowing, Rational | Permalink

Posted by Steven Pigeon

July 17, 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?

Read the rest of this entry »

Leave a Comment » | algorithms, hacks, Mathematics | Tagged: Centered hexagonal numbers, Hexagonal numbers, HSV, Lattice, OEIS, Palette | Permalink

Posted by Steven Pigeon

March 13, 2018
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:

Read the rest of this entry »

Leave a Comment » | algorithms, hacks, Mathematics | Tagged: Archytas, Bakhshali, Hypotenuse, Paeth, Square root, Taylor Series | Permalink

Posted by Steven Pigeon

February 27, 2018
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.

Read the rest of this entry »

Leave a Comment » | algorithms, Mathematics, programming | Tagged: Calculus, Curve Length, pseudo-random, random, Sphere, uniform random | Permalink

Posted by Steven Pigeon

February 20, 2018
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).

Read the rest of this entry »

Leave a Comment » | algorithms, hacks, Mathematics | Tagged: Archytas, Newton's Method, Old Babylonian, Square root | Permalink

Posted by Steven Pigeon