1 // Copyright 2018 Stichting Organism 2 // 3 // Copyright 2018 Friedel Ziegelmayer 4 // 5 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT 6 // file at the top-level directory of this distribution and at 7 // http://rust-lang.org/COPYRIGHT. 8 // 9 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or 10 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license 11 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your 12 // option. This file may not be copied, modified, or distributed 13 // except according to those terms. 14 15 //! A Big integer (signed version: `BigInt`, unsigned version: `BigUint`). 16 //! 17 //! A `BigUint` is represented as a vector of `BigDigit`s. 18 //! A `BigInt` is a combination of `BigUint` and `Sign`. 19 //! 20 //! Common numerical operations are overloaded, so we can treat them 21 //! the same way we treat other numbers. 22 //! 23 //! ## Example 24 //! 25 //! ```rust 26 //! extern crate num_bigint_dig as num_bigint; 27 //! extern crate num_traits; 28 //! 29 //! # fn main() { 30 //! use num_bigint::BigUint; 31 //! use num_traits::{Zero, One}; 32 //! use std::mem::replace; 33 //! 34 //! // Calculate large fibonacci numbers. 35 //! fn fib(n: usize) -> BigUint { 36 //! let mut f0: BigUint = Zero::zero(); 37 //! let mut f1: BigUint = One::one(); 38 //! for _ in 0..n { 39 //! let f2 = f0 + &f1; 40 //! // This is a low cost way of swapping f0 with f1 and f1 with f2. 41 //! f0 = replace(&mut f1, f2); 42 //! } 43 //! f0 44 //! } 45 //! 46 //! // This is a very large number. 47 //! //println!("fib(1000) = {}", fib(1000)); 48 //! # } 49 //! ``` 50 //! 51 //! It's easy to generate large random numbers: 52 //! 53 #![cfg_attr(feature = "std", doc = " ```")] 54 #![cfg_attr(not(feature = "std"), doc = " ```ignore")] 55 //! 56 //! # #[cfg(feature = "rand")] 57 //! extern crate rand; 58 //! extern crate num_bigint_dig as bigint; 59 //! 60 //! # #[cfg(feature = "rand")] 61 //! # fn main() { 62 //! use bigint::{ToBigInt, RandBigInt}; 63 //! 64 //! let mut rng = rand::thread_rng(); 65 //! let a = rng.gen_bigint(1000); 66 //! 67 //! let low = -10000.to_bigint().unwrap(); 68 //! let high = 10000.to_bigint().unwrap(); 69 //! let b = rng.gen_bigint_range(&low, &high); 70 //! 71 //! // Probably an even larger number. 72 //! //println!("{}", a * b); 73 //! # } 74 //! 75 //! # #[cfg(not(feature = "rand"))] 76 //! # fn main() { 77 //! # } 78 //! ``` 79 //! 80 //! ## Compatibility 81 //! 82 //! The `num-bigint` crate is tested for rustc 1.15 and greater. 83 //! 84 //! ## `no_std` compatibility 85 //! 86 //! This crate is compatible with `no_std` environments from Rust 1.36. Note 87 //! however that it still requires the `alloc` crate, so the user should ensure 88 //! that they set a `global_allocator`. 89 //! 90 //! To use in no_std environment, add the crate as such in your `Cargo.toml` 91 //! file: 92 //! 93 //! ```toml 94 //! [dependencies] 95 //! num-bigint = { version = "0.3", default-features=false } 96 //! ``` 97 //! 98 //! Every features should be compatible with no_std environment, so feel free to 99 //! add features like `prime`, `i128`, etc... 100 101 #![doc(html_root_url = "https://docs.rs/num-bigint/0.2")] 102 #![cfg_attr(not(feature = "std"), no_std)] 103 104 #[cfg(not(feature = "std"))] 105 #[macro_use] 106 extern crate alloc; 107 108 #[cfg(feature = "std")] 109 use std as alloc; 110 111 #[cfg(feature = "std")] 112 extern crate core; 113 114 #[cfg(feature = "rand")] 115 extern crate rand; 116 #[cfg(all(test, feature = "rand"))] 117 extern crate rand_chacha; 118 #[cfg(all(test, feature = "rand"))] 119 extern crate rand_isaac; 120 #[cfg(all(test, feature = "rand"))] 121 extern crate rand_xorshift; 122 123 #[cfg(feature = "serde")] 124 extern crate serde; 125 126 #[cfg(feature = "zeroize")] 127 extern crate zeroize; 128 129 #[macro_use] 130 extern crate smallvec; 131 132 #[cfg(feature = "prime")] 133 #[macro_use] 134 extern crate lazy_static; 135 136 extern crate num_integer as integer; 137 extern crate num_iter; 138 extern crate num_traits; 139 140 #[cfg(feature = "prime")] 141 extern crate byteorder; 142 143 extern crate libm; 144 145 #[cfg(feature = "std")] 146 use std::error::Error; 147 use core::fmt; 148 149 #[macro_use] 150 mod macros; 151 152 mod bigint; 153 mod biguint; 154 155 #[cfg(feature = "prime")] 156 pub mod prime; 157 158 pub mod algorithms; 159 pub mod traits; 160 161 pub use traits::*; 162 163 #[cfg(feature = "rand")] 164 mod bigrand; 165 166 #[cfg(target_pointer_width = "32")] 167 type UsizePromotion = u32; 168 #[cfg(target_pointer_width = "64")] 169 type UsizePromotion = u64; 170 171 #[cfg(target_pointer_width = "32")] 172 type IsizePromotion = i32; 173 #[cfg(target_pointer_width = "64")] 174 type IsizePromotion = i64; 175 176 #[derive(Debug, Clone, PartialEq, Eq)] 177 pub struct ParseBigIntError { 178 kind: BigIntErrorKind, 179 } 180 181 #[derive(Debug, Clone, PartialEq, Eq)] 182 enum BigIntErrorKind { 183 Empty, 184 InvalidDigit, 185 } 186 187 impl ParseBigIntError { __description(&self) -> &str188 fn __description(&self) -> &str { 189 use BigIntErrorKind::*; 190 match self.kind { 191 Empty => "cannot parse integer from empty string", 192 InvalidDigit => "invalid digit found in string", 193 } 194 } 195 empty() -> Self196 fn empty() -> Self { 197 ParseBigIntError { 198 kind: BigIntErrorKind::Empty, 199 } 200 } 201 invalid() -> Self202 fn invalid() -> Self { 203 ParseBigIntError { 204 kind: BigIntErrorKind::InvalidDigit, 205 } 206 } 207 } 208 209 impl fmt::Display for ParseBigIntError { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result210 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 211 self.__description().fmt(f) 212 } 213 } 214 215 #[cfg(feature = "std")] 216 impl Error for ParseBigIntError { description(&self) -> &str217 fn description(&self) -> &str { 218 self.__description() 219 } 220 } 221 222 pub use biguint::BigUint; 223 pub use biguint::IntoBigUint; 224 pub use biguint::ToBigUint; 225 226 pub use bigint::negate_sign; 227 pub use bigint::BigInt; 228 pub use bigint::IntoBigInt; 229 pub use bigint::Sign; 230 pub use bigint::ToBigInt; 231 232 #[cfg(feature = "rand")] 233 pub use bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint}; 234 235 #[cfg(feature = "prime")] 236 pub use bigrand::RandPrime; 237 238 #[cfg(not(feature = "u64_digit"))] 239 pub const VEC_SIZE: usize = 8; 240 241 #[cfg(feature = "u64_digit")] 242 pub const VEC_SIZE: usize = 4; 243 244 mod big_digit { 245 /// A `BigDigit` is a `BigUint`'s composing element. 246 #[cfg(not(feature = "u64_digit"))] 247 pub type BigDigit = u32; 248 #[cfg(feature = "u64_digit")] 249 pub type BigDigit = u64; 250 251 /// A `DoubleBigDigit` is the internal type used to do the computations. Its 252 /// size is the double of the size of `BigDigit`. 253 #[cfg(not(feature = "u64_digit"))] 254 pub type DoubleBigDigit = u64; 255 #[cfg(feature = "u64_digit")] 256 pub type DoubleBigDigit = u128; 257 258 /// A `SignedDoubleBigDigit` is the signed version of `DoubleBigDigit`. 259 #[cfg(not(feature = "u64_digit"))] 260 pub type SignedDoubleBigDigit = i64; 261 #[cfg(feature = "u64_digit")] 262 pub type SignedDoubleBigDigit = i128; 263 264 // `DoubleBigDigit` size dependent 265 #[cfg(not(feature = "u64_digit"))] 266 pub const BITS: usize = 32; 267 #[cfg(feature = "u64_digit")] 268 pub const BITS: usize = 64; 269 270 #[cfg(not(feature = "u64_digit"))] 271 const LO_MASK: DoubleBigDigit = (-1i32 as DoubleBigDigit) >> BITS; 272 #[cfg(feature = "u64_digit")] 273 const LO_MASK: DoubleBigDigit = (-1i64 as DoubleBigDigit) >> BITS; 274 275 #[inline] get_hi(n: DoubleBigDigit) -> BigDigit276 fn get_hi(n: DoubleBigDigit) -> BigDigit { 277 (n >> BITS) as BigDigit 278 } 279 #[inline] get_lo(n: DoubleBigDigit) -> BigDigit280 fn get_lo(n: DoubleBigDigit) -> BigDigit { 281 (n & LO_MASK) as BigDigit 282 } 283 284 /// Split one `DoubleBigDigit` into two `BigDigit`s. 285 #[inline] from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit)286 pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) { 287 (get_hi(n), get_lo(n)) 288 } 289 290 /// Join two `BigDigit`s into one `DoubleBigDigit` 291 #[inline] to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit292 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit { 293 (DoubleBigDigit::from(lo)) | ((DoubleBigDigit::from(hi)) << BITS) 294 } 295 } 296