Simple, Efficient, and Wrong.

I’m finally giving this thing a name of its own, paraphrasing a quote by H.L. Menken:

For every problem there is a solution that is simple, efficient, and wrong.

Reality has a nasty habit of getting in our way. Like icebergs, real problems have edge cases and complexities that mean most of the problem is underwater, and it’s hard to tell where their bounds really lie until you are on top of them.

Continue reading “Simple, Efficient, and Wrong.”

Sorting a linked list

For God’s sake, don’t try sorting a linked list

— Steve Yegge

Why would it be a bad idea to sort a linked list? A few things come to mind:

  1. To locate the nth item you have to go through the n-1 items that precede it. This makes the formulation of many sorting algorithms unusable for linked lists: the basic “swap" operation no longer takes constant time.
  2. Linked lists are inefficient in general: going over the items in a list means jumping around memory in random. This is bad for the CPU caches, and it might be faster to copy the linked list into an array, and then sort the array.

But let’s not be discouraged: in defiance of Steve, let’s sort a linked list, and do it efficiently, with minimal cache misses!

Continue reading “Sorting a linked list”

Counting combinations modulo power of 2

It is pretty simple to calculate the number of ways to choose k items out of n: There are n ways to choose the first item, n-1 ways to choose the second item, and so on, until there are \(n-k+1\) ways to choose the kth item. By the rule of product there are \(n (n-1)···(n-k+1)\) ways to choose the k items in total.

But hold on, this process considers picking first A and then B distinct from picking first B and then A. If you don’t care about in which order the items are picked you have to remove the duplicates by dividing by the number of ways there are to order k items: this is k! = \(k·(k-1)···3·2·1\). So, the number of ways you can choose k items out of n is:

Continue reading “Counting combinations modulo power of 2”

Infinite integers

Lately we’ve discussed how integers work in computers when their size is limited to a fixed number of bits. What if there is no such limitation and we can use as many bits as we want?

As computers get more and more powerful we’d like to derive this case by looking at what happens when we add more and more bits to the binary representation. For example, if you use 2 bits, -1 = 112 because 1+112 = 1002, and 1002 ≡ 0 (mod 2²). When you move to 3 bits and more you start to see a pattern emerge:

Continue reading “Infinite integers”

Why We Use Two’s Complement

Previously we discussed the mathematical foundations of computer integers and found that, as far as arithmetic is concerned, we can choose to use any range of N = 2m numbers, and the arithmetic operations that have to be implemented in hardware are not affected. Why is it then that in most programming languages we are limited to only two choices of range, called “signed” and “unsigned”?

Continue reading “Why We Use Two’s Complement”