## Category Archives: Mathematics

### 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 2′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. Why is it then that in most programming languages we are limited to only two choices of range, called “signed” and “unsigned”? The problem is [...]

### 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? The main problem with having a finite number of bits is that we have a [...]

### Positive and negative zeros, and MySQL

In mathematics zero usually is considered signless; it’s neither positive nor negative. In computer floating point numbers there are two zeros: one positive, +0.0, and one negative -0.0, at least if we follow the IEEE standard. Most of the time you can’t tell the difference between the two: As far as basic arithmetics is concerned [...]

### Converting decimal numbers to fractions

Given that computer numbers have a finite precision, a calculation like 20/3 produces a result like 6.66667, which is slightly off. This begs the question: can we reverse the division operation, to make a routine that outputs “20/3″ when it’s given the approximate value? One trick is to take a large number as the denominator. [...]

### An Interesting Golden Ratio Identity

Lately I’ve been intrigued  by the Fibonacci number sequence, i.e. the sequence where each number is the sum of the two previous. Formally the sequence is defined by the recurrence formula \(F_{n+1} = F_n+F_{n-1}\), when we set \(F_1 = 1\) and \(F_2=1\). If needed, we can use \(F_{n-1} = F_{n+1}-F_n\) to extend the sequence backwards; [...]