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}
269