a/math/numbers/
iter.rs

1//! Sums and products of iterators of numbers: [`Sum`] and [`Product`], of owned or borrowed
2//! numbers.
3//!
4//! A sum is built in place, each number added to the sum so far. A product is built as a balanced
5//! tree, so that the factors of each multiplication are about as long as each other: the product
6//! of n numbers of one limb each, multiplied in turn, takes O(n²) time, as each step multiplies the
7//! whole product so far by one limb; in a tree, its last steps are products of halves, which
8//! Karatsuba's and Toom-Cook's methods multiply in less. Measured on an Apple M4 Max, the product
9//! of the numbers from 1 to 10,000 took 10.5 million cycles in turn and 1.9 million as a tree, and
10//! from 1 to 1,000 253,000 and 134,000.
11
12use super::sign::trim;
13use super::{ByteOrder, Number};
14use core::iter::{Product, Sum};
15
16/// A zero or one, little-endian, the sum or product of no numbers.
17fn small(v: u8) -> Number {
18    Number::new_from_u8(v, ByteOrder::LittleEndian)
19}
20
21/// The sum of the numbers of `iter`, in the byte order of the first and in the shortest form.
22fn sum(mut iter: impl Iterator<Item = Number>) -> Number {
23    let Some(first) = iter.next() else {
24        return small(0);
25    };
26    let mut sum = Number {
27        value: Vec::new(),
28        negative: false,
29        byte_order: first.byte_order,
30    };
31    sum += first;
32    iter.fold(sum, |sum, x| sum + x)
33}
34
35/// The product of the numbers of `iter`, multiplied as a balanced tree, in the byte order of the
36/// first and in the shortest form.
37///
38/// The partial products wait on a stack, each multiplied with the one below it while that one is
39/// not longer, as a binary counter carries: so the product of n numbers of equal length is a
40/// complete binary tree, and of numbers of different lengths one in which the factors of each
41/// product are still of about equal length. The earlier factor is always the left one, so that the
42/// result has the byte order of the first number.
43fn product(iter: impl Iterator<Item = Number>) -> Number {
44    let mut stack: Vec<Number> = Vec::new();
45    for mut x in iter {
46        while let Some(top) = stack.last()
47            && top.value.len() <= x.value.len()
48        {
49            let top = stack.pop().unwrap_or_default();
50            x = top * x;
51        }
52        stack.push(x);
53    }
54    let Some(mut product) = stack.pop() else {
55        return small(1);
56    };
57    while let Some(below) = stack.pop() {
58        product = below * product;
59    }
60    // A single number is the product as it is stored.
61    trim(&mut product);
62    product
63}
64
65impl Sum for Number {
66    /// Returns the sum of the numbers, in the byte order of the first and in the shortest form,
67    /// built in the vectors of the numbers; zero, little-endian, for none.
68    ///
69    /// # Examples
70    ///
71    /// ```
72    /// use a::math::numbers::Number;
73    ///
74    /// let sum: Number = (1..=100).map(Number::from).sum();
75    /// assert_eq!(sum, 5050);
76    /// ```
77    fn sum<I: Iterator<Item = Number>>(iter: I) -> Number {
78        sum(iter)
79    }
80}
81
82impl<'a> Sum<&'a Number> for Number {
83    /// Returns the sum of the borrowed numbers, as for owned ones; the first is copied.
84    fn sum<I: Iterator<Item = &'a Number>>(mut iter: I) -> Number {
85        let Some(first) = iter.next() else {
86            return small(0);
87        };
88        let mut sum = Number {
89            value: Vec::new(),
90            negative: false,
91            byte_order: first.byte_order,
92        };
93        sum += first;
94        iter.fold(sum, |sum, x| sum + x)
95    }
96}
97
98impl Product for Number {
99    /// Returns the product of the numbers, in the byte order of the first and in the shortest
100    /// form, multiplied as a balanced tree; one, little-endian, for none.
101    ///
102    /// # Examples
103    ///
104    /// ```
105    /// use a::math::numbers::Number;
106    ///
107    /// let factorial: Number = (1..=25u32).map(Number::from).product();
108    /// assert_eq!(factorial.to_string(), "15511210043330985984000000");
109    /// ```
110    fn product<I: Iterator<Item = Number>>(iter: I) -> Number {
111        product(iter)
112    }
113}
114
115impl<'a> Product<&'a Number> for Number {
116    /// Returns the product of the borrowed numbers, as for owned ones; each is copied once.
117    fn product<I: Iterator<Item = &'a Number>>(iter: I) -> Number {
118        product(iter.cloned())
119    }
120}
a/math/numbers/iter.rs

a/math/numbers/
iter.rs
