From 45e0597762efa1bc14b29b7e1f7f0fc7cd4adb36 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Wed, 16 Apr 2025 07:14:25 +0100 Subject: [PATCH] Top-level intro documentation. --- src/lib.rs | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 80 insertions(+) diff --git a/src/lib.rs b/src/lib.rs index ce39975..d589580 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,3 +1,83 @@ +//! 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; -- 2.30.2