How much bias is introduced by the remainder technique?

(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

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

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

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

Math from scratch, part ten: integer comparisons

I’m going to use the same technique I used for Natural comparisons to do Integer comparisons: make a helper function that returns -1 if x < y, 0 if x == y and 1 if x > y, and then have every entry point simply call that helper function. This way we know that all the operators are consistent. The big difference here of course is that I do not need to have a special case that says that null sorts before any value. Continue reading

Math from scratch, part eight: integers

The integers are an extension to the naturals that closes them over subtraction. Rather than do anything fancy, I’m simply going to say that an integer is a natural with an associated sign, and that zero is always “positive”. We don’t want to end up in a situation where there are two forms of zero, since that is confusing.[1. We could of course have three signs, positive, negative and zero, but, meh. We don't gain any great benefits from having a third sign.]

This time however I’m going to make a struct. C# requires that default(SomeStruct), where all the fields are their default values, be a valid value of the type. The default should logically be zero, as it is with all the built-in number types. So rather than checking for null, as we did with the reference type Natural, I’m going to check the sign field for null, which will only be possible if we’ve got a default struct. We’ll simply replace that with zero.[1. I am in general opposed to modifying the formal parameters of a method; I prefer to treat them as read-only variables. I'll make an exception in this case because it keeps the code short and clear.] Continue reading

Math from scratch, part seven: division and remainder

We have only two[1. I'm not going to do bit shifting operators; I don't think of them as operations on natural numbers. If you want them, obviously they are trivial: shifting right is just taking the tail, shifting left is appending a zero bit as the new head. Similarly I am not going to implement the bitwise logical operators. Nor am I going to do the unary plus operator, which wins my award for World's Most Useless Operator. It is a no-op on both naturals and integers; if you really want it, it's not hard to write. The unary minus operator makes no sense on naturals; the only legal operand value would be zero.] operators left, integer division and remainder. We’ve left the most complicated two operations for last, so let’s tread carefully here. Continue reading