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 O(\lg n+\lg\lg n) 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.


Read the rest of this entry »

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 r is given by:

c(r)=2\pi r

Let’s say we’re interested in the Earth’s circumference. The radius r is something in the order of 6400 Km, so c(6400\text{ Km})\approx 40200\text{ Km}. Now, what happens to the radius if we add just 1 meter to the circumference? You’d expect the radius to vary infinitesimally. Wrong!

Read the rest of this entry »

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?

Read the rest of this entry »