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 //! extern crate num_bigint; 23 //! extern crate num_traits; 24 //! 25 //! # fn main() { 26 //! use num_bigint::BigUint; 27 //! use num_traits::{Zero, One}; 28 //! use std::mem::replace; 29 //! 30 //! // Calculate large fibonacci numbers. 31 //! fn fib(n: usize) -> BigUint { 32 //! let mut f0: BigUint = Zero::zero(); 33 //! let mut f1: BigUint = One::one(); 34 //! for _ in 0..n { 35 //! let f2 = f0 + &f1; 36 //! // This is a low cost way of swapping f0 with f1 and f1 with f2. 37 //! f0 = replace(&mut f1, f2); 38 //! } 39 //! f0 40 //! } 41 //! 42 //! // This is a very large number. 43 //! println!("fib(1000) = {}", fib(1000)); 44 //! # } 45 //! ``` 46 //! 47 //! It's easy to generate large random numbers: 48 //! 49 //! ```rust 50 //! # #[cfg(feature = "rand")] 51 //! extern crate rand; 52 //! extern crate num_bigint as bigint; 53 //! 54 //! # #[cfg(feature = "rand")] 55 //! # fn main() { 56 //! use bigint::{ToBigInt, RandBigInt}; 57 //! 58 //! let mut rng = rand::thread_rng(); 59 //! let a = rng.gen_bigint(1000); 60 //! 61 //! let low = -10000.to_bigint().unwrap(); 62 //! let high = 10000.to_bigint().unwrap(); 63 //! let b = rng.gen_bigint_range(&low, &high); 64 //! 65 //! // Probably an even larger number. 66 //! println!("{}", a * b); 67 //! # } 68 //! 69 //! # #[cfg(not(feature = "rand"))] 70 //! # fn main() { 71 //! # } 72 //! ``` 73 //! 74 //! See the "Features" section for instructions for enabling random number generation. 75 //! 76 //! ## Features 77 //! 78 //! The `std` crate feature is mandatory and enabled by default. If you depend on 79 //! `num-bigint` with `default-features = false`, you must manually enable the 80 //! `std` feature yourself. In the future, we hope to support `#![no_std]` with 81 //! the `alloc` crate when `std` is not enabled. 82 //! 83 //! Implementations for `i128` and `u128` are only available with Rust 1.26 and 84 //! later. The build script automatically detects this, but you can make it 85 //! mandatory by enabling the `i128` crate feature. 86 //! 87 //! ### Random Generation 88 //! 89 //! `num-bigint` supports the generation of random big integers when the `rand` 90 //! feature is enabled. To enable it include rand as 91 //! 92 //! ```toml 93 //! rand = "0.5" 94 //! num-bigint = { version = "0.2", features = ["rand"] } 95 //! ``` 96 //! 97 //! Note that you must use the version of `rand` that `num-bigint` is compatible 98 //! with: `0.5`. 99 //! 100 //! 101 //! ## Compatibility 102 //! 103 //! The `num-bigint` crate is tested for rustc 1.15 and greater. 104 105 #![doc(html_root_url = "https://docs.rs/num-bigint/0.2")] 106 // We don't actually support `no_std` yet, and probably won't until `alloc` is stable. We're just 107 // reserving this ability with the "std" feature now, and compilation will fail without. 108 #![cfg_attr(not(feature = "std"), no_std)] 109 110 #[cfg(feature = "rand")] 111 extern crate rand; 112 #[cfg(feature = "serde")] 113 extern crate serde; 114 115 extern crate num_integer as integer; 116 extern crate num_traits as traits; 117 #[cfg(feature = "quickcheck")] 118 extern crate quickcheck; 119 120 use std::error::Error; 121 use std::fmt; 122 123 #[macro_use] 124 mod macros; 125 126 mod bigint; 127 mod biguint; 128 129 #[cfg(feature = "rand")] 130 mod bigrand; 131 132 #[cfg(target_pointer_width = "32")] 133 type UsizePromotion = u32; 134 #[cfg(target_pointer_width = "64")] 135 type UsizePromotion = u64; 136 137 #[cfg(target_pointer_width = "32")] 138 type IsizePromotion = i32; 139 #[cfg(target_pointer_width = "64")] 140 type IsizePromotion = i64; 141 142 #[derive(Debug, Clone, PartialEq, Eq)] 143 pub struct ParseBigIntError { 144 kind: BigIntErrorKind, 145 } 146 147 #[derive(Debug, Clone, PartialEq, Eq)] 148 enum BigIntErrorKind { 149 Empty, 150 InvalidDigit, 151 } 152 153 impl ParseBigIntError { __description(&self) -> &str154 fn __description(&self) -> &str { 155 use BigIntErrorKind::*; 156 match self.kind { 157 Empty => "cannot parse integer from empty string", 158 InvalidDigit => "invalid digit found in string", 159 } 160 } 161 empty() -> Self162 fn empty() -> Self { 163 ParseBigIntError { 164 kind: BigIntErrorKind::Empty, 165 } 166 } 167 invalid() -> Self168 fn invalid() -> Self { 169 ParseBigIntError { 170 kind: BigIntErrorKind::InvalidDigit, 171 } 172 } 173 } 174 175 impl fmt::Display for ParseBigIntError { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result176 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 177 self.__description().fmt(f) 178 } 179 } 180 181 impl Error for ParseBigIntError { description(&self) -> &str182 fn description(&self) -> &str { 183 self.__description() 184 } 185 } 186 187 pub use biguint::BigUint; 188 pub use biguint::ToBigUint; 189 190 pub use bigint::BigInt; 191 pub use bigint::Sign; 192 pub use bigint::ToBigInt; 193 194 #[cfg(feature = "rand")] 195 pub use bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint}; 196 197 mod big_digit { 198 /// A `BigDigit` is a `BigUint`'s composing element. 199 pub type BigDigit = u32; 200 201 /// A `DoubleBigDigit` is the internal type used to do the computations. Its 202 /// size is the double of the size of `BigDigit`. 203 pub type DoubleBigDigit = u64; 204 205 /// A `SignedDoubleBigDigit` is the signed version of `DoubleBigDigit`. 206 pub type SignedDoubleBigDigit = i64; 207 208 // `DoubleBigDigit` size dependent 209 pub const BITS: usize = 32; 210 211 const LO_MASK: DoubleBigDigit = (-1i32 as DoubleBigDigit) >> BITS; 212 213 #[inline] get_hi(n: DoubleBigDigit) -> BigDigit214 fn get_hi(n: DoubleBigDigit) -> BigDigit { 215 (n >> BITS) as BigDigit 216 } 217 #[inline] get_lo(n: DoubleBigDigit) -> BigDigit218 fn get_lo(n: DoubleBigDigit) -> BigDigit { 219 (n & LO_MASK) as BigDigit 220 } 221 222 /// Split one `DoubleBigDigit` into two `BigDigit`s. 223 #[inline] from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit)224 pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) { 225 (get_hi(n), get_lo(n)) 226 } 227 228 /// Join two `BigDigit`s into one `DoubleBigDigit` 229 #[inline] to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit230 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit { 231 DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS) 232 } 233 } 234