Bresenham’s Pie


Approximating \pi is always fun. Some approximations are well known, like Zu Chongzhi’s, \frac{355}{113}, that is fairly precise (it gives 6 digits).

We can derive a good approximation using continue fractions, series, or some spigot algorithm. We can also use Monte Carlo methods, such as drawing uniformly distributed values inside a square, count those who falls in the circle, then use the ratio of inside points to outside points to evaluate \pi. This converges slowly. How do we evaluate the area of the circle then? Well, we could do it exhaustively, but in a smart way.

Read the rest of this entry »

Binary Trees are optimal… except when they’re not.


The best case depth for a search tree is O(\log_b n), if b is the arity (or branching) of the tree. Intuitively, we know that if we increase b, the depth goes down, but is that all there is to it? And if not, how do we chose the optimal branching b?


While it’s true that an optimal search tree will have depth O(\log_b n), we can’t just increase b indefinitely, because we also increase the number of comparisons we must do in each node. A b-ary tree will have (in the worst case) b-1 keys, and for each, we must do comparisons for lower-than and equal (the right-most child will be searched without comparison, it will be the “else” of all the comparisons). We must first understand how these comparisons affect average search time.

Read the rest of this entry »

The very long summer


The original plan was to come back in september 2018, but it turns out, I was rather busy with everything else. I missed blogging, so I’ve decided to continue, but it will be at a much softer rate of about a post of month, rather than once a week.



constexpr is one of C++11’s features I’m starting to like very much. constexpr is a bit finicky, but it allows you to evaluate functions—including ctors—at compile time. This of course, allows computations to be replaced directly by results.

So in the best of cases, you could end-up with less code, or better yet, no code at all!

Read the rest of this entry »

ANSI soit-il.


There’s no easy way of getting a console-based color output with standard C++. Of course, you can use ncurse, which does pretty much everything, but that is also quite tedious to use. But if you need just a little bit of color, ncurse is pretty overkill. Fortunately, if you have an ANSI capable terminal, that’s much easier.

Read the rest of this entry »

l8r, allig8r


See you all in september!

Reading cassettes, tout azimuth (Part II)


Last week we started to look at the problem of azimuth alignment on olden compact cassette tape drives, and how this misalignment affects the sound. Let’s now have a look at how azimuth affects the frequencies.

Read the rest of this entry »

Closed for Summer (2016)


It’s that time again. The semester’s almost over, only a few assignments and exams to mark; everybody’s busy at their own stuff. Like the last few summers, I’ll kind of close the blog until September. I said “kind of” because maybe I’ll post a few things anyway. Especially that this summer will be interesting: more time for research, 7ECM, which I will attend, and a few other things. Seeya in September!

(RGB II, 2560×1440)

(RGB II, 2560×1440)



Sorry, no entry for this week: I’ve been rather busy lately (because of science).


Busy doing Science


Sorry, no entry for this week… I’ve been busy doing science ¯\_(ツ)_/¯