Fractional Bits (Part III)

A long time ago, we discussed the problem of using fractions of bits to encode, jointly, values without wasting much bits. But we considered then only special cases, but what if we need to shift precisely by, say, half a bit?

But what does shifting by half a bit even means?

Count like an Egyptian (Part III)

In previous posts, I’ve looked into unit fractions, also known as “Egyptian fractions”, fractions where the numerator is and the denominator , some integer. We have noticed that finding good representation for a fraction as a sum of unit fraction is not as trivial as it may first seem. Indeed, we noticed that the greedy algorithm, the one that always pick the largest unitary fraction that does not exceed the rest as the next term, may lead to long series of unit fractions, sometimes with large denominators, even for simple fraction. For example,

.

In a previous post, I suggested decomposing in an “easy way”, which was often better than the greedy algorithm. Surely, we can do better, but how?

Yet Another Square Root Algorithm (part III)

Finding good, fast, and stable numerical algorithms is usually hard, even for simple problems like the square root, subject we’ve visited a number of times. One method we haven’t explored yet, is using the Taylor series. The Taylor series for around is given by:

Can we exploit that to compute efficiently, and with some precision, square roots?

Weird binomial coefficients

The binomial coefficients find great many uses in combinatorics, but also in calculus. The usual way we understand the binomial coefficients is

,

where and are integers. But what do you do with ?! Is it even defined?

Padé Approximants

Sometimes, you need to compute a function that’s complex, cumbersome, or which your favorite language doesn’t quite provide for. We may be interested in an exact implementation, or in a sufficiently good approximation. For the later, I often turn to Abramovitz and Stegun’s Handbook of Mathematical Function, a treasure trove of tables and approximations to hard functions. But how do they get all these approximations? The rational function approximations seemed the most mysterious of them all. Indeed, how can one come up with

for , for ?

Well, turns out, it’s hard work, but there’s a twist to it. Let’s see how it’s done!

The protoshadok number system

We’re so used to our positional notation system that we can’t really figure out how to write numbers in other systems. Most of the ancient systems are either tedious, complicated, or both. Zero, of course, plays a central role within that positional system. But is it indispensable?

In one of my classes, I discuss a lot of different numeration systems (like Egyptian, Babylonian, Roman and Greek) to explain why the positional system solves all, or at least most, of these systems’ problems. I even give the example of Shadok counting (in french) to show that the basis used isn’t that important (it still has to be greater than one, and, while not strictly necessary, preferably a positive integer). But can we write numbers in a positional system without zero?

Serializing Trees

Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.

But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.

Log2 (with C++ metaprogramming)

C++ meta-programming a powerful tool. Not only can you use it to build generic types (such as the STL’s std::list), you can also use it to have compile-time evaluation. Let’s have a look at a simple problem that can be solved in two very different ways: computing the Log base 2 of an integer.

Rotating Arrays (part II)

Last week we had a look at Kernighan’s algorithm to rotate an array position and concluded that it might not be optimal, as each element was moved twice. This week, we’ll have a look at another algorithm that moves some items more than once, but overall will do less than two exchanges per items.

Rotating Arrays (Part I)

To “rotate” an array position to the left (or to the right, doesn’t really matter) we could repeat times a shift of one, using only one temporary variable. This method doesn’t use much auxiliary memory but is inefficient: it will do copies if we apply it to an array of size . Surely we can do better.