| 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] |
| 104 |
extern crate alloc; |
| 105 |
|
| 106 |
#[cfg(feature = "std")] |
| 107 |
extern crate std; |
| 108 |
|
| 109 |
use core::fmt; |
| 110 |
|
| 111 |
#[macro_use] |
| 112 |
mod macros; |
| 113 |
|
| 114 |
mod bigint; |
| 115 |
mod bigrand; |
| 116 |
mod biguint; |
| 117 |
|
| 118 |
#[cfg(target_pointer_width = "32")] |
| 119 |
type UsizePromotion = u32; |
| 120 |
#[cfg(target_pointer_width = "64")] |
| 121 |
type UsizePromotion = u64; |
| 122 |
|
| 123 |
#[cfg(target_pointer_width = "32")] |
| 124 |
type IsizePromotion = i32; |
| 125 |
#[cfg(target_pointer_width = "64")] |
| 126 |
type IsizePromotion = i64; |
| 127 |
|
| 128 |
#[derive(Debug, Clone, PartialEq, Eq)] |
| 129 |
pub struct ParseBigIntError { |
| 130 |
kind: BigIntErrorKind, |
| 131 |
} |
| 132 |
|
| 133 |
#[derive(Debug, Clone, PartialEq, Eq)] |
| 134 |
enum BigIntErrorKind { |
| 135 |
Empty, |
| 136 |
InvalidDigit, |
| 137 |
} |
| 138 |
|
| 139 |
impl 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 |
|
| 161 |
impl 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")))] |
| 169 |
impl 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)] |
| 177 |
pub struct TryFromBigIntError<T> { |
| 178 |
original: T, |
| 179 |
} |
| 180 |
|
| 181 |
impl<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")))] |
| 199 |
impl<T> std::error::Error for TryFromBigIntError<T> |
| 200 |
where |
| 201 |
T: fmt::Debug, |
| 202 |
{ |
| 203 |
fn description(&self) -> &str { |
| 204 |
self.__description() |
| 205 |
} |
| 206 |
} |
| 207 |
|
| 208 |
impl<T> fmt::Display for TryFromBigIntError<T> { |
| 209 |
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 210 |
self.__description().fmt(f) |
| 211 |
} |
| 212 |
} |
| 213 |
|
| 214 |
pub use crate::biguint::BigUint; |
| 215 |
pub use crate::biguint::ToBigUint; |
| 216 |
pub use crate::biguint::U32Digits; |
| 217 |
pub use crate::biguint::U64Digits; |
| 218 |
|
| 219 |
pub use crate::bigint::BigInt; |
| 220 |
pub use crate::bigint::Sign; |
| 221 |
pub use crate::bigint::ToBigInt; |
| 222 |
|
| 223 |
#[cfg(feature = "rand")] |
| 224 |
#[cfg_attr(docsrs, doc(cfg(feature = "rand")))] |
| 225 |
pub use crate::bigrand::{RandBigInt, RandomBits, UniformBigInt, UniformBigUint}; |
| 226 |
|
| 227 |
mod 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 |
} |