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!

# Category Archives: Integer arithmetic

# 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 thirteen: multiplicative inverses

Here’s an interesting question: what is the behavior of this infinite sequence? WOLOG let’s make the simplifying assumption that `x`

and `m`

are greater than zero and that `x`

is smaller than `m`

. 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.

# 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