Almost all the Integer operations are simply wrappers around the Natural operations, plus some gear to deal with the signs. Again, recall that we have decided that default(Integer) is an alias for zero.
Our general plan of attack for all these operators will be to reduce them to an operation on two positive numbers, which can then be done in naturals. The first thing we’ll need that the Natural class cannot give us is unary negation, which of course simply swaps the sign:
public static Integer operator -(Integer x)
{
if (x.IsDefault) x = Zero;
return Create(x.sign == Positive ? Negative : Positive, x.magnitude);
}
Addition of two positive quantities or two negative quantities simply adds the magnitudes and keeps the sign the same. Addition of a positive quantity and a negative quantity can be handled by turning them both into positive quantities and doing a subtraction:
public static Integer operator +(Integer x, Integer y)
{
if (x.IsDefault) x = Zero;
if (y.IsDefault) y = Zero;
if (x.sign == y.sign)
return Create(x.sign, x.magnitude + y.magnitude);
else if (x.sign == Positive)
return x - (-y);
else
return y - (-x);
}
Subtraction is a bit trickier. If we have a negative number subtracted from a positive number, we can turn that into an addition of positive numbers. Similarly with a positive number subtracted from a negative number. A negative number subtracted from a negative number can be turned into the difference of two positive numbers. That leaves the subtraction of a positive number from a positive number. Since our Natural class will reject the subtraction of a larger number from a smaller number, we need to know which is larger in order to do the subtraction safely; we then assign the sign accordingly.
public static Integer operator -(Integer x, Integer y)
{
if (x.IsDefault) x = Zero;
if (y.IsDefault) y = Zero;
if (x.sign != y.sign)
return Create(x.sign, x.magnitude + y.magnitude);
else if (x.sign == Negative)
return (-y) - (-x);
else if (x.magnitude >= y.magnitude)
return Create(Positive, x.magnitude - y.magnitude);
else
return Create(Negative, y.magnitude - x.magnitude);
}
Now that we have addition and subtraction we can trivially implement increment and decrement:
public static Integer operator ++(Integer x)
{
return x + One;
}
public static Integer operator --(Integer x)
{
return x - One;
}
Multiplication is trivial; we just multiply the magnitudes and assign the sign appropriately:
public static Integer operator *(Integer x, Integer y)
{
if (x.IsDefault) x = Zero;
if (y.IsDefault) y = Zero;
return Create(
x.sign == y.sign ? Positive : Negative,
x.magnitude * y.magnitude);
}
The power operation is only defined on integers where the exponent is a natural:
public Integer Power(Natural exponent)
{
if (ReferenceEquals(exponent, null))
throw new ArgumentNullException("exponent");
Integer x = this;
if (x.IsDefault) x = Zero;
return Create(
x.sign == Negative && exponent % Natural.Two != Natural.Zero ? Negative : Positive,
x.magnitude.Power(exponent));
}
Note that I added a Natural.Two field for convenience. Note also that I don’t want to say
if (this.IsDefault) this = Zero;
because I don’t want to mutate the storage that the caller gave me. Remember, this is essentially a ref Integer parameter in this value type; we can modify it but we don’t want to.
In order to do division and remainder we need to be able to compare integers to Zero, so we’ll do those after we implement comparisons.
Next time on FAIC: we’ll implement the Integer comparison operators. They’ll look unsurprisingly similar to the Natural comparison operators.
Fabulous adventures in coding 
Your definition of Power uses the variable “y” that isn’t defined. I assume you meant “exponent” instead.
Whoops, that’s what I get for editing the code in the blog after I’ve already pasted it in from the code editor. Fixed.
Earlier you’d indicated you weren’t interested in defining “bit operators”, but computing a modulus and then checking whether that’s zero seems clunky–not just from a performance standpoint, but also from a legibility standpoint. Perhaps having `Natural` include an `IsMultipleOf` member would be helpful; note that one could include some optimizations in that member that would not be applicable in a normal “modulus” computation, since (in binary) X0 is a multiple of Y0 iff X is a multiple of Y, X0 is a multiple of Y1 iff X is a multiple of Y1, X1 is not a multiple of Y0, and of course everything is a multiple of 1.
Also, is there any reason to copy `this` to X so as to avoid modifing `this` in the zero case, as opposed to simply returning zero if `this` is default?
I also find the modulo a little bit overcomplicated. What would be wrong just testing if exponents head equals ZeroBit? A number is dividablle by 2 when it is even. In base 2 this is obviously when least significant digit is 0.
As another proposal: Implementing addition on its own leads to a very simple subtraction.
public static Integer operator +(Integer x, Integer y)
{
if (x.IsDefault) x = Zero;
if (y.IsDefault) y = Zero;
if (x.sign == y.sign)
return Create(x.sign, x.magnitude + y.magnitude);
else if (x.magnitude >= y.magnitude)
return Create(x.sign, x.magnitude – y.magnitude);
else
return Create(y.sign, y.magnitude – x.magnitude);
}
public static Integer operator -(Integer x, Integer y)
{
return x + (-y);
}
To answer your first question: that’s a private implementation detail of Natural. But I agree with both you and John: were I trying to design a high performance robust library here I would surely have a fast implementation of “is even”, somehow.
To answer your second question: I like it! This is indeed a better implementation.
I like the modulo myself. Using mathematical operators to express the mathematical concept is more natural that relying on the implementation detail that Natural happens to use strings of bits.
Doing bit operations here seems a bit C-ish to me. If I were writing that method I’d use % too, even using normal ints and longs; the compiler should figure out that it can check the low bit.
But, while we’re picking nits, I think that in your unary minus operator, flipping the sign ought to be the responsibility of the sign class:
return Create(x.sign.Flip(), x.magnitude);
or similar. With your fancy enumerations, you can do that.
Good idea!
That a number’s head determines whether it’s even or odd is an implementation detail, but with many numeric types finding out whether a number is a multiple of another number is simpler than computing the actual value of the modulus/remainder (e.g. to compute `signedInt % 4` without a division instruction requires three instructions including a conditional branch; setting a flag based upon whether `signedInt` was a multiple of four requires only one). Since the operator is probably used about as often to test whether something is a multiple as it is to find out the actual value of the modulus/remainder, that would seem a helpful optimization [btw, if I’d written the C standard, I probably would defined x%y such that if x is a multiple of y, x%y must be zero, but if x is not a multiple of y and either operand is negative, the implementation may arbitrarily return any non-zero value ; if code wants the modulus, converting both values to positive unsigned values before using `%` and then adjusting the result will be faster, and no more difficult, than computing a signed remainder and adjusting it; if code only cares about whether the modulus/remainder is non-zero, letting the compiler return any convenient non-zero value would allow it to generate faster code].
In Eric’s library, both approaches have drawbacks. Testing bits relies on an implementation detail, and I think is less clear – I’d be relying on the fact that people are used to doing evenness tests that way, because of C history. Using the % operator is, as you say, less efficient. Eric has not been primarily concerned with efficiency, which is why I’d go with the clearer option myself.
In C, or normal integer maths in C-family languages, I’d hate the sematics of % that you describe. It makes % too complicated to easily remember, which will lead to bugs. It strikes me that a compiler could recognise for itself that the % was followed by a comparison with zero, and use your optimisation without any externally visible change in semantics or violation of the existing standard. Maybe they already do?
Another way that avoids both drawbacks, in C or in some hypothetical fully-featured version of this library, would be a method or function specifically for testing whether one number is an even multiple of the other, without %’s extra semantics. A method named “IsMultipleOf” or something returning boolean would be completely clear, and be able to be optimised.
The semantics for the “%” operator used to be that if either operand was negative the results were implementation defined, subject to the constraint that a=a*(a/b) = a%b. I can think of zero cases where I’ve wanted the remainder when ‘a’ was negative, and many where I’ve wanted the modulus; to compute the modulus of a potentially-negative value thus requires “m=a%b; if (m<0) m+=b;" If b happens to be a power of two (e.g. eight), having the compiler compute "r=a & 7; if (a < 0) r-=8;" just so that the following code can add 8 back is rather silly and pointless. Even if the compiler isn't going to take the time to consistently produce a useful modulus function, I'm not sure what value there is having it waste time in those cases where a useful modulus would naturally be produced, converting it into the useless remainder function.
Do you have a specific reason for handling the .IsDefault checks by just setting the value Zero way in the binary operators.
In several cases you could just directly return the final result from there instead without adding real complexity to the code.
E.g. x+0 is x, x-0 is x and x*0 is 0.
Correct. I wanted the entirely *mechanical* code in the method — this unfortunate need for checking for a default value has nothing whatsoever to do with the semantics of arithmetic — to be textually distinct from the *business* of the method.
Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1468
“Addition of a positive quantity and a negative quantity can be handled by turning them both into positive quantities and doing a subtraction:”
Doesn’t that give you the same problem as subtraction with two positive numbers:
1 + -5 results 1 – 5, which is not allowed.
1-5 is not allowed for naturals but for integers it is fine. If you look at the code there it handles the case fine. Though see elsewhere in comments for a suggested better implemenation.
Ah, I see, it uses Integer subtraction rather than Natural subtraction. I was confused because that came before the handling of Integer subtraction. I was expecting to see something like what Steffen posted, but his comment when reading the comments.
Pingback: Math from scratch, part eight: integers | Fabulous adventures in coding