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 13, 2019
Last week, we used the 6×7×6 palette as an example of very simple fraction-of-a-bit coding^{1}. However, we can generalize still a bit more to allow single field extraction and modification

Read the rest of this entry »

2 Comments | algorithms, data compression, data structures | Tagged: Arithmetic Coding, bit-field, fractional bits, Palette, sub-bit | Permalink

Posted by Steven Pigeon

August 6, 2019
Remember ye olde dayes when we had to be mindful of the so-called “web safe palette“? Once upon a time, screens could display 24-bits colors, but only 256 at a time in some “hi-res” modes. But that’s not what I’m going to tell you about: I’d rather tell you about the encoding of the palette, and about a somewhat better palette. And also about using *fractions of bits* for more efficient encodings.

Read the rest of this entry »

1 Comment | algorithms, data compression, hacks | Tagged: bit, coding, colorspace, log, web safe palette | Permalink

Posted by Steven Pigeon

July 30, 2019
While this sounds something like a shameful family secret, discrete inversion is only the finite-valued variation on the method of inversion for the generation of random numbers with a given distribution (as I’ve discussed quite a while ago here). The case we’ll consider here is a random variable with few possible outcomes, each with different odds

Read the rest of this entry »

Leave a Comment » | algorithms, C-plus-plus | Tagged: discrete random variable, initializer_list, inversion, probabilities, pseudo-random, pseudo-random number generator, Random Variable, uniform random | 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 24, 2018
This week, we’ll discuss a cool, but failed, experiment.

In the last few weeks (of posts, because in real time, I worked on that problem over a week-end) we’ve looked at how to generate well distributed, maximally different colors. The methods were to use well-distributed sequences or lattices to ensure that the colors are equidistant. What if we used physical analogies to push the colors around so that they are maximally apart?

Read the rest of this entry »

2 Comments | algorithms, hacks | Tagged: gas, magic constants, molecule, Palette, Physics | Permalink

Posted by Steven Pigeon