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
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
Almost all the
Integer operations are simply wrappers around the
Natural operations, plus some gear to deal with the signs. Continue reading
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.
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. Continue reading
We have only two operators left, integer division and remainder. We've left the most complicated two operations for last, so let's tread carefully here. Continue reading
Getting equality correct is surprisingly tricky in C#. The landscape is a bit of a confusing jumble:
!= operators are a syntactic sugar for static method calls, so it is dispatched based on the static (compile-time) type of both operands.
object.Equals(object) is a virtual method, so of course it dispatches on the runtime type of its receiver but not its argument. An override on a type T is required to handle any object as an argument, not just instances of T.
IEquatable<T>.Equals(T) by contrast takes a T.
- For reference types, you've got to consider comparisons to null even if it is an invalid value.
That's four ways to implement equality already and we haven't even gotten into
IComparable<T>.CompareTo(T), which also needs to be able to compute equality. Continue reading
Ok, addition and multiplication are in the can. Those are the easy ones because the set of natural numbers is "closed" over those operations. That is, if you have any two naturals then both their sum and their product is also a natural. Not so subtraction! To see why, first we have to state what subtraction really is. Continue reading