Wednesday, August 11, 2010

Circular Number System in C

In a previous post I discussed the idea of a circular number system. To reiterate: it is a system whereby the passing the maximum value will return one to the beginning. Take a twenty-four hour clock, for example, which has the range of [0, 23]. The hour that is two hours beyond 23 is not 25, but 1.

Another example is angle measurement. If one has two angles, one at 5 degrees and another at 355 degrees, how far is the second from the first. Linear measurement has one subtracting the two, resulting in an answer of 350 degrees, but looking at the two angles marked on a circle one can see that that is not entirely correct. It is a distance and in some situations has value, but it is not the shortest distance. For that, the correct answer is -10 degrees.

The implementation of this system that I posted was written in Python, but different programming languages have different behaviours for the modulo operator. In some cases, like C++, the behaviour depends upon the implementation. I will not discuss these differences here, as more knowledgeable individuals have already done so elsewhere. For the purpose of this article, I refer to the default C standard used by gcc under Ubuntu 10.04 Linux.

One further difference between C and Python is that Python's modulo operator also works with floating point numbers, while in C it works only with integers. For floating point numbers one must use fmod, which is found in math.h.

Here is the difference function in C:

double diff(double x0, double x1) {
double r = fmod(x1 - x0 + 0.5*UPPER, UPPER);
return (r <>
}

The function finds the shortest distance to x1 from x0 distance, assuming a range of [0, UPPER). The maximum absolute distance between any two values will never be more than half of UPPER.

Followers