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//! # 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]
93extern crate std;
94
95#[cfg(feature = "std")]
96mod 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]
106extern crate alloc;
107
108#[cfg(not(feature = "std"))]
109mod 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
117use core::fmt;
118#[cfg(feature = "std")]
119use std::error::Error;
120
121#[macro_use]
122mod macros;
123
124mod bigint;
125mod biguint;
126
127#[cfg(feature = "rand")]
128mod bigrand;
129
130#[cfg(target_pointer_width = "32")]
131type UsizePromotion = u32;
132#[cfg(target_pointer_width = "64")]
133type UsizePromotion = u64;
134
135#[cfg(target_pointer_width = "32")]
136type IsizePromotion = i32;
137#[cfg(target_pointer_width = "64")]
138type IsizePromotion = i64;
139
140#[derive(Debug, Clone, PartialEq, Eq)]
141pub struct ParseBigIntError {
142    kind: BigIntErrorKind,
143}
144
145#[derive(Debug, Clone, PartialEq, Eq)]
146enum BigIntErrorKind {
147    Empty,
148    InvalidDigit,
149}
150
151impl 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
173impl 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")]
180impl 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)]
189pub struct TryFromBigIntError<T> {
190    original: T,
191}
192
193#[cfg(has_try_from)]
194impl<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))]
214impl<T> std::error::Error for TryFromBigIntError<T>
215where
216    T: fmt::Debug,
217{
218    fn description(&self) -> &str {
219        self.__description()
220    }
221}
222
223#[cfg(has_try_from)]
224impl<T> fmt::Display for TryFromBigIntError<T> {
225    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
226        self.__description().fmt(f)
227    }
228}
229
230pub use crate::biguint::BigUint;
231pub use crate::biguint::ToBigUint;
232pub use crate::biguint::U32Digits;
233pub use crate::biguint::U64Digits;
234
235pub use crate::bigint::BigInt;
236pub use crate::bigint::Sign;
237pub use crate::bigint::ToBigInt;
238
239#[cfg(feature = "rand")]
240pub use crate::bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint};
241
242mod 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}
num_bigint/lib.rs

num_bigint/
lib.rs
