num_bigint/
lib.rs

Help
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//! Big Integer Types for Rust
12//!
13//! * A [`BigUint`] is unsigned and represented as a vector of digits.
14//! * A [`BigInt`] is signed and 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::One;
25//!
26//! // Calculate large fibonacci numbers.
27//! fn fib(n: usize) -> BigUint {
28//!     let mut f0 = BigUint::ZERO;
29//!     let mut f1 = BigUint::one();
30//!     for _ in 0..n {
31//!         let f2 = f0 + &f1;
32//!         f0 = f1;
33//!         f1 = f2;
34//!     }
35//!     f0
36//! }
37//!
38//! // This is a very large number.
39//! println!("fib(1000) = {}", fib(1000));
40//! # }
41//! ```
42//!
43//! It's easy to generate large random numbers:
44//!
45//! ```rust,ignore
46//! use num_bigint::{ToBigInt, RandBigInt};
47//!
48//! let mut rng = rand::thread_rng();
49//! let a = rng.gen_bigint(1000);
50//!
51//! let low = -10000.to_bigint().unwrap();
52//! let high = 10000.to_bigint().unwrap();
53//! let b = rng.gen_bigint_range(&low, &high);
54//!
55//! // Probably an even larger number.
56//! println!("{}", a * b);
57//! ```
58//!
59//! See the "Features" section for instructions for enabling random number generation.
60//!
61//! ## Features
62//!
63//! The `std` crate feature is enabled by default, which enables [`std::error::Error`]
64//! implementations and some internal use of floating point approximations. This can be disabled by
65//! depending on `num-bigint` with `default-features = false`. Either way, the `alloc` crate is
66//! always required for heap allocation of the `BigInt`/`BigUint` digits.
67//!
68//! ### Random Generation
69//!
70//! `num-bigint` supports the generation of random big integers when the `rand`
71//! feature is enabled. To enable it include rand as
72//!
73//! ```toml
74//! rand = "0.8"
75//! num-bigint = { version = "0.4", features = ["rand"] }
76//! ```
77//!
78//! Note that you must use the version of `rand` that `num-bigint` is compatible
79//! with: `0.8`.
80//!
81//! ### Arbitrary Big Integers
82//!
83//! `num-bigint` supports `arbitrary` and `quickcheck` features to implement
84//! [`arbitrary::Arbitrary`] and [`quickcheck::Arbitrary`], respectively, for both `BigInt` and
85//! `BigUint`. These are useful for fuzzing and other forms of randomized testing.
86//!
87//! ### Serialization
88//!
89//! The `serde` feature adds implementations of [`Serialize`][serde::Serialize] and
90//! [`Deserialize`][serde::Deserialize] for both `BigInt` and `BigUint`. Their serialized data is
91//! generated portably, regardless of platform differences like the internal digit size.
92//!
93//!
94//! ## Compatibility
95//!
96//! The `num-bigint` crate is tested for rustc 1.60 and greater.
97
98#![cfg_attr(docsrs, feature(doc_cfg))]
99#![doc(html_root_url = "https://docs.rs/num-bigint/0.4")]
100#![warn(rust_2018_idioms)]
101#![no_std]
102
103#[macro_use]
104extern crate alloc;
105
106#[cfg(feature = "std")]
107extern crate std;
108
109use core::fmt;
110
111#[macro_use]
112mod macros;
113
114mod bigint;
115mod bigrand;
116mod biguint;
117
118#[cfg(target_pointer_width = "32")]
119type UsizePromotion = u32;
120#[cfg(target_pointer_width = "64")]
121type UsizePromotion = u64;
122
123#[cfg(target_pointer_width = "32")]
124type IsizePromotion = i32;
125#[cfg(target_pointer_width = "64")]
126type IsizePromotion = i64;
127
128#[derive(Debug, Clone, PartialEq, Eq)]
129pub struct ParseBigIntError {
130    kind: BigIntErrorKind,
131}
132
133#[derive(Debug, Clone, PartialEq, Eq)]
134enum BigIntErrorKind {
135    Empty,
136    InvalidDigit,
137}
138
139impl ParseBigIntError {
140    fn __description(&self) -> &str {
141        use crate::BigIntErrorKind::*;
142        match self.kind {
143            Empty => "cannot parse integer from empty string",
144            InvalidDigit => "invalid digit found in string",
145        }
146    }
147
148    fn empty() -> Self {
149        ParseBigIntError {
150            kind: BigIntErrorKind::Empty,
151        }
152    }
153
154    fn invalid() -> Self {
155        ParseBigIntError {
156            kind: BigIntErrorKind::InvalidDigit,
157        }
158    }
159}
160
161impl fmt::Display for ParseBigIntError {
162    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
163        self.__description().fmt(f)
164    }
165}
166
167#[cfg(feature = "std")]
168#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
169impl std::error::Error for ParseBigIntError {
170    fn description(&self) -> &str {
171        self.__description()
172    }
173}
174
175/// The error type returned when a checked conversion regarding big integer fails.
176#[derive(Debug, Copy, Clone, PartialEq, Eq)]
177pub struct TryFromBigIntError<T> {
178    original: T,
179}
180
181impl<T> TryFromBigIntError<T> {
182    fn new(original: T) -> Self {
183        TryFromBigIntError { original }
184    }
185
186    fn __description(&self) -> &str {
187        "out of range conversion regarding big integer attempted"
188    }
189
190    /// Extract the original value, if available. The value will be available
191    /// if the type before conversion was either [`BigInt`] or [`BigUint`].
192    pub fn into_original(self) -> T {
193        self.original
194    }
195}
196
197#[cfg(feature = "std")]
198#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
199impl<T> std::error::Error for TryFromBigIntError<T>
200where
201    T: fmt::Debug,
202{
203    fn description(&self) -> &str {
204        self.__description()
205    }
206}
207
208impl<T> fmt::Display for TryFromBigIntError<T> {
209    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
210        self.__description().fmt(f)
211    }
212}
213
214pub use crate::biguint::BigUint;
215pub use crate::biguint::ToBigUint;
216pub use crate::biguint::U32Digits;
217pub use crate::biguint::U64Digits;
218
219pub use crate::bigint::BigInt;
220pub use crate::bigint::Sign;
221pub use crate::bigint::ToBigInt;
222
223#[cfg(feature = "rand")]
224#[cfg_attr(docsrs, doc(cfg(feature = "rand")))]
225pub use crate::bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint};
226
227mod big_digit {
228    // A [`BigDigit`] is a [`BigUint`]'s composing element.
229    cfg_digit!(
230        pub(crate) type BigDigit = u32;
231        pub(crate) type BigDigit = u64;
232    );
233
234    // A [`DoubleBigDigit`] is the internal type used to do the computations.  Its
235    // size is the double of the size of [`BigDigit`].
236    cfg_digit!(
237        pub(crate) type DoubleBigDigit = u64;
238        pub(crate) type DoubleBigDigit = u128;
239    );
240
241    pub(crate) const BITS: u8 = BigDigit::BITS as u8;
242    pub(crate) const HALF_BITS: u8 = BITS / 2;
243    pub(crate) const HALF: BigDigit = (1 << HALF_BITS) - 1;
244
245    pub(crate) const MAX: BigDigit = BigDigit::MAX;
246    const LO_MASK: DoubleBigDigit = MAX as DoubleBigDigit;
247
248    #[inline]
249    fn get_hi(n: DoubleBigDigit) -> BigDigit {
250        (n >> BITS) as BigDigit
251    }
252    #[inline]
253    fn get_lo(n: DoubleBigDigit) -> BigDigit {
254        (n & LO_MASK) as BigDigit
255    }
256
257    /// Split one [`DoubleBigDigit`] into two [`BigDigit`]s.
258    #[inline]
259    pub(crate) fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
260        (get_hi(n), get_lo(n))
261    }
262
263    /// Join two [`BigDigit`]s into one [`DoubleBigDigit`].
264    #[inline]
265    pub(crate) fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
266        DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS)
267    }
268}
num_bigint/lib.rs

num_bigint/
lib.rs
