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: 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 …
Category Archives: Programming
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 …
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 …
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 …
Mathematics of computer integers
Integers have typically a fixed size in computers, for example 32 or 64 bits. Since there are no such limits on the size of integers in mathematics, the question arises: how do computer integers work, with respect to mathematical theory?