A Bit About Bit-Fields

Let’s make a detour through low-level programming this week. Let’s talk about bit-fields and some of their quirks.

the Dutch Flag Problem

While preparing my lecture notes on sorting, I rediscovered the Dutch flag problem proposed by Edsger W. Dijkstra quite a while ago. This problem is relevant in the context of sorting, especially for variants of Quicksort, where you want to create not two but three partitions.

Like many problems, the Dutch flag problem has a very simple statement. Say you have an array with three types of value, how can you arrange them so that all the items of the first type is at the beginning of the array, the items of the third at the end (and, of course, leaving the second type between the two)?

OB Sqrt

I have discussed the problem of efficient square root calculation quite a few times. And yet, while reading Rudman’s The Babylonian Theorem, I found yet another square root algorithm. The Old Babylonian square root algorithm. Let’s have a look on how it works.

Eratosuite

The other day in class, we were looking at recurrence relations and how to solve them with the characteristic equation. Among the examples I gave was a recurrence that seemed to give a good number of primes numbers. Are there many of those? How do we find them?

Well, we need two things: a method of testing if a given number is prime, and a method of generating recurrences—parameters and initial conditions. Well, make that three: we also need to generate the suite generated by the recurrence relation. Let’s go!

Single-Pointer Doubly-Linked Lists

Old computer science books aren’t perceived as being of much use, since everything is so much better now. Of course, that’s not entirely true, especially when we are interested in the techniques used in the days where 32KB core memory was “a lot”. Leafing through one such book, Standish’s 1980 Data Structure Techniques, I found a method of maintaining doubly-linked lists using only one pointer. Let’s see how it works!

Pythagorean Primes

Last Week, we had a look at Pythagorean triples. Remember: a Pythagorean triple is three natural numbers (positive integers) such that . Most of the times, even with and natural numbers, is irrational. Sometimes is prime; sometimes is. Is either frequent?

Pythagorean Triples

The Pythagorean theorem, linking the sides of a right triangle, is one of the most useful basic mathematical identities. It is also one of the more entertaining. Loomis, in his book The Pythagorean Proposition (1968), gives 370 different proofs of the theorem. However, we’ll more often interested in computing the length of the hypotenuse, or finding triples—three natural numbers that makes the theorem hold—than finding a new proof for it.

There is, of course, the smallest possible triple (defined as involving the smallest possible numbers) 3, 4, 5. But there are infinitely more triples. Let’s see how we can generate them.

…And a Good One (Hash functions, part VI)

In the previous entries, we learned that a good hash function for look-ups should disperse bits as much as possible as well as being unpredictable, that is, behave more or less like a pseudo-random number generator. We had a few failed attempts, a few promising ones, and now, a good one.

Rational approximations of π (Divertimento)

While reading on the rather precise approximation 355/113 for π, I’ve wondered how many useful approximation we could find.

Busy doing Science

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