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.

Hidden lunch

What delicious lunch hides in the equation

?

Rearrange the equation to find out!

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

Walk Count like an Egyptian (Part I)

The strangest aspect of the Ancient Egyptian’s limited mathematics is how they wrote fractions. For example, they could not write outright, they wrote

,

and this method of writing fractions lead to absurdly complicated solutions to trivial problems—at least, trivial when you can write a vulgar fraction such as . But how much more complicated is it to write rather than ?

Universal Coding (part III)

In Universal Coding (part II), we explored the idea of variable length codes that encode integers of any magnitude in 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.

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

Let’s say we’re interested in the Earth’s circumference. The radius is something in the order of 6400 Km, so . Now, what happens to the radius if we add just 1 meter to the circumference? You’d expect the radius to vary infinitesimally. Wrong!

SEND+MORE=MONEY

Let’s consider a rather simple puzzle:

   SEND
+  MORE
= MONEY

where each letter is assigned a value from 0 to 9. How would you solve
it?

The Speed of GCD

The subject of computing the GCD was brought up a couple of times lately, and we assumed that the straightforward divide-and-remained implementation was the most efficient. But is it?

Before writing this post, I knew of basically two versions, one due to Euclid, invented sometimes in Antiquity of course, and one that used the remainder (that is, modulo) to do basically the same thing (which can be implemented either recursively or iteratively). Turns out that there are other algorithms, for example the so-called binary GCD that tries to somewhat speed up the process by removing multiples of two. But which one is the most efficient?