num_bigint/lib.rs
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")]
111extern crate rand;
112#[cfg(feature = "serde")]
113extern crate serde;
114
115extern crate num_integer as integer;
116extern crate num_traits as traits;
117#[cfg(feature = "quickcheck")]
118extern crate quickcheck;
119
120use std::error::Error;
121use std::fmt;
122
123#[macro_use]
124mod macros;
125
126mod bigint;
127mod biguint;
128
129#[cfg(feature = "rand")]
130mod bigrand;
131
132#[cfg(target_pointer_width = "32")]
133type UsizePromotion = u32;
134#[cfg(target_pointer_width = "64")]
135type UsizePromotion = u64;
136
137#[cfg(target_pointer_width = "32")]
138type IsizePromotion = i32;
139#[cfg(target_pointer_width = "64")]
140type IsizePromotion = i64;
141
142#[derive(Debug, Clone, PartialEq, Eq)]
143pub struct ParseBigIntError {
144 kind: BigIntErrorKind,
145}
146
147#[derive(Debug, Clone, PartialEq, Eq)]
148enum BigIntErrorKind {
149 Empty,
150 InvalidDigit,
151}
152
153impl ParseBigIntError {
154 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
162 fn empty() -> Self {
163 ParseBigIntError {
164 kind: BigIntErrorKind::Empty,
165 }
166 }
167
168 fn invalid() -> Self {
169 ParseBigIntError {
170 kind: BigIntErrorKind::InvalidDigit,
171 }
172 }
173}
174
175impl fmt::Display for ParseBigIntError {
176 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
177 self.__description().fmt(f)
178 }
179}
180
181impl Error for ParseBigIntError {
182 fn description(&self) -> &str {
183 self.__description()
184 }
185}
186
187pub use biguint::BigUint;
188pub use biguint::ToBigUint;
189
190pub use bigint::BigInt;
191pub use bigint::Sign;
192pub use bigint::ToBigInt;
193
194#[cfg(feature = "rand")]
195pub use bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint};
196
197mod 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]
214 fn get_hi(n: DoubleBigDigit) -> BigDigit {
215 (n >> BITS) as BigDigit
216 }
217 #[inline]
218 fn get_lo(n: DoubleBigDigit) -> BigDigit {
219 (n & LO_MASK) as BigDigit
220 }
221
222 /// Split one `DoubleBigDigit` into two `BigDigit`s.
223 #[inline]
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]
230 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
231 DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS)
232 }
233}