The wireless keyboard, again (part deux)

For last week’s entry, I wrote a small script to monitor my wireless keyboard’s activity, logging keys, and mode changes. This week, let’s have a look at the data we can grab, and what we can do with it.

So, after grabbing keyboard activity for a bit more than a week (from 2014-10-12 22:47:31.059636 to 2014-10-20 08:45:06.733120), we’re ready to preprocess the logs and extract useful information.

The wireless keyboard, again.

So, again, I got a Bluetooth keyboard. This time, I’m pleased with the fact that it will, in principle, never need to have its batteries changed. It’s solar. I got the Logitech K760.

So of course, I set out to test it a good while before concluding whether or not it would be charged enough to keep up with me. But how much typing do I do in a day? Well, let’s find out!

A quick primer on Graphviz

One of the tools I use to make figures for papers and books—if I need to make a graph, of course—is Graphviz. Graphviz is flexible, powerful, but also a rather finicky beast that will repeatedly bite your fingers. Today, I’ll share some of my tricks with you.

Take That, Fermat!

You’ve certainly heard of Fermat’s last theorem stating that

has no integer solutions for . Well, guess what:

.

Take that, Fermat!

Yet Another Square Root Algorithm (part II)

last week, we saw that we could use a (supposed) efficient machine-specific instruction to derive good bounds (but not very tight) to help binary search-based and Newton-based square root extraction algorithms go faster. Last week, we saw that the technique did lead to fewer iterations in both algorithms.

Now, does the reduced number of iterations translate into actual, machine speed-up?

Yet another Square Root Algorithm

Computing (integer) square root is usually done by using a float square root routine and casting it to an integer, possibly with rounding. What if, for some reason, we can’t use floats? What are the possibilities?

One possibility is to use binary search to find the square root of a number. It may be a good choice because it will only perform a number of iterations that is half of the (maximum) numbers of bits of the number (we will explain why in a moment). Another possibility is to use Newton’s method to find the square root. It does a bit better than binary search, but not exceedingly so: on very small integers, it may iterate a third as much iterations as binary search, but on large integers, it will do only a bit fewer iterations. Can we do better? Yes!

A runcible nonce

In the recent panic surrounding the Heartbleed bug, we ask ourselves why, and how, these bugs still happen. We know that it was a preventable bug, with a simple fix, but with potentially important repercussions.

The bug is explained in non-technical (but accurate) terms here, and the patch is shown here. But that’s not what I want to talk you about. Let’s discuss the source of the problem.

Converting PDFs to Hard B+W

Nothing too this week: how to convert a Djvu or PDF to hard black and white PDF—not shades of gray. Why would you want to do that anyway? Well, you may, like me, have a printer that has no concept of color calibration and has dreadful half-toning algorithms, resulting in unreadable text and no contrast when you print a Djvu or a PDF of a scanned book.

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?

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.