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 (including some further references in turn)