nimber 0.1.1

//! Computation 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)

mod finite;

pub use finite::FiniteNimber;