Walk Count like an Egyptian (Part I)

The strangest aspect of the Ancient Egyptian’s limited mathematics is how they wrote fractions. For example, they could not write outright, they wrote

,

and this method of writing fractions lead to absurdly complicated solutions to trivial problems—at least, trivial when you can write a vulgar fraction such as . But how much more complicated is it to write rather than ?

Fractional Bits (Part II)

In a previous post, we started discussing the subject of encoding values using fractional bits. This is quite counter-intuitive as we usually think that encoding asks for whole bits, furthermore that we think of bits as being essentially atomic—unsplittable.

However, bits can be fractioned, helping us devising efficient encodings, something not unlike a primitive form of arithmetic coding, for a variety of data. Let’s consider a simple case that illustrates the principle: encoding the date.

No post today

Well, obviously, except this one. A bit too busy right now to mind the blog, I’ll be back on track for next week.

Universal Coding (part III)

In Universal Coding (part II), we explored the idea of variable length codes that encode integers of any magnitude in bits, but the encoding requires (somewhat) complex arithmetic, and we concluded that sometimes, it’s better to use a simple code that sacrifices some coding-efficiency in exchange for machine-efficiency. Let’s now look at one of those, MIDI VLQ and how we can make it a bit better.

Around The World

Intuition does not always help us getting mathematical results right. Au contraire, some very simple results are blatantly counter-intuitive. For example, the circumference of a circle of radius is given by:

Let’s say we’re interested in the Earth’s circumference. The radius is something in the order of 6400 Km, so . Now, what happens to the radius if we add just 1 meter to the circumference? You’d expect the radius to vary infinitesimally. Wrong!

Short Pointers

One good thing with 64 bits addresses, is that you can, in principle, use essentially as much memory as you want—the address space certainly exceeds today’s computers’ capabilities. One bad thing, especially when you create lots of objects and need plenty of pointers, is that 64 bits pointers are big. They use 8 bytes of memory. One or two pointers aren’t a problem, of course, but what if your data structure is a sparse graph, each node being mostly pointers, and that you need to create a very large graph?

One solution is to use stretch codes, as I proposed a while ago, trading off precision of addressing for shorter pointers. However, unless you rewrite the memory allocator, the technique won’t play well with the default new. Another solution is to store just barely the number of bits (rounded to bytes) necessary to hold an address. Can we do this? If so, how?

Enumerating Enums

Every programming language has its defects; sometimes large, sometimes subtle; often causing irks. One thing that has been bugging me for a while (and many others, as you can see if you use Google) is the impossibility of enumerating enums from basic language constructs. You just can’t. Using the STL (and C++ 2011), however, you can have a somewhat elegant solution.

The solution I propose in this post is robust as it does not depend on the actual values of enums nor on that they can be mapped onto integers. We arrived at this solution (we being me and people on the ##c++ channel on Freenode, especially user “moonchild”) and I think it (almost) solves the problem of enumerating enums.

Yet More __builtins

So last week we saw how to use some of GCC’s built-ins, this week, let’s have a look at how we can create our own, if need be. Say because you need to have access to some instruction and that GCC does not offer the corresponding built-in.

To do so, we’ll use a bit of the C preprocessor and GCC’s inline assembly extension.

More __builtins

Last week we discussed GCC intrinsics a bit. This week, let’s have a look at what kind of speed-ups we can get, and how the use of intrinsics affect code generation.

Sometimes, I do strange things. I mean, my experiments aren’t necessarily self-evident, and sometimes, I need performance from primitives that usually are not bottlenecks—such as computing the GCD. This time, I need to get and in as fast as possible. Let’s have a look at how intrinsics help us.

GCC Built-ins

In the discussion of The Speed of GCD, Daniel Lemire remarked that one could use the compiler-specific intrinsic function __builtin_ctz to get a good speed-up on binary GCD. That remark made me look into all the others intrinsics and built-ins offered by GCC.

Let’s have a look to at least a few of them!