Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 1 | // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT |
| 2 | // file at the top-level directory of this distribution and at |
| 3 | // http://rust-lang.org/COPYRIGHT. |
| 4 | // |
| 5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| 6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| 7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your |
| 8 | // option. This file may not be copied, modified, or distributed |
| 9 | // except according to those terms. |
| 10 | |
| 11 | //! A Big integer (signed version: `BigInt`, unsigned version: `BigUint`). |
| 12 | //! |
| 13 | //! A `BigUint` is represented as a vector of `BigDigit`s. |
| 14 | //! A `BigInt` is a combination of `BigUint` and `Sign`. |
| 15 | //! |
| 16 | //! Common numerical operations are overloaded, so we can treat them |
| 17 | //! the same way we treat other numbers. |
| 18 | //! |
| 19 | //! ## Example |
| 20 | //! |
| 21 | //! ```rust |
| 22 | //! # fn main() { |
| 23 | //! use num_bigint::BigUint; |
| 24 | //! use num_traits::{Zero, One}; |
| 25 | //! use std::mem::replace; |
| 26 | //! |
| 27 | //! // Calculate large fibonacci numbers. |
| 28 | //! fn fib(n: usize) -> BigUint { |
| 29 | //! let mut f0: BigUint = Zero::zero(); |
| 30 | //! let mut f1: BigUint = One::one(); |
| 31 | //! for _ in 0..n { |
| 32 | //! let f2 = f0 + &f1; |
| 33 | //! // This is a low cost way of swapping f0 with f1 and f1 with f2. |
| 34 | //! f0 = replace(&mut f1, f2); |
| 35 | //! } |
| 36 | //! f0 |
| 37 | //! } |
| 38 | //! |
| 39 | //! // This is a very large number. |
| 40 | //! println!("fib(1000) = {}", fib(1000)); |
| 41 | //! # } |
| 42 | //! ``` |
| 43 | //! |
| 44 | //! It's easy to generate large random numbers: |
| 45 | //! |
| 46 | //! ```rust,ignore |
| 47 | //! use num_bigint::{ToBigInt, RandBigInt}; |
| 48 | //! |
| 49 | //! let mut rng = rand::thread_rng(); |
| 50 | //! let a = rng.gen_bigint(1000); |
| 51 | //! |
| 52 | //! let low = -10000.to_bigint().unwrap(); |
| 53 | //! let high = 10000.to_bigint().unwrap(); |
| 54 | //! let b = rng.gen_bigint_range(&low, &high); |
| 55 | //! |
| 56 | //! // Probably an even larger number. |
| 57 | //! println!("{}", a * b); |
| 58 | //! ``` |
| 59 | //! |
| 60 | //! See the "Features" section for instructions for enabling random number generation. |
| 61 | //! |
| 62 | //! ## Features |
| 63 | //! |
| 64 | //! The `std` crate feature is enabled by default, and is mandatory before Rust |
| 65 | //! 1.36 and the stabilized `alloc` crate. If you depend on `num-bigint` with |
| 66 | //! `default-features = false`, you must manually enable the `std` feature yourself |
| 67 | //! if your compiler is not new enough. |
| 68 | //! |
| 69 | //! ### Random Generation |
| 70 | //! |
| 71 | //! `num-bigint` supports the generation of random big integers when the `rand` |
| 72 | //! feature is enabled. To enable it include rand as |
| 73 | //! |
| 74 | //! ```toml |
| 75 | //! rand = "0.8" |
| 76 | //! num-bigint = { version = "0.4", features = ["rand"] } |
| 77 | //! ``` |
| 78 | //! |
| 79 | //! Note that you must use the version of `rand` that `num-bigint` is compatible |
| 80 | //! with: `0.8`. |
| 81 | //! |
| 82 | //! |
| 83 | //! ## Compatibility |
| 84 | //! |
| 85 | //! The `num-bigint` crate is tested for rustc 1.31 and greater. |
| 86 | |
| 87 | #![doc(html_root_url = "https://docs.rs/num-bigint/0.4")] |
| 88 | #![warn(rust_2018_idioms)] |
| 89 | #![no_std] |
| 90 | |
| 91 | #[cfg(feature = "std")] |
| 92 | #[macro_use] |
| 93 | extern crate std; |
| 94 | |
| 95 | #[cfg(feature = "std")] |
| 96 | mod std_alloc { |
| 97 | pub(crate) use std::borrow::Cow; |
| 98 | #[cfg(any(feature = "quickcheck"))] |
| 99 | pub(crate) use std::boxed::Box; |
| 100 | pub(crate) use std::string::String; |
| 101 | pub(crate) use std::vec::Vec; |
| 102 | } |
| 103 | |
| 104 | #[cfg(not(feature = "std"))] |
| 105 | #[macro_use] |
| 106 | extern crate alloc; |
| 107 | |
| 108 | #[cfg(not(feature = "std"))] |
| 109 | mod std_alloc { |
| 110 | pub(crate) use alloc::borrow::Cow; |
| 111 | #[cfg(any(feature = "quickcheck"))] |
| 112 | pub(crate) use alloc::boxed::Box; |
| 113 | pub(crate) use alloc::string::String; |
| 114 | pub(crate) use alloc::vec::Vec; |
| 115 | } |
| 116 | |
| 117 | use core::fmt; |
| 118 | #[cfg(feature = "std")] |
| 119 | use std::error::Error; |
| 120 | |
| 121 | #[macro_use] |
| 122 | mod macros; |
| 123 | |
| 124 | mod bigint; |
| 125 | mod biguint; |
| 126 | |
| 127 | #[cfg(feature = "rand")] |
| 128 | mod bigrand; |
| 129 | |
| 130 | #[cfg(target_pointer_width = "32")] |
| 131 | type UsizePromotion = u32; |
| 132 | #[cfg(target_pointer_width = "64")] |
| 133 | type UsizePromotion = u64; |
| 134 | |
| 135 | #[cfg(target_pointer_width = "32")] |
| 136 | type IsizePromotion = i32; |
| 137 | #[cfg(target_pointer_width = "64")] |
| 138 | type IsizePromotion = i64; |
| 139 | |
| 140 | #[derive(Debug, Clone, PartialEq, Eq)] |
| 141 | pub struct ParseBigIntError { |
| 142 | kind: BigIntErrorKind, |
| 143 | } |
| 144 | |
| 145 | #[derive(Debug, Clone, PartialEq, Eq)] |
| 146 | enum BigIntErrorKind { |
| 147 | Empty, |
| 148 | InvalidDigit, |
| 149 | } |
| 150 | |
| 151 | impl ParseBigIntError { |
| 152 | fn __description(&self) -> &str { |
| 153 | use crate::BigIntErrorKind::*; |
| 154 | match self.kind { |
| 155 | Empty => "cannot parse integer from empty string", |
| 156 | InvalidDigit => "invalid digit found in string", |
| 157 | } |
| 158 | } |
| 159 | |
| 160 | fn empty() -> Self { |
| 161 | ParseBigIntError { |
| 162 | kind: BigIntErrorKind::Empty, |
| 163 | } |
| 164 | } |
| 165 | |
| 166 | fn invalid() -> Self { |
| 167 | ParseBigIntError { |
| 168 | kind: BigIntErrorKind::InvalidDigit, |
| 169 | } |
| 170 | } |
| 171 | } |
| 172 | |
| 173 | impl fmt::Display for ParseBigIntError { |
| 174 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 175 | self.__description().fmt(f) |
| 176 | } |
| 177 | } |
| 178 | |
| 179 | #[cfg(feature = "std")] |
| 180 | impl Error for ParseBigIntError { |
| 181 | fn description(&self) -> &str { |
| 182 | self.__description() |
| 183 | } |
| 184 | } |
| 185 | |
| 186 | /// The error type returned when a checked conversion regarding big integer fails. |
| 187 | #[cfg(has_try_from)] |
| 188 | #[derive(Debug, Copy, Clone, PartialEq, Eq)] |
| 189 | pub struct TryFromBigIntError<T> { |
| 190 | original: T, |
| 191 | } |
| 192 | |
| 193 | #[cfg(has_try_from)] |
| 194 | impl<T> TryFromBigIntError<T> { |
| 195 | fn new(original: T) -> Self { |
| 196 | TryFromBigIntError { original } |
| 197 | } |
| 198 | |
| 199 | fn __description(&self) -> &str { |
| 200 | "out of range conversion regarding big integer attempted" |
| 201 | } |
| 202 | |
| 203 | /// Extract the original value, if available. The value will be available |
| 204 | /// if the type before conversion was either [`BigInt`] or [`BigUint`]. |
| 205 | /// |
| 206 | /// [`BigInt`]: struct.BigInt.html |
| 207 | /// [`BigUint`]: struct.BigUint.html |
| 208 | pub fn into_original(self) -> T { |
| 209 | self.original |
| 210 | } |
| 211 | } |
| 212 | |
| 213 | #[cfg(all(feature = "std", has_try_from))] |
| 214 | impl<T> std::error::Error for TryFromBigIntError<T> |
| 215 | where |
| 216 | T: fmt::Debug, |
| 217 | { |
| 218 | fn description(&self) -> &str { |
| 219 | self.__description() |
| 220 | } |
| 221 | } |
| 222 | |
| 223 | #[cfg(has_try_from)] |
| 224 | impl<T> fmt::Display for TryFromBigIntError<T> { |
| 225 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 226 | self.__description().fmt(f) |
| 227 | } |
| 228 | } |
| 229 | |
| 230 | pub use crate::biguint::BigUint; |
| 231 | pub use crate::biguint::ToBigUint; |
| 232 | pub use crate::biguint::U32Digits; |
| 233 | pub use crate::biguint::U64Digits; |
| 234 | |
| 235 | pub use crate::bigint::BigInt; |
| 236 | pub use crate::bigint::Sign; |
| 237 | pub use crate::bigint::ToBigInt; |
| 238 | |
| 239 | #[cfg(feature = "rand")] |
| 240 | pub use crate::bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint}; |
| 241 | |
| 242 | mod big_digit { |
| 243 | /// A `BigDigit` is a `BigUint`'s composing element. |
| 244 | #[cfg(not(u64_digit))] |
| 245 | pub(crate) type BigDigit = u32; |
| 246 | #[cfg(u64_digit)] |
| 247 | pub(crate) type BigDigit = u64; |
| 248 | |
| 249 | /// A `DoubleBigDigit` is the internal type used to do the computations. Its |
| 250 | /// size is the double of the size of `BigDigit`. |
| 251 | #[cfg(not(u64_digit))] |
| 252 | pub(crate) type DoubleBigDigit = u64; |
| 253 | #[cfg(u64_digit)] |
| 254 | pub(crate) type DoubleBigDigit = u128; |
| 255 | |
| 256 | /// A `SignedDoubleBigDigit` is the signed version of `DoubleBigDigit`. |
| 257 | #[cfg(not(u64_digit))] |
| 258 | pub(crate) type SignedDoubleBigDigit = i64; |
| 259 | #[cfg(u64_digit)] |
| 260 | pub(crate) type SignedDoubleBigDigit = i128; |
| 261 | |
| 262 | // `DoubleBigDigit` size dependent |
| 263 | #[cfg(not(u64_digit))] |
| 264 | pub(crate) const BITS: u8 = 32; |
| 265 | #[cfg(u64_digit)] |
| 266 | pub(crate) const BITS: u8 = 64; |
| 267 | |
| 268 | pub(crate) const HALF_BITS: u8 = BITS / 2; |
| 269 | pub(crate) const HALF: BigDigit = (1 << HALF_BITS) - 1; |
| 270 | |
| 271 | const LO_MASK: DoubleBigDigit = (1 << BITS) - 1; |
| 272 | pub(crate) const MAX: BigDigit = LO_MASK as BigDigit; |
| 273 | |
| 274 | #[inline] |
| 275 | fn get_hi(n: DoubleBigDigit) -> BigDigit { |
| 276 | (n >> BITS) as BigDigit |
| 277 | } |
| 278 | #[inline] |
| 279 | fn get_lo(n: DoubleBigDigit) -> BigDigit { |
| 280 | (n & LO_MASK) as BigDigit |
| 281 | } |
| 282 | |
| 283 | /// Split one `DoubleBigDigit` into two `BigDigit`s. |
| 284 | #[inline] |
| 285 | pub(crate) fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) { |
| 286 | (get_hi(n), get_lo(n)) |
| 287 | } |
| 288 | |
| 289 | /// Join two `BigDigit`s into one `DoubleBigDigit` |
| 290 | #[inline] |
| 291 | pub(crate) fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit { |
| 292 | DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS) |
| 293 | } |
| 294 | } |