I said last time that binary-searching the rationals (WOLOG between zero and one) for a particular fraction that is very close to a given double does not really work, because we end up with only fractions that have powers of two in the denominators. We already know what fraction with a power of two in the denominator is closest to our given double; itself!
But there is a way to binary-search the rationals between zero and one, as it turns out. Before we get into it, a quick refresher on how binary search works:
All right, we have an arbitrary-precision rational arithmetic type now, so we can do arithmetic on fractions with confidence. Remember the problem I set out to explore here was: a double is actually a fraction whose denominator is a large power of two, so fractions which do not have powers of two in their denominators cannot be represented with full fidelity by a double. Now that we have this machinery we can see exactly what the representation error is:
A couple of years ago I developed my own arbitrary precision natural number and integer mathematics types, just for fun and to illustrate how it could be done. I’m going to do the same for rational numbers here, but rather than using my integer type, I’ll just use the existing
BigInteger type to represent the numerator and denominator. Either would do just fine.
Of course I could have used some existing
BigRational types but for various reasons that I might go into in a future blog article, I decided it would be more interesting to simply write my own. Let’s get right to it; I’ll annotate the code as I go.
Good Monday morning everyone; I hope my American readers had a lovely Thanksgiving. I sure did!
Well enough chit-chat, here’s a problem I was pondering the other day. We know that doubles introduce some “representation error” when trying to represent most numbers. The number 3/4, or 0.75 for example, can be exactly represented by a double, but the number 3/5, or 0.6, cannot.
The nice people at DevProConnections asked me to write a beginner-level article for them about the perils of arithmetic in C#; of course these same perils apply to C, C++, Java and many, many other languages. Check it out!
(This is a follow-up article to my post on generating random data that conforms to a given distribution; you might want to read it first.)
Here’s an interesting question I was pondering last week. The .NET base class library has a method
Random.Next(int) which gives you a pseudo-random integer greater than or equal to zero, and less than the argument. By contrast, the
rand() method in the standard C library returns a random integer between 0 and
RAND_MAX, which is usually 32768. A common technique for generating random numbers in a particular range is to use the remainder operator:
int value = rand() % range;
However, this almost always introduces some bias that causes the distribution to stop being uniform. Do you see why?
Last time we showed how you can take any two coprime positive integers
m and compute a third positive integer
y with the property that
(x * y) % m == 1, and therefore that
(x * z * y) % m == z % m for any positive integer
z. That is, there always exists a “multiplicative inverse”, that “undoes” the results of multiplying by
m. That’s pretty neat, but of what use is it?
Here’s an interesting question: what is the behavior of this infinite sequence? WOLOG let’s make the simplifying assumption that
m are greater than zero and that
x is smaller than
m. Continue reading
Now that we have an integer library, let’s see if we can do some 2300-year-old mathematics. The Euclidean Algorithm as you probably recall dates from at least 300 BC and determines the greatest common divisor (GCD) of two natural numbers. The Extended Euclidean Algorithm solves Bézout’s Identity: given non-negative integers
b, it finds integers
y such that:
a * x + b * y == d
d is the greatest common divisor of
b. Obviously if we can write an algorithm that finds
y then we can get
y have many useful properties themselves that we’ll explore in future episodes.
Now we come to the controversial one. As I pointed out back in 2011, the
% operator is the remainder operator. When extending the division and remainder operators from naturals to integers, I require that the following conditions be true for dividend
x, non-zero divisor
q and remainder
x == y * q + r
y are non-negative then
0 <= r < y
(-x) / y == x / (-y) == -(x / y)
Let’s take a look at the consequences of these three facts. Continue reading