The `nimber` crate computes with "nimbers", aka Conway's
nim-arithmetic, aka **On**₂.
Nim-arithmetic consists of an alternative pair of definitions of
operations 'addition' and 'multiplication', which don't look like
the ordinary integer arithmetic operations, but are internally
consistent on their own terms. They're relevant to the theory of
impartial games, and also to lexicographic error-correcting codes.
# Finite nimbers
The nim-arithmetic operations can be applied to the non-negative
integers to turn them into an infinite field. In this field,
addition looks like bitwise XOR (and therefore the field has
_characteristic 2_, in that anything plus itself is 0).
Multiplication is defined inductively, and behaves much more
strangely. The [`FiniteNimber`] type in this module allows
computing with integers using these operations. A brief example
(see `FiniteNimber` itself for a longer demonstration):
```
use nimber::FiniteNimber;
// Addition of finite nimbers is just like bitwise XOR
let a = FiniteNimber::from(0b1010); // adding this
let b = FiniteNimber::from(0b1100); // to this
let s = FiniteNimber::from(0b0110); // gives this
assert_eq!(&a + &b, s);
// Because it's like XOR, adding any two of those gives the third
assert_eq!(&b + &s, a);
assert_eq!(&s + &a, b);
// Multiplication is very strange and doesn't look bitwise at all
let a = FiniteNimber::from(0x8000000000000000); // multiplying this
let b = FiniteNimber::from(0x4000000000000000); // by this
let p = FiniteNimber::from(0xb9c59257c5445713); // ... gives this!
assert_eq!(&a * &b, p);
// Nimbers form a field, so multiplication is invertible
assert_eq!(&p / &a, b);
assert_eq!(&p / &b, a);
```
The finite nimbers can be regarded as the 'quadratic completion'
of the finite field GF(2) with two elements: they are the smallest
field that contains GF(2) such that every quadratic equation has a
solution. The `FiniteNimber` type includes methods for solving
quadratic equations.
# Infinite nimbers
The nim-arithmetic operations can be extended beyond the integers,
in principle applying to any ordinal at all (making an algebraic
structure that behaves like a field except that it's too large to
count as a set!). General ordinals can't be represented fully in
any computer software. But _some_ infinite ordinals can be worked
with.
I believe it ought to be possible in principle to implement
nim-arithmetic for the ordinals up to ω^(ω^ω), which together form
a field that is the _algebraic_ completion of GF(2), that is, it
contains a full set of solutions for every polynomial equation of
any degree. I haven't done that _yet_, but that's why the
`FiniteNimber` type in this crate is not just called `Nimber`: I'm
leaving space alongside it for a potential `AlgebraicNimber` type.
# References
For more information on nimbers in general, and more formal
treatments including proofs:
* John Conway, "On Numbers and Games", Academic Press, 1976.
Chapter 6, "The Curious Field **On**₂"
* John Conway and Neil Sloane, "Lexicographic Codes:
Error-Correcting Codes from Game Theory", IEEE Trans. Information
Theory, 32 (1986), pp. 337–348. Section 2.9 defines nim-addition
and nim-multiplication.
* [Nimbers on Wikipedia](https://en.wikipedia.org/wiki/Nimber)
(including some further references in turn)