// option. This file may not be copied, modified, or distributed
// except according to those terms.
-/*!
-
-A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
-
-A `BigUint` is represented as an array of `BigDigit`s.
-A `BigInt` is a combination of `BigUint` and `Sign`.
-*/
+//! A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
+//!
+//! A `BigUint` is represented as an array of `BigDigit`s.
+//! A `BigInt` is a combination of `BigUint` and `Sign`.
+//!
+//! Common numerical operations are overloaded, so we can treat them
+//! the same way we treat other numbers.
+//!
+//! ## Example
+//!
+//! ```rust
+//! use num::bigint::BigUint;
+//! use std::num::{Zero, One};
+//! use std::mem::replace;
+//!
+//! // Calculate large fibonacci numbers.
+//! fn fib(n: uint) -> BigUint {
+//! let mut f0: BigUint = Zero::zero();
+//! let mut f1: BigUint = One::one();
+//! for _ in range(0, n) {
+//! let f2 = f0 + f1;
+//! // This is a low cost way of swapping f0 with f1 and f1 with f2.
+//! f0 = replace(&mut f1, f2);
+//! }
+//! f0
+//! }
+//!
+//! // This is a very large number.
+//! println!("fib(1000) = {}", fib(1000));
+//! ```
+//!
+//! It's easy to generate large random numbers:
+//!
+//! ```rust
+//! use num::bigint::{ToBigInt, RandBigInt};
+//! use std::rand;
+//!
+//! let mut rng = rand::task_rng();
+//! let a = rng.gen_bigint(1000u);
+//!
+//! let low = -10000i.to_bigint().unwrap();
+//! let high = 10000i.to_bigint().unwrap();
+//! let b = rng.gen_bigint_range(&low, &high);
+//!
+//! // Probably an even larger number.
+//! println!("{}", a * b);
+//! ```
use Integer;
+use rand::Rng;
-use std::cmp;
+use std::{cmp, fmt};
use std::default::Default;
-use std::fmt;
use std::from_str::FromStr;
use std::num::CheckedDiv;
-use std::num::{Bitwise, ToPrimitive, FromPrimitive};
+use std::num::{ToPrimitive, FromPrimitive};
use std::num::{Zero, One, ToStrRadix, FromStrRadix};
-use rand::Rng;
use std::string::String;
-use std::uint;
-use std::{i64, u64};
+use std::{uint, i64, u64};
-/**
-A `BigDigit` is a `BigUint`'s composing element.
-*/
+/// A `BigDigit` is a `BigUint`'s composing element.
pub type BigDigit = u32;
-/**
-A `DoubleBigDigit` is the internal type used to do the computations. Its
-size is the double of the size of `BigDigit`.
-*/
+/// A `DoubleBigDigit` is the internal type used to do the computations. Its
+/// size is the double of the size of `BigDigit`.
pub type DoubleBigDigit = u64;
pub static ZERO_BIG_DIGIT: BigDigit = 0;
}
}
-/**
-A big unsigned integer type.
-
-A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
-`(a + b * BigDigit::base + c * BigDigit::base^2)`.
-*/
+/// A big unsigned integer type.
+///
+/// A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
+/// `(a + b * BigDigit::base + c * BigDigit::base^2)`.
#[deriving(Clone)]
pub struct BigUint {
data: Vec<BigDigit>
impl PartialOrd for BigUint {
#[inline]
- fn lt(&self, other: &BigUint) -> bool {
- match self.cmp(other) { Less => true, _ => false}
+ fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
+ Some(self.cmp(other))
}
}
impl Default for BigUint {
#[inline]
- fn default() -> BigUint { BigUint::new(Vec::new()) }
+ fn default() -> BigUint { Zero::zero() }
}
impl fmt::Show for BigUint {
let zeros = ZERO_VEC.iter().cycle();
let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
- let mut borrow = 0;
+ let mut borrow = 0i;
let diff: Vec<BigDigit> = a.take(new_len).zip(b).map(|(ai, bi)| {
let (hi, lo) = BigDigit::from_doublebigdigit(
BigDigit::base
}
}
- /**
- * Calculates the Greatest Common Divisor (GCD) of the number and `other`
- *
- * The result is always positive
- */
+ /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
+ ///
+ /// The result is always positive.
#[inline]
fn gcd(&self, other: &BigUint) -> BigUint {
// Use Euclid's algorithm
return n;
}
- /**
- * Calculates the Lowest Common Multiple (LCM) of the number and `other`
- */
+ /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
#[inline]
fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
- /// Returns `true` if the number can be divided by `other` without leaving a remainder
+ /// Deprecated, use `is_multiple_of` instead.
+ #[deprecated = "function renamed to `is_multiple_of`"]
+ #[inline]
+ fn divides(&self, other: &BigUint) -> bool { return self.is_multiple_of(other); }
+
+ /// Returns `true` if the number is a multiple of `other`.
#[inline]
- fn divides(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
+ fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
- /// Returns `true` if the number is divisible by `2`
+ /// Returns `true` if the number is divisible by `2`.
#[inline]
fn is_even(&self) -> bool {
// Considering only the last digit.
}
}
- /// Returns `true` if the number is not divisible by `2`
+ /// Returns `true` if the number is not divisible by `2`.
#[inline]
fn is_odd(&self) -> bool { !self.is_even() }
}
impl ToStrRadix for BigUint {
fn to_str_radix(&self, radix: uint) -> String {
- assert!(1 < radix && radix <= 16);
+ assert!(1 < radix && radix <= 16, "The radix must be within (1, 16]");
let (base, max_len) = get_radix_base(radix);
if base == BigDigit::base {
return fill_concat(self.data.as_slice(), radix, max_len)
impl FromStrRadix for BigUint {
/// Creates and initializes a `BigUint`.
#[inline]
- fn from_str_radix(s: &str, radix: uint)
- -> Option<BigUint> {
+ fn from_str_radix(s: &str, radix: uint) -> Option<BigUint> {
BigUint::parse_bytes(s.as_bytes(), radix)
}
}
///
/// The digits are be in base 2^32.
#[inline]
- pub fn new(v: Vec<BigDigit>) -> BigUint {
+ pub fn new(mut digits: Vec<BigDigit>) -> BigUint {
// omit trailing zeros
- let new_len = v.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
-
- if new_len == v.len() { return BigUint { data: v }; }
- let mut v = v;
- v.truncate(new_len);
- return BigUint { data: v };
+ let new_len = digits.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
+ digits.truncate(new_len);
+ BigUint { data: digits }
}
/// Creates and initializes a `BigUint`.
/// The digits are be in base 2^32.
#[inline]
pub fn from_slice(slice: &[BigDigit]) -> BigUint {
- return BigUint::new(Vec::from_slice(slice));
+ BigUint::new(Vec::from_slice(slice))
}
/// Creates and initializes a `BigUint`.
// `DoubleBigDigit` size dependent
#[inline]
fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
- assert!(1 < radix && radix <= 16);
match radix {
2 => (4294967296, 32),
3 => (3486784401, 20),
14 => (1475789056, 8),
15 => (2562890625, 8),
16 => (4294967296, 8),
- _ => fail!()
+ _ => fail!("The radix must be within (1, 16]")
}
}
impl PartialEq for BigInt {
#[inline]
fn eq(&self, other: &BigInt) -> bool {
- match self.cmp(other) { Equal => true, _ => false }
+ self.cmp(other) == Equal
}
}
impl PartialOrd for BigInt {
#[inline]
- fn lt(&self, other: &BigInt) -> bool {
- match self.cmp(other) { Less => true, _ => false}
+ fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
+ Some(self.cmp(other))
}
}
impl Default for BigInt {
#[inline]
- fn default() -> BigInt { BigInt::new(Zero, Vec::new()) }
+ fn default() -> BigInt { Zero::zero() }
}
impl fmt::Show for BigInt {
match (self.sign, other.sign) {
(Zero, _) => other.clone(),
(_, Zero) => self.clone(),
- (Plus, Plus) => BigInt::from_biguint(Plus,
- self.data + other.data),
+ (Plus, Plus) => BigInt::from_biguint(Plus, self.data + other.data),
(Plus, Minus) => self - (-*other),
(Minus, Plus) => other - (-*self),
(Minus, Minus) => -((-self) + (-*other))
#[inline]
fn div(&self, other: &BigInt) -> BigInt {
let (q, _) = self.div_rem(other);
- return q;
+ q
}
}
#[inline]
fn rem(&self, other: &BigInt) -> BigInt {
let (_, r) = self.div_rem(other);
- return r;
+ r
}
}
#[inline]
fn div_floor(&self, other: &BigInt) -> BigInt {
let (d, _) = self.div_mod_floor(other);
- return d;
+ d
}
#[inline]
fn mod_floor(&self, other: &BigInt) -> BigInt {
let (_, m) = self.div_mod_floor(other);
- return m;
+ m
}
fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
}
}
- /**
- * Calculates the Greatest Common Divisor (GCD) of the number and `other`
- *
- * The result is always positive
- */
+ /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
+ ///
+ /// The result is always positive.
#[inline]
fn gcd(&self, other: &BigInt) -> BigInt {
BigInt::from_biguint(Plus, self.data.gcd(&other.data))
}
- /**
- * Calculates the Lowest Common Multiple (LCM) of the number and `other`
- */
+ /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
#[inline]
fn lcm(&self, other: &BigInt) -> BigInt {
BigInt::from_biguint(Plus, self.data.lcm(&other.data))
}
- /// Returns `true` if the number can be divided by `other` without leaving a remainder
+ /// Deprecated, use `is_multiple_of` instead.
+ #[deprecated = "function renamed to `is_multiple_of`"]
+ #[inline]
+ fn divides(&self, other: &BigInt) -> bool { return self.is_multiple_of(other); }
+
+ /// Returns `true` if the number is a multiple of `other`.
#[inline]
- fn divides(&self, other: &BigInt) -> bool { self.data.divides(&other.data) }
+ fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
- /// Returns `true` if the number is divisible by `2`
+ /// Returns `true` if the number is divisible by `2`.
#[inline]
fn is_even(&self) -> bool { self.data.is_even() }
- /// Returns `true` if the number is not divisible by `2`
+ /// Returns `true` if the number is not divisible by `2`.
#[inline]
fn is_odd(&self) -> bool { self.data.is_odd() }
}
let final_digit: BigDigit = self.gen();
data.push(final_digit >> (BigDigit::bits - rem));
}
- return BigUint::new(data);
+ BigUint::new(data)
}
fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
} else {
Minus
};
- return BigInt::from_biguint(sign, biguint);
+ BigInt::from_biguint(sign, biguint)
}
fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
///
/// The digits are be in base 2^32.
#[inline]
- pub fn new(sign: Sign, v: Vec<BigDigit>) -> BigInt {
- BigInt::from_biguint(sign, BigUint::new(v))
+ pub fn new(sign: Sign, digits: Vec<BigDigit>) -> BigInt {
+ BigInt::from_biguint(sign, BigUint::new(digits))
}
/// Creates and initializes a `BigInt`.
if sign == Zero || data.is_zero() {
return BigInt { sign: Zero, data: Zero::zero() };
}
- return BigInt { sign: sign, data: data };
+ BigInt { sign: sign, data: data }
}
/// Creates and initializes a `BigInt`.
}
/// Creates and initializes a `BigInt`.
- pub fn parse_bytes(buf: &[u8], radix: uint)
- -> Option<BigInt> {
+ pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigInt> {
if buf.is_empty() { return None; }
let mut sign = Plus;
let mut start = 0;
fn test_rand_range() {
let mut rng = task_rng();
- for _ in range(0, 10) {
+ for _ in range(0u, 10) {
assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
&FromPrimitive::from_uint(237).unwrap()),
FromPrimitive::from_uint(236).unwrap());
let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
- for _ in range(0, 1000) {
+ for _ in range(0u, 1000) {
let n: BigUint = rng.gen_biguint_below(&u);
assert!(n < u);
// attempt to allocate a vector of size (-1u) == huge.
let x: BigInt =
from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
- let _y = x.to_str();
+ let _y = x.to_string();
}
#[test]
fn test_rand_range() {
let mut rng = task_rng();
- for _ in range(0, 10) {
+ for _ in range(0u, 10) {
assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
&FromPrimitive::from_uint(237).unwrap()),
FromPrimitive::from_uint(236).unwrap());
fn check(l: BigInt, u: BigInt) {
let mut rng = task_rng();
- for _ in range(0, 1000) {
+ for _ in range(0u, 1000) {
let n: BigInt = rng.gen_bigint_range(&l, &u);
assert!(n >= l);
assert!(n < u);
}
#[bench]
- fn to_str(b: &mut Bencher) {
+ fn to_string(b: &mut Bencher) {
let fac = factorial(100);
let fib = fib(100);
b.iter(|| {
- fac.to_str();
+ fac.to_string();
});
b.iter(|| {
- fib.to_str();
+ fib.to_string();
});
}
let n = { let one : BigUint = One::one(); one << 1000 };
b.iter(|| {
let mut m = n.clone();
- for _ in range(0, 10) {
+ for _ in range(0u, 10) {
m = m >> 1;
}
})
projects / rust.git / blobdiff