Blasons, Poésies Anciennes (Ebook, DjVu)

M. D. M. M*** — Blasons, Poésies anciennes des XV et XVImes Siècles, extraites de différens auteurs imprimés et manuscrits, nouvelle édition, augmentée d’un glossaire des mors hors d’usage — Paris, Gillemot et Nicolle, 1809

This book was scanned with the help of Christine Arsenault at the Centre Joseph Charles Taché, a research center on the literary history of Canada.

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!

Count Like an Egyptian (Part II)

In a previous entry, we discussed egyptian fractions and, in particular, a greedy algorithm to convert them. We noticed that, once in a while, the greedy algorithm generates a really large denominator, despite harmless-looking fractions:

So, I had an idea to, maybe, minimize the size of the maximum denominator.

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.

Of Sets and bitmaps

When we represent sets, we have many options. We can use a language-specific primitive, like std::set<T> (which is likely list- or tree-like in its detail), or use a bitmap that marks, for each element (and therefore assumes that there is an universal set that contains all elements) whether or not it is included in the set. Bitmaps are simple to implement (especially when one uses something like std::vector<bool>) but need an amount of memory proportional to the universal set, not to the actual subset you’re trying to encode.

We can also use lists, or interval lists. But which one is the most efficient? Under what conditions? Let’s have a look.

Hidden lunch

What delicious lunch hides in the equation

?

Rearrange the equation to find out!

Consider Simplicity, Verily.

If you’re a perfectionist, it’s really hard to limit the efforts you put into developing code. A part of you wants to write the perfect code, while another reminds you that you haven’t time for that, and you will have to settle for good enough code. Today’s entry is exactly this: an ambitious design that was reduced to merely OK code.

I needed to have an exporter (but no importer) to CSV format for C++. One of the first thing that came to mind is to have a variant-like hierarchy that can store arbitrary values, each specific class having its own to_string function, and then have some engine on top that can scan a data structure and spew it to disk as CSV. That’s ridiculously complicated—very general—but ridiculously complicated.

The Great Sultan of the Indies

The Great Sultan of the Indies was sent by one of his viziers 99 bags of gold, each containing exactly 50 coins. Hidden somewhere in those 99 bags is a hollowed coin (indistinguishable to the naked eye from the others) containing a secret message destined to His Most Excellent Majesty. Using a simple two-pan balance, in how many weighing can you find the bag containing the lighter coin? With how many further weighing can you find the coin within the bag?

The solution of the problem is not that complicated, but depends entirely on the assumptions you make on the balance. If one supposes that the balance is large enough to pile the 99 bags in either one of its pan, and that is locked while you’re loading it, giving its reading only once you’re done loading it, the solution that comes to mind is

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.