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 { __description(&self) -> &str152 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 empty() -> Self160 fn empty() -> Self { 161 ParseBigIntError { 162 kind: BigIntErrorKind::Empty, 163 } 164 } 165 invalid() -> Self166 fn invalid() -> Self { 167 ParseBigIntError { 168 kind: BigIntErrorKind::InvalidDigit, 169 } 170 } 171 } 172 173 impl fmt::Display for ParseBigIntError { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result174 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 { description(&self) -> &str181 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> { new(original: T) -> Self195 fn new(original: T) -> Self { 196 TryFromBigIntError { original } 197 } 198 __description(&self) -> &str199 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 into_original(self) -> T208 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 { description(&self) -> &str218 fn description(&self) -> &str { 219 self.__description() 220 } 221 } 222 223 #[cfg(has_try_from)] 224 impl<T> fmt::Display for TryFromBigIntError<T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result225 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] get_hi(n: DoubleBigDigit) -> BigDigit275 fn get_hi(n: DoubleBigDigit) -> BigDigit { 276 (n >> BITS) as BigDigit 277 } 278 #[inline] get_lo(n: DoubleBigDigit) -> BigDigit279 fn get_lo(n: DoubleBigDigit) -> BigDigit { 280 (n & LO_MASK) as BigDigit 281 } 282 283 /// Split one `DoubleBigDigit` into two `BigDigit`s. 284 #[inline] from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit)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] to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit291 pub(crate) fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit { 292 DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS) 293 } 294 } 295