nettrash-a 0.0.24

//! Sums and products of iterators of numbers: [`Sum`] and [`Product`], of owned or borrowed
//! numbers.
//!
//! A sum is built in place, each number added to the sum so far. A product is built as a balanced
//! tree, so that the factors of each multiplication are about as long as each other: the product
//! of n numbers of one limb each, multiplied in turn, takes O(n²) time, as each step multiplies the
//! whole product so far by one limb; in a tree, its last steps are products of halves, which
//! Karatsuba's and Toom-Cook's methods multiply in less. Measured on an Apple M4 Max, the product
//! of the numbers from 1 to 10,000 took 10.5 million cycles in turn and 1.9 million as a tree, and
//! from 1 to 1,000 253,000 and 134,000.

use super::sign::trim;
use super::{ByteOrder, Number};
use core::iter::{Product, Sum};

/// A zero or one, little-endian, the sum or product of no numbers.
fn small(v: u8) -> Number {
    Number::new_from_u8(v, ByteOrder::LittleEndian)
}

/// The sum of the numbers of `iter`, in the byte order of the first and in the shortest form.
fn sum(mut iter: impl Iterator<Item = Number>) -> Number {
    let Some(first) = iter.next() else {
        return small(0);
    };
    let mut sum = Number {
        value: Vec::new(),
        negative: false,
        byte_order: first.byte_order,
    };
    sum += first;
    iter.fold(sum, |sum, x| sum + x)
}

/// The product of the numbers of `iter`, multiplied as a balanced tree, in the byte order of the
/// first and in the shortest form.
///
/// The partial products wait on a stack, each multiplied with the one below it while that one is
/// not longer, as a binary counter carries: so the product of n numbers of equal length is a
/// complete binary tree, and of numbers of different lengths one in which the factors of each
/// product are still of about equal length. The earlier factor is always the left one, so that the
/// result has the byte order of the first number.
fn product(iter: impl Iterator<Item = Number>) -> Number {
    let mut stack: Vec<Number> = Vec::new();
    for mut x in iter {
        while let Some(top) = stack.last()
            && top.value.len() <= x.value.len()
        {
            let top = stack.pop().unwrap_or_default();
            x = top * x;
        }
        stack.push(x);
    }
    let Some(mut product) = stack.pop() else {
        return small(1);
    };
    while let Some(below) = stack.pop() {
        product = below * product;
    }
    // A single number is the product as it is stored.
    trim(&mut product);
    product
}

impl Sum for Number {
    /// Returns the sum of the numbers, in the byte order of the first and in the shortest form,
    /// built in the vectors of the numbers; zero, little-endian, for none.
    ///
    /// # Examples
    ///
    /// ```
    /// use a::math::numbers::Number;
    ///
    /// let sum: Number = (1..=100).map(Number::from).sum();
    /// assert_eq!(sum, 5050);
    /// ```
    fn sum<I: Iterator<Item = Number>>(iter: I) -> Number {
        sum(iter)
    }
}

impl<'a> Sum<&'a Number> for Number {
    /// Returns the sum of the borrowed numbers, as for owned ones; the first is copied.
    fn sum<I: Iterator<Item = &'a Number>>(mut iter: I) -> Number {
        let Some(first) = iter.next() else {
            return small(0);
        };
        let mut sum = Number {
            value: Vec::new(),
            negative: false,
            byte_order: first.byte_order,
        };
        sum += first;
        iter.fold(sum, |sum, x| sum + x)
    }
}

impl Product for Number {
    /// Returns the product of the numbers, in the byte order of the first and in the shortest
    /// form, multiplied as a balanced tree; one, little-endian, for none.
    ///
    /// # Examples
    ///
    /// ```
    /// use a::math::numbers::Number;
    ///
    /// let factorial: Number = (1..=25u32).map(Number::from).product();
    /// assert_eq!(factorial.to_string(), "15511210043330985984000000");
    /// ```
    fn product<I: Iterator<Item = Number>>(iter: I) -> Number {
        product(iter)
    }
}

impl<'a> Product<&'a Number> for Number {
    /// Returns the product of the borrowed numbers, as for owned ones; each is copied once.
    fn product<I: Iterator<Item = &'a Number>>(iter: I) -> Number {
        product(iter.cloned())
    }
}