nanvm_lib/vm/bigint/
pow.rs

1use crate::{
2    common::sized_index::SizedIndex,
3    sign::Sign,
4    vm::{Any, BigInt, IVm, error},
5};
6
7impl<A: IVm> BigInt<A> {
8    /// `**`. Not a `core::ops` trait — Rust has no operator for
9    /// exponentiation, so this is a plain method, the same as `Any::pow`
10    /// one level up.
11    ///
12    /// Exponentiation by squaring, walking the exponent's own bits rather
13    /// than converting it to a Rust integer, so an exponent wider than
14    /// `u64` still works. A negative exponent throws instead of coercing to
15    /// a fraction, unlike `Number ** Number`, since `BigInt` has none. A
16    /// power longer than `MAX_WORDS` words throws the `RangeError` that `*`
17    /// throws for the multiplication that crosses it.
18    pub fn pow(self, rhs: Self) -> Result<Self, Any<A>> {
19        if rhs.sign() == Sign::Negative {
20            return Err(error::negative_exponent());
21        }
22        let exponent: Vec<u64> = rhs.index_iter().collect();
23        // The word count times 64 overcounts: only bits up to the top word's
24        // own highest set bit are ever meaningful. Squaring `base` beyond
25        // that point would still be correct (the skipped bits are all zero,
26        // so no further multiply ever triggers) but blows `base` up to an
27        // astronomically large, wholly unused magnitude, so the loop stops
28        // there instead.
29        let bit_len = match exponent.last() {
30            None => 0,
31            Some(&top) => (exponent.len() as u32 - 1) * 64 + (64 - top.leading_zeros()),
32        };
33
34        let mut result = Self::from(1u64);
35        let mut base = self;
36        for bit in 0..bit_len {
37            if (exponent[(bit / 64) as usize] >> (bit % 64)) & 1 != 0 {
38                result = (result * base.clone())?;
39            }
40            if bit + 1 < bit_len {
41                base = (base.clone() * base)?;
42            }
43        }
44        Ok(result)
45    }
46}
47
48#[cfg(test)]
49mod tests {
50    use crate::vm::{
51        bigint::test_util::{T, int},
52        error,
53    };
54
55    /// A power past the size limit is the `RangeError` `*` throws, not a
56    /// result grown without bound: `2^(2^20)` has 16385 words.
57    #[test]
58    fn power_past_the_limit() {
59        assert_eq!(int(2).pow(int(1 << 20)), Err(error::bigint_too_large()));
60    }
61
62    #[test]
63    fn zero_exponent_gives_one() {
64        assert_eq!(int(5).pow(int(0)).unwrap(), int(1));
65        assert_eq!(int(0).pow(int(0)).unwrap(), int(1));
66    }
67
68    #[test]
69    fn positive_exponent() {
70        assert_eq!(int(2).pow(int(10)).unwrap(), int(1_024));
71    }
72
73    #[test]
74    fn negative_base_odd_and_even_exponent() {
75        assert_eq!(int(-2).pow(int(3)).unwrap(), int(-8));
76        assert_eq!(int(-2).pow(int(2)).unwrap(), int(4));
77    }
78
79    #[test]
80    fn negative_exponent_throws() {
81        assert!(int(2).pow(int(-1)).is_err());
82    }
83
84    #[test]
85    fn zero_base_positive_exponent() {
86        assert_eq!(int(0).pow(int(5)).unwrap(), T::default());
87    }
88}
nanvm_lib/vm/bigint/pow.rs

nanvm_lib/vm/bigint/
pow.rs
