// 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::string::String;
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 {
- self.cmp(other) == Less
+ fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
+ Some(self.cmp(other))
}
}
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 { (*self % *other).is_zero() }
+ fn divides(&self, other: &BigUint) -> bool { return self.is_multiple_of(other); }
- /// Returns `true` if the number is divisible by `2`
+ /// Returns `true` if the number is a multiple of `other`.
+ #[inline]
+ fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
+
+ /// 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 PartialOrd for BigInt {
#[inline]
- fn lt(&self, other: &BigInt) -> bool {
- self.cmp(other) == Less
+ fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
+ Some(self.cmp(other))
}
}
}
}
- /**
- * 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() }
}
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