Yet another Square Root Algorithm

April 29, 2014

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?

malevich-square

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!

Read the rest of this entry »


Count Like an Egyptian (Part II)

April 22, 2014

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:

\displaystyle \frac{412}{1000}=\frac{1}{3}+\frac{1}{13}+\frac{1}{574}+\frac{1}{699563}

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

Read the rest of this entry »


A runcible nonce

April 15, 2014

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.

heartbleed

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.

Read the rest of this entry »


Of Sets and bitmaps

April 8, 2014

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.

malevich-square

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

Read the rest of this entry »


Hidden lunch

April 2, 2014

What delicious lunch hides in the equation

\displaystyle \pi=\left(\frac{n_{om}}{z\sqrt{a}}\right)^2?

Rearrange the equation to find out!

Read the rest of this entry »


Consider Simplicity, Verily.

April 1, 2014

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.

turbo-napkin

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.

Read the rest of this entry »