Category Archives: Mathematics

The dedoublifier, part four

Posted on by
19

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:
Continue reading →

The dedoublifier, part three

Posted on by
21

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:
Continue reading →

The dedoublifier, part two

Posted on by
29

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.
Continue reading →

The dedoublifier, part one

Posted on by
30

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.
Continue reading →

How much bias is introduced by the remainder technique?

Posted on by
29

(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?
Continue reading →

A practical use of multiplicative inverses

Posted on by
36

Last time we showed how you can take any two coprime positive integers x and 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 x modulo m. That’s pretty neat, but of what use is it?
Continue reading →

Math from scratch, part twelve: Euclid and Bézout

Posted on by
14

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 a and b, it finds integers x and y such that:

a * x + b * y == d

where d is the greatest common divisor of a and b. Obviously if we can write an algorithm that finds x and y then we can get d, and x and y have many useful properties themselves that we’ll explore in future episodes.

Continue reading →

Math from scratch, part eleven: integer division

Posted on by
17

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 y, quotient q and remainder r:

  • x == y * q + r
  • if x and 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 →