From a9f00663307062147db3ca3c5418f541c399476b Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Sun, 13 Apr 2025 14:18:12 +0100 Subject: [PATCH] Documentation, including internal methods. --- examples/a382121.rs | 9 +- src/finitenimber.rs | 624 +++++++++++++++++++++++++++++++++++++++++--- src/lib.rs | 1 - 3 files changed, 597 insertions(+), 37 deletions(-) diff --git a/examples/a382121.rs b/examples/a382121.rs index 1159fc1..ce8d9d9 100644 --- a/examples/a382121.rs +++ b/examples/a382121.rs @@ -1,16 +1,13 @@ use itertools::Itertools; -use std::borrow::Borrow; use std::collections::hash_map::Entry; use std::collections::HashMap; use std::fmt::{Display, Formatter}; use std::ops::AddAssign; -use nimber::{FiniteNimber, Word}; +use nimber::FiniteNimber; fn lowest_set_bit(n: &FiniteNimber) -> Option { - let words: &[nimber::Word] = n.borrow(); - - for (i, word) in words.iter().cloned().enumerate() { + for (i, word) in n.as_slice().iter().cloned().enumerate() { if word != 0 { let tz: usize = word.trailing_zeros().try_into().expect( "a number of leading zeros can't be too big to fit in a usize", @@ -104,7 +101,7 @@ fn largest_nimber_in_subfield(level: usize) -> FiniteNimber { None => FiniteNimber::from((1 << (1 << level)) - 1), Some(wordlevel) => { let words = 1 << wordlevel; - let v: Vec = + let v: Vec<_> = std::iter::repeat(0xffffffffffffffff).take(words).collect(); FiniteNimber::from(v) } diff --git a/src/finitenimber.rs b/src/finitenimber.rs index f0be307..bb1b79e 100644 --- a/src/finitenimber.rs +++ b/src/finitenimber.rs @@ -1,37 +1,216 @@ -use core::borrow::Borrow; +//! Internal module of the `nimber` crate dealing with finite nimbers. +//! +//! The type [`FiniteNimber`] is exported as a public type by the +//! top-level module. It's a singleton struct wrapping +//! [`FiniteNimberEnum`]. + use core::cmp::max; use core::fmt::{Debug, Display, Formatter}; -use core::ops::{Add, Div, Mul, Sub}; +use core::ops::{Add, Div, Mul, Neg, Sub}; use itertools::Itertools; -pub type Word = u64; // element type of the vectors we use +/// Alias for the `u64` type, used within the implementation as the +/// element type of [`FiniteNimber`] and [`FiniteNimberRef`]. +type Word = u64; + +/// The largest "level" of any nimber that fits in a [`Word`]. See +/// [`FiniteNimberRef`] for an explanation of levels. const WORDLEVELS: usize = 6; // 2^{2^6} = 64 = size of Word /// A type representing a finite nimber. +/// +/// This type has no upper bound: it can represent _any_ finite +/// nimber, in principle (limited only by available memory). For this +/// reason, it implements [`Clone`] but not [`Copy`], because cloning +/// it may require a memory allocation. However, _small_ nimbers +/// (fitting in one `u64`) are stored without an extra memory +/// allocation at all, for speed. +/// +/// Nimbers can be constructed using the [`From`] trait, either +/// starting from a single [`u64`] for small nimbers, or from a +/// [`Vec`] or slice of [`u64`] for larger ones. In the vector or +/// slice case, the values you provide are taken in a little-endian +/// manner, so that the first `u64` in the list represents the +/// low-order bits of the overall number. +/// +/// Most operations on nimbers are performed using the ordinary `+`, +/// `*` and `/` operators (and `-` if you like, although nimbers have +/// characteristic 2, it's the same as `+`). These can be applied to +/// any combination of `FiniteNimber` and `&FiniteNimber`. +/// +/// `FiniteNimber` also provides a few extra arithmetic operations as +/// ordinary methods, like [`FiniteNimber::sqrt`]. +/// +/// To extract the results of a nimber calculation into another type, +/// you can retrieve an `&[u64]` via the [`FiniteNimber::as_slice`] +/// method. You can also format nimbers for output using [`Display`]. +/// +/// # Examples +/// +/// ``` +/// use nimber::FiniteNimber; +/// +/// // Two different ways to make the same nimber +/// assert_eq!(FiniteNimber::from(0xfedcba9876543210u64), +/// FiniteNimber::from(&[0xfedcba9876543210u64, 0])); +/// +/// // Arithmetic operations via std::ops overloading +/// assert_eq!(FiniteNimber::from(0xf0f0) + FiniteNimber::from(0xff00), +/// FiniteNimber::from(0x0ff0)); // addition just looks like XOR +/// assert_eq!(FiniteNimber::from(0xf0f0) - FiniteNimber::from(0xff00), +/// FiniteNimber::from(0x0ff0)); // subtraction is same as addition +/// assert_eq!(FiniteNimber::from(0x8000) * FiniteNimber::from(0x4000), +/// FiniteNimber::from(0xb9c5)); // multiplication is weirder! +/// assert_eq!(FiniteNimber::from(0xb9c5) / FiniteNimber::from(0x8000), +/// FiniteNimber::from(0x4000)); // and division inverts it +/// +/// // Extra operations via dedicated FiniteNimber methods +/// assert_eq!(FiniteNimber::from(0x8000).square(), +/// FiniteNimber::from(0xde4a)); // faster way to multiply by self +/// assert_eq!(FiniteNimber::from(0xde4a).sqrt(), +/// FiniteNimber::from(0x8000)); // square root inverts squaring +/// +/// // Get the results back out as a slice of u64 +/// assert_eq!(FiniteNimber::from(0x8000).square().as_slice(), &[0xde4a]); +/// let big_nimber = FiniteNimber::from(&[0, 0x8000000000000000]); +/// assert_eq!(big_nimber.square().as_slice(), +/// &[0xe3a92850a9218171, 0xde4ae3a94a88a921]); +/// +/// // Or format for display, using the * prefix notation from game theory. +/// // This displays large numbers as if they were integers, so the highest- +/// // order digit comes first. +/// assert_eq!(format!("{}", FiniteNimber::from(0x1234)), "*0x1234"); +/// assert_eq!(format!("{}", FiniteNimber::from(&[1, 2, 3])), +/// "*0x300000000000000020000000000000001"); +/// assert_eq!(format!("{}", big_nimber.square()), +/// "*0xde4ae3a94a88a921e3a92850a9218171"); +/// ``` #[derive(Clone, PartialEq, Eq, Hash)] pub struct FiniteNimber(FiniteNimberEnum); -/// A type representing a finite nimber. +/// Enumeration forming the guts of [`FiniteNimber`]. Large finite +/// nimbers are stored as a `Vec`, but small ones are stored +/// directly, which means that the lowest few levels of each recursive +/// algorithm can run without needing any memory allocation. #[derive(Clone, PartialEq, Eq, Hash)] enum FiniteNimberEnum { + /// A nimber of level 6 or below, that is, with an integer value + /// less than 2^64, is stored in this branch by directly storing + /// that integer. Single(Word), + + /// A nimber of level > 6 is stored in this branch, as a vector of + /// `u64`. The vector is always non-empty, and its length is + /// normalised so that the last element is nonzero. Vector(Vec), } +/// Internal type representing a reference to a [`FiniteNimber`]. Most +/// of the actual arithmetic implementation lives in methods of this +/// type; the trait implementations on `FiniteNimber` itself are +/// mostly small wrappers. +/// +/// The key concept in computing with finite nimbers is a _level_. +/// The field of finite nimbers consists of a nested sequence of +/// finite fields of size 2^(2^n): the field of order 2, nested +/// inside the field of order 4, then 16, 256, 65536, etc. A +/// nimber's "level" is the index in this sequence of the smallest +/// subfield that contains it. +/// +/// In other words: +/// * the nimbers *0 and *1 have level 0 +/// * the nimbers *2 and *3 have level 1 +/// * the nimbers *4 to *15 inclusive have level 2 +/// * the nimbers *16 to *255 inclusive have level 3, etc. +/// +/// Most nimber calculation algorithms (except addition, which is +/// exceptionally simple) involve recursing to lower and lower levels, +/// by splitting a nimber at level n into two half-sized nimbers at +/// level n−1, then separately calculating the two half-sized parts +/// of the answer by arithmetic on the smaller nimbers, then joining +/// the two halves back together for output. +/// +/// The recursive functions implementing nimber arithmetic will take a +/// parameter `level` giving the (maximum) level of the input nimbers, +/// which makes it easy to determine their remaining recursion depth. +/// The top-level wrappers in `FiniteNimber` will call +/// [`FiniteNimberRef::level`] to find the level(s) of their input +/// nimbers, and use that to start the recursion. +/// +/// In the descriptions of these recursive algorithms, we'll refer to +/// the variable t, which is the nimber \*2^(2^(n−1)), i.e. the +/// smallest nimber that has level n. This nimber t has the useful +/// property that multiplying it by any smaller nimber works the same +/// way in the strange nimber multiplication as it does in ordinary +/// integers: that is, if a { + /// A nimber of level 6 or below, that is, with an integer value + /// less than 2^64, is stored in this branch by directly storing + /// that integer. Single(Word), + + /// A nimber of level > 6 is stored in this branch, as a reference + /// to a slice of `u64`. The slice is always non-empty, and its + /// length is normalised so that the last element is nonzero. Slice(&'a [Word]), } impl Debug for FiniteNimber { + /// The debug representation of a `FiniteNimber` is displayed with + /// parentheses if it's stored internally as a single word without + /// a subsidiary memory allocation, or square brackets if it's + /// stored via an auxiliary `Vec`. + /// + /// In the latter case, the elements of the `Vec` are shown + /// individually, in little-endian order, matching the storage + /// representation. + /// + /// # Examples + /// + /// ``` + /// use nimber::FiniteNimber; + /// + /// assert_eq!(format!("{:?}", FiniteNimber::from(0x1234)), + /// "FiniteNimber(0x0000000000001234)"); + /// assert_eq!(format!("{:?}", FiniteNimber::from(&[0x1234, 0x5678])), + /// "FiniteNimber[0x0000000000001234, 0x0000000000005678]"); + /// ``` fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), core::fmt::Error> { match &self.0 { FiniteNimberEnum::Single(v) => { - write!(f, "FiniteNimberEnum::Single(0x{:16x})", v) + write!(f, "FiniteNimber(0x{:016x})", v) } FiniteNimberEnum::Vector(s) => { - write!(f, "FiniteNimberEnum::Vector[")?; + write!(f, "FiniteNimber[")?; let mut sep: &str = ""; for v in s { write!(f, "{}0x{:016x}", sep, v)?; @@ -47,10 +226,10 @@ impl Debug for FiniteNimberRef<'_> { fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), core::fmt::Error> { match self { FiniteNimberRef::Single(v) => { - write!(f, "FiniteNimberRef::Single(0x{:16x})", v) + write!(f, "FiniteNimberRef(0x{:16x})", v) } FiniteNimberRef::Slice(s) => { - write!(f, "FiniteNimberRef::Slice[")?; + write!(f, "FiniteNimberRef[")?; let mut sep: &str = ""; for v in *s { write!(f, "{}0x{:016x}", sep, v)?; @@ -63,6 +242,39 @@ impl Debug for FiniteNimberRef<'_> { } impl Display for FiniteNimber { + /// Format a `FiniteNimber` for user-friendly display. + /// + /// The general format is a `*` indicating a nimber, followed by a + /// hex number, e.g. `*0x1234`. However, for nimbers with value + /// less than 10, the `0x` is omitted, so in particular you get + /// `*0` and `*1`. + /// + /// At present, the only supported formatting option is the + /// "alternate" flag. This causes the `0x` never to be omitted, so + /// that nimbers look more consistent with each other. + /// + /// # Examples + /// + /// ``` + /// use nimber::FiniteNimber; + /// + /// // Some general examples + /// assert_eq!(format!("{}", FiniteNimber::from(0x1234)), "*0x1234"); + /// let big = FiniteNimber::from( + /// &[0xe3a92850a9218171, 0xde4ae3a94a88a921]); + /// assert_eq!(format!("{}", big), "*0xde4ae3a94a88a921e3a92850a9218171"); + /// + /// // 0x is omitted for 0,1,...,9, but not for 10 + /// assert_eq!(format!("{}", FiniteNimber::from(0)), "*0"); + /// assert_eq!(format!("{}", FiniteNimber::from(1)), "*1"); + /// assert_eq!(format!("{}", FiniteNimber::from(9)), "*9"); + /// assert_eq!(format!("{}", FiniteNimber::from(10)), "*0xa"); + /// + /// // The alternate # flag makes the 0x unconditional + /// assert_eq!(format!("{:#}", FiniteNimber::from(0)), "*0x0"); + /// assert_eq!(format!("{:#}", FiniteNimber::from(1)), "*0x1"); + /// assert_eq!(format!("{:#}", FiniteNimber::from(9)), "*0x9"); + /// ``` fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), core::fmt::Error> { let r = self.to_ref(); if !f.alternate() && r.level() < WORDLEVELS && r.low_word() < 10 { @@ -86,17 +298,23 @@ impl Display for FiniteNimber { } } -impl Borrow<[Word]> for FiniteNimber { - fn borrow(&self) -> &[Word] { - self.as_slice() +impl Default for FiniteNimber { + /// The default value for a nimber is zero. + fn default() -> Self { + Self(FiniteNimberEnum::Single(0)) } } +/// Some low-level administrative methods. impl<'a> FiniteNimberRef<'a> { + /// The `FiniteNimberRef` representing zero. fn zero() -> Self { FiniteNimberRef::Single(0) } + /// Return the low-order `Word` of a `FiniteNimberRef`. If you've + /// determined via [`FiniteNimberRef::level()`] that its level is + /// at most [`WORDLEVELS`], then this is the _whole_ of the value. fn low_word(self) -> Word { match self { FiniteNimberRef::Single(v) => v, @@ -106,6 +324,11 @@ impl<'a> FiniteNimberRef<'a> { } } + /// Return a `&[Word]` representing the contents of a + /// `FiniteNimberRef`. Because a single word might be stored + /// directly in the `FiniteNimberRef` itself, this method requires + /// a `&FiniteNimberRef`: it can't work on a `FiniteNimberRef` + /// passed by value. fn as_slice<'b, 'c>(&'b self) -> &'c [Word] where 'a: 'c, @@ -117,6 +340,7 @@ impl<'a> FiniteNimberRef<'a> { } } + /// Calculate the "level" of a finite nimber. fn level(self) -> usize { fn word_level(w: Word) -> usize { let log_w: u32 = @@ -144,6 +368,26 @@ impl<'a> FiniteNimberRef<'a> { } } + /// Split a nimber into two half-sized nimbers, with the output + /// nimbers having level at most `level`. If the output + /// `FiniteNimberRef` are large enough, this is implemented by + /// returning sub-slice references into the slice held by the + /// original one, so this operation is fast. + /// + /// The returned tuple from `split()` contains the low half and + /// then the high half. + /// + /// For example, if `x` is the nimber \*0x1234 and you split it at + /// level 3: `t` is the nimber *(2^(2^3)), or \*0x100, so you can + /// write `x = xhi * t + xlo` with `xhi` being \*0x12 and `xlo` + /// being \*0x34. So `x.split(3)` gives (\*0x34,\*0x12) (or rather, + /// `FiniteNimberRef` objects containing those values). + /// + /// If the input nimber has level greater than `level+1`, then + /// this function will return its low 2^(2^(level+1)) bits, + /// discarding any higher-order bits. For example, with `x` equal + /// to \*0x1234 as above, `x.split(2)` will give (\*0x4, \*0x3), + /// discarding the 0x12 at the top. This probably isn't useful. fn split( self, level: usize, @@ -191,6 +435,23 @@ impl<'a> FiniteNimberRef<'a> { } } + /// Join two half-sized nimbers into a bigger one, with the input + /// nimbers having level at most `level`. This can't be done in + /// general in a way that generates a `FiniteNimberRef` as output: + /// it requires allocating a new `FiniteNimber`. + /// + /// This is the inverse of [`FiniteNimberRef::split()`], and takes + /// the same `level` value (hence why `level` is the size of the + /// outputs for `split` and the inputs for `join`). + /// + /// For example, if x and y are the nimbers \*0x34 and \*0x12 + /// respectively, then `x.join(y, 3)` is the nimber \*0x1234, and + /// `x.join(y, 4)` is \*0x120034. + /// + /// As with `split`, if the input nimbers are too large, then + /// their higher bits are discarded. For example, with `x`,`y` as + /// above, `x.join(y, 2)` gives \*0x24, discarding the high digit + /// of each input. fn join(self, hi: FiniteNimberRef<'_>, level: usize) -> FiniteNimber { match level.checked_sub(WORDLEVELS) { None => { @@ -237,13 +498,6 @@ impl FiniteNimber { }, } } - - fn as_slice(&self) -> &[Word] { - match &self.0 { - FiniteNimberEnum::Single(w) => core::slice::from_ref(w), - FiniteNimberEnum::Vector(v) => &v, - } - } } impl<'a> From<&'a FiniteNimber> for FiniteNimberRef<'a> { @@ -262,12 +516,18 @@ impl From> for FiniteNimber { } impl From for FiniteNimber { + /// Make a `FiniteNimber` out of a single integer. fn from(val: Word) -> FiniteNimber { Self(FiniteNimberEnum::Single(val)) } } impl From> for FiniteNimber { + /// Make a `FiniteNimber` out of a list of integers provided as a + /// `Vec`. These 64-bit integers are regarded as representing + /// one big integer, in little-endian order, so that the first + /// integer in the list is treated as the least significant 64 + /// bits of the represented integer. fn from(mut vec: Vec) -> FiniteNimber { match vec .iter() @@ -286,6 +546,11 @@ impl From> for FiniteNimber { } impl From<&[Word]> for FiniteNimber { + /// Make a `FiniteNimber` out of a list of integers provided as a + /// slice reference. These 64-bit integers are regarded as + /// representing one big integer, in little-endian order, so that + /// the first integer in the list is treated as the least + /// significant 64 bits of the represented integer. fn from(slice: &[Word]) -> FiniteNimber { match slice .iter() @@ -303,13 +568,21 @@ impl From<&[Word]> for FiniteNimber { } impl From<&[Word; N]> for FiniteNimber { + /// Make a `FiniteNimber` out of a list of integers provided as an + /// array reference. These 64-bit integers are regarded as + /// representing one big integer, in little-endian order, so that + /// the first integer in the list is treated as the least + /// significant 64 bits of the represented integer. fn from(array: &[Word; N]) -> FiniteNimber { FiniteNimber::from(array as &[Word]) } } +/// Macro to implement a binary operation and its associated +/// assignment operator on all meaningful combinations of +/// `FiniteNimber` and `&FiniteNimber`. macro_rules! impl_binop_wrappers { - ($trait:tt, $fn:ident, $assigntrait:tt, $assignfn:ident) => { + ($trait:tt, $fn:ident, $assigntrait:tt, $assignfn:ident, $comment:literal) => { impl $trait> for FiniteNimber { type Output = FiniteNimber; fn $fn(self, other: FiniteNimberRef<'_>) -> FiniteNimber { @@ -329,7 +602,11 @@ macro_rules! impl_binop_wrappers { } impl $trait<&FiniteNimber> for &FiniteNimber { + /// The result of combining two `FiniteNimber` with an + /// arithmetic operation is another `FiniteNimber`, which + /// must be newly allocated. type Output = FiniteNimber; + #[doc=$comment] fn $fn(self, other: &FiniteNimber) -> FiniteNimber { let aref: FiniteNimberRef = self.into(); let bref: FiniteNimberRef = other.into(); @@ -338,7 +615,11 @@ macro_rules! impl_binop_wrappers { } impl $trait<&FiniteNimber> for FiniteNimber { + /// The result of combining two `FiniteNimber` with an + /// arithmetic operation is another `FiniteNimber`, which + /// must be newly allocated. type Output = FiniteNimber; + #[doc=$comment] fn $fn(self, other: &FiniteNimber) -> FiniteNimber { let aref: FiniteNimberRef = (&self).into(); let bref: FiniteNimberRef = other.into(); @@ -347,7 +628,11 @@ macro_rules! impl_binop_wrappers { } impl $trait for &FiniteNimber { + /// The result of combining two `FiniteNimber` with an + /// arithmetic operation is another `FiniteNimber`, which + /// must be newly allocated. type Output = FiniteNimber; + #[doc=$comment] fn $fn(self, other: FiniteNimber) -> FiniteNimber { let aref: FiniteNimberRef = self.into(); let bref: FiniteNimberRef = (&other).into(); @@ -356,7 +641,11 @@ macro_rules! impl_binop_wrappers { } impl $trait for FiniteNimber { + /// The result of combining two `FiniteNimber` with an + /// arithmetic operation is another `FiniteNimber`, which + /// must be newly allocated. type Output = FiniteNimber; + #[doc=$comment] fn $fn(self, other: FiniteNimber) -> FiniteNimber { let aref: FiniteNimberRef = (&self).into(); let bref: FiniteNimberRef = (&other).into(); @@ -365,6 +654,7 @@ macro_rules! impl_binop_wrappers { } impl core::ops::$assigntrait<&FiniteNimber> for FiniteNimber { + #[doc=$comment] fn $assignfn(&mut self, other: &FiniteNimber) { let aref: FiniteNimberRef = (&self as &FiniteNimber).into(); let bref: FiniteNimberRef = other.into(); @@ -373,6 +663,7 @@ macro_rules! impl_binop_wrappers { } impl core::ops::$assigntrait for FiniteNimber { + #[doc=$comment] fn $assignfn(&mut self, other: FiniteNimber) { let aref: FiniteNimberRef = (&self as &FiniteNimber).into(); let bref: FiniteNimberRef = (&other).into(); @@ -403,7 +694,32 @@ impl<'a, 'b> Sub> for FiniteNimberRef<'b> { } } +/// Internal functions having to do with multiplication. impl<'a> FiniteNimberRef<'a> { + /// Recursively multiply a nimber by the special value + /// \*(2^(2^level−1)). + /// + /// This is a separate method from multiplication for two reasons. + /// Firstly, it's more efficient than general multiplication + /// (because if h itself is split into two halves, one of the + /// halves is zero and can be ignored); secondly, it's a necessary + /// _subroutine_ of general multiplication. + /// + /// When we call this routine from another context, we think of it + /// as multiplying by h, where h is the value in the squaring + /// equation t^2 = t+h described above. But _within_ the context + /// of this method, `level` is one less, so we have our own + /// smaller value of h, and the value our caller wants us to + /// multiply by is h\*t, in our terms. + /// + /// The formula for multiplication by h\*t is + /// + /// ```text + /// (ah t + al) h t + /// = ah h t^2 + al h + /// = ah h (t + h) + al h + /// = (ah h) t + (ah h + al) h + /// ``` fn mul_by_h(self, level: usize) -> FiniteNimber { match level.checked_sub(1) { Some(sublevel) => { @@ -423,6 +739,25 @@ impl<'a> FiniteNimberRef<'a> { } } + /// Recursively calculate the square of a nimber. Underlies the + /// public method [`FiniteNimber::square`], and is also used as a + /// subroutine in other arithmetic implementations. + /// + /// This is faster than general multiplication because squaring a + /// sum in any field of characteristic 2 has a particularly simple + /// formula: instead of (a+b)^2 = a^2+2ab+b^2 as usual, the + /// cross-term 2ab vanishes, because we're working mod 2. So you + /// just get (a+b)^2 = a^2 + b^2, which looks like a schoolchild + /// mistake, but in this context, is perfectly true! + /// + /// So the formula for squaring a = ah\*t+al is + /// + /// ```text + /// (ah t + al)^2 + /// = ah^2 t^2 + al^2 + /// = ah^2 (t + h) + al^2 + /// = (ah^2) t + (ah^2 h + al^2) + /// ``` fn square_recurse(self, level: usize) -> FiniteNimber { match level.checked_sub(1) { Some(sublevel) => { @@ -439,6 +774,41 @@ impl<'a> FiniteNimberRef<'a> { } } + /// Recursively multiply two nimbers. Underlies the [`Mul`] + /// implementations on `FiniteNimber` itself. + /// + /// The most obvious formula for multiplying a = ah\*t+al by b = + /// bh\*t+bl is + /// + /// ```text + /// (ah t + al)(bh t + bl) + /// = ah bh t^2 + ah bl t + al bh t + al bl + /// = ah bh (t + h) + ah bl t + al bh t + al bl + /// = (ah bh + ah bl + al bh) t + (ah bh h + al bl) + /// ``` + /// + /// But this requires four smaller multiplications, which can be + /// reduced to three by a variant of the Karatsuba optimisation. + /// First compute the following value, using a single half-sized + /// multiplication: + /// + /// ```text + /// k = (ah + al)(bh + bl) = ah bh + ah bl + al bh + al bl + /// ``` + /// + /// Then the `t` coefficient in the above product formula contains + /// three of the four terms in `k`. The missing one is `al bl`, + /// which we needed to compute anyway for the other coefficient. + /// + /// So after computing `k`, we use two more half-sized + /// multiplications to compute `ah bh` and `al bl`, and then + /// combine those three smaller products using the following + /// formula, which uses `al bl` twice, and involves nothing but + /// addition and multiplication by the special value h: + /// + /// ```text + /// (k + al bl) t + (ah bh h + al bl) + /// ``` fn mul_recurse( self, other: FiniteNimberRef<'a>, @@ -471,7 +841,52 @@ impl<'a, 'b> Mul> for FiniteNimberRef<'b> { } } +/// Internal functions having to do with division. impl<'a> FiniteNimberRef<'a> { + /// Recursively calculate the multiplicative inverse of a finite + /// nimber. Underlies the [`Div`] implementations on + /// `FiniteNimber` itself, which compute a/b by finding the + /// inverse of b and then multiplying by a. + /// + /// We do this by rearranging into a form where we only have to + /// divide by a nimber at the next smaller level, and recursing. + /// + /// There are several ways to derive the same formula for the + /// inverse of a number; one involves inverting a matrix, and one + /// involves highfalutin' stuff about Galois conjugates (an + /// extension of the standard trick for dividing by a complex + /// number by multiplying top and bottom by its complex + /// conjugate). I think this derivation is simpler than either: + /// + /// We're after a number u such that (uh t + ul)(ah t + al), + /// multiplied out and reduced via t^2=t+h so that it's a + /// polynomial in t of degree < 2, comes out to 0t+1. So we need + /// its t coefficient to be 0. By the unoptimised version of the + /// product formula, that t coefficient comes to + /// + /// ```text + /// (uh ah + uh al + ul ah) = (ah + al) uh + (ah) ul + /// ``` + /// + /// To make that zero, we need to choose any two numbers uh,ul in + /// the right ratio, that is, such that uh/ul = (ah)/(ah+al). One + /// very obvious choice is to take uh=ah and ul=ah+al, so that + /// those two fractions are obviously equal because we're dividing + /// the exact same pair of numbers on both sides. + /// + /// So the product (ah t + ah + al)(ah t + al) has t coefficient + /// zero. So we can work out what the rest of it comes to, and + /// divide by that to scale the output to be 1. + /// + /// Omitting the boring algebra of multiplying that out, this + /// leads to the following formula for the inverse of (ah t + al): + /// + /// ```text + /// (ah t + ah + al) / (al (ah + al) + ah^2 h) + /// ``` + /// + /// where the denominator has no t in it, so it can be done by + /// inversion at the next smaller level. fn inverse_recurse(self, level: usize) -> Option { match level.checked_sub(1) { Some(sublevel) => { @@ -506,7 +921,38 @@ impl<'a, 'b> Div> for FiniteNimberRef<'b> { } } +/// Internal functions having to do with square root. impl<'a> FiniteNimberRef<'a> { + /// Recursively calculate the square root of a nimber. Underlies + /// the public method [`FiniteNimber::sqrt`]. + /// + /// To derive a formula for square root, we invert the formula for + /// squaring. We want r such that r^2 = a. The documentation for + /// [`FiniteNimberRef::square_recurse`] derives the squaring + /// formula as + /// + /// ```text + /// (rh t + rl)^2 = (rh^2) t + (rh^2 h + rl^2) + /// ``` + /// + /// Setting this equal to the input `ah t + al` and equating + /// coefficients, we get two equations + /// + /// ```text + /// rh^2 = ah + /// rh^2 h + rl^2 = al + /// ``` + /// + /// Simplifying the second equation using the first and + /// rearranging gives + /// + /// ```text + /// rh^2 = ah + /// rl^2 = ah h + al + /// ``` + /// + /// and so we can compute each half of `r` by calculating the RHS + /// of one of those equations and taking its square root. fn sqrt_recurse(self, level: usize) -> FiniteNimber { match level.checked_sub(1) { Some(sublevel) => { @@ -524,9 +970,47 @@ impl<'a> FiniteNimberRef<'a> { } impl FiniteNimber { - /// Compute the square of a nimber, faster than the general - /// multiplication algorithm performed by the `Mul` trait can do - /// it. + /// Allows the binary representation of a `FiniteNimber` to be + /// extracted and examined by client code. + /// + /// The returned slice of `u64` is arranged in little-endian + /// order, exactly the same as you would pass to `FiniteNimber::from`. + /// + /// The slice always has at least one element. The last element in + /// the slice (representing the highest-order 64-bit chunk) is + /// always nonzero, except when the nimber is 0, in which case the + /// slice has a single element 0. + /// + /// # Examples + /// + /// ``` + /// use nimber::FiniteNimber; + /// + /// assert_eq!(FiniteNimber::default().as_slice(), &[0]); + /// assert_eq!(FiniteNimber::from(1).as_slice(), &[1]); + /// assert_eq!(FiniteNimber::from(&[1, 2, 0, 0, 0]).as_slice(), &[1, 2]); + /// ``` + pub fn as_slice(&self) -> &[Word] { + match &self.0 { + FiniteNimberEnum::Single(w) => core::slice::from_ref(w), + FiniteNimberEnum::Vector(v) => &v, + } + } + + /// Compute the square of a nimber, just like multiplying it by + /// itself in the ordinary way. This method is faster than the + /// general multiplication algorithm performed by the `Mul` trait, + /// so if you _know_ you're squaring a number, it helps to use + /// this method instead of writing `&x * &x`. + /// + /// # Examples + /// + /// ``` + /// use nimber::FiniteNimber; + /// + /// let x = FiniteNimber::from(&[0x3141592653589793, 0x2718281828459045]); + /// assert_eq!(x.square(), &x * &x); + /// ``` pub fn square(&self) -> FiniteNimber { let r = self.to_ref(); r.square_recurse(r.level()) @@ -536,16 +1020,99 @@ impl FiniteNimber { /// square root, and the square root of a finite nimber is finite. /// So this function can't fail, and doesn't need to return a list /// or a tuple or anything more complicated than a single nimber. + /// + /// # Examples + /// + /// ``` + /// use nimber::FiniteNimber; + /// + /// let x = FiniteNimber::from(&[0x3141592653589793, 0x2718281828459045]); + /// assert_eq!(x.square().sqrt(), x); + /// assert_eq!(x.sqrt().square(), x); + /// ``` pub fn sqrt(&self) -> FiniteNimber { let r = self.to_ref(); r.sqrt_recurse(r.level()) } } -impl_binop_wrappers!(Add, add, AddAssign, add_assign); -impl_binop_wrappers!(Sub, sub, SubAssign, sub_assign); -impl_binop_wrappers!(Mul, mul, MulAssign, mul_assign); -impl_binop_wrappers!(Div, div, DivAssign, div_assign); +impl_binop_wrappers!( + Add, + add, + AddAssign, + add_assign, + r##" + +Addition of finite nimbers behaves like bitwise XOR on unsigned +integers. + +"## +); +impl_binop_wrappers!( + Sub, + sub, + SubAssign, + sub_assign, + r##" + +Subtraction of finite nimbers behaves just like addition, i.e. like +bitwise XOR on unsigned integers. This is due to the field of nimbers +having characteristic 2, i.e. it is such that `x + x = 0` for any `x`, +so that `-x` is the same as `x`. + +"## +); +impl_binop_wrappers!( + Mul, + mul, + MulAssign, + mul_assign, + r##" + +Multiplication of finite nimbers has the property that if the two +input nimbers both fitted in 2^n bits, then so does the output. + +"## +); +impl_binop_wrappers!( + Div, + div, + DivAssign, + div_assign, + r##" + +Division of finite nimbers has the property that if the two input +nimbers both fitted in 2^n bits, then so does the output. + +Dividing by the zero nimber causes a panic. + +"## +); + +impl Neg for FiniteNimber { + /// The result of negating a `FiniteNimber` is another + /// `FiniteNimber`. + type Output = Self; + + /// Since nimbers have characteristic 2, negating a nimber leaves + /// it unchanged. So the unary - operator has no effect. + fn neg(self) -> Self { + self + } +} + +impl<'a> Neg for &'a FiniteNimber { + /// Since negation of nimbers is the identity function, this is + /// the one arithmetic operation where we can return a reference, + /// namely the same reference passed in. + type Output = &'a FiniteNimber; + + /// Since nimbers have characteristic 2, negating a nimber leaves + /// it unchanged. So the unary - operator has no effect. + fn neg(self) -> Self { + self + } +} #[cfg(test)] mod tests { @@ -695,10 +1262,7 @@ mod tests { ); assert_eq!(FiniteNimber::from(&[0x55, 0, 0, 0]).to_ref().level(), 3); - assert_eq!( - FiniteNimber::from(&[0x55, 1, 0, 0]).to_ref().level(), - 7 - ); + assert_eq!(FiniteNimber::from(&[0x55, 1, 0, 0]).to_ref().level(), 7); assert_eq!(FiniteNimber::from(&[0x55, 1, 1, 0]).to_ref().level(), 8); assert_eq!(FiniteNimber::from(&[0x55, 1, 1, 1]).to_ref().level(), 8); assert_eq!( diff --git a/src/lib.rs b/src/lib.rs index ed6ff49..bc692dc 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,4 +1,3 @@ mod finitenimber; -pub use finitenimber::Word; pub use finitenimber::FiniteNimber; -- 2.30.2