use std::cmp;
use std::fmt;
+pub trait Minimum {
+ /// Return the smaller of the two
+ fn min<'a>(&'a self, other: &'a Self) -> &'a Self;
+}
+
+/// Return a pointer to the minimal value of `v`.
+pub fn vec_min<T: Minimum>(v: &Vec<T>) -> Option<&T> {
+ let mut min = None;
+ for e in v {
+ min = Some(match min {
+ None => e,
+ Some(n) => e.min(n)
+ });
+ }
+ min
+}
+
pub struct BigInt {
data: Vec<u64>, // least significant digits first. The last block will *not* be 0.
}
// Add with carry, returning the sum and the carry
fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
- match u64::checked_add(a, b) {
- Some(sum) if !carry => (sum, false),
- Some(sum) => { // we have to increment the sum by 1, where it may overflow again
- match u64::checked_add(sum, 1) {
- Some(total_sum) => (total_sum, false),
- None => (0, true) // we overflowed incrementing by 1, so we are just "at the edge"
- }
- },
- None => {
- // Get the remainder, i.e., the wrapping sum. This cannot overflow again by adding just 1, so it is safe
- // to add the carry here.
- let rem = u64::wrapping_add(a, b) + if carry { 1 } else { 0 };
- (rem, true)
- }
+ let sum = u64::wrapping_add(a, b);
+ let carry_n = if carry { 1 } else { 0 };
+ if sum >= a { // the first sum did not overflow
+ let sum_total = u64::wrapping_add(sum, carry_n);
+ let had_overflow = sum_total < sum;
+ (sum_total, had_overflow)
+ } else { // the first sum did overflow
+ // it is impossible for this to overflow again, as we are just adding 0 or 1
+ (sum + carry_n, true)
}
}
-
impl BigInt {
/// Construct a BigInt from a "small" one.
pub fn new(x: u64) -> Self {
}
}
- /// Construct a BigInt from a vector of 64-bit "digits", with the last significant digit being first
+ /// Construct a BigInt from a vector of 64-bit "digits", with the last significant digit being first. Solution to 05.1.
pub fn from_vec(mut v: Vec<u64>) -> Self {
- // remove trailing zeroes
+ // remove trailing zeros
while v.len() > 0 && v[v.len()-1] == 0 {
v.pop();
}
BigInt { data: v }
}
- /// Return the smaller of the two numbers
- pub fn min(self, other: Self) -> Self {
- debug_assert!(self.test_invariant() && other.test_invariant());
- if self.data.len() < other.data.len() {
- self
- } else if self.data.len() > other.data.len() {
- other
- } else {
- // compare back-to-front, i.e., most significant digit first
- let mut idx = self.data.len()-1;
- while idx > 0 {
- if self.data[idx] < other.data[idx] {
- return self;
- } else if self.data[idx] > other.data[idx] {
- return other;
- }
- else {
- idx = idx-1;
- }
+ /// Increments the number by 1.
+ pub fn inc1(&mut self) {
+ let mut idx = 0;
+ // This loop adds "(1 << idx)". If there is no more carry, we leave.
+ while idx < self.data.len() {
+ let cur = self.data[idx];
+ let sum = u64::wrapping_add(cur, 1);
+ self.data[idx] = sum;
+ if sum >= cur {
+ // No overflow, we are done.
+ return;
+ } else {
+ // We need to go on.
+ idx += 1;
}
- // the two are equal
- return self;
}
- }
-
- /// Returns a view on the raw digits representing the number.
- ///
- /// ```
- /// use solutions::bigint::BigInt;
- /// let b = BigInt::new(13);
- /// let d = b.data();
- /// assert_eq!(d, [13]);
- /// ```
- pub fn data(&self) -> &[u64] {
- &self.data[..]
+ // If we came here, there is a last carry to add
+ self.data.push(1);
}
/// Increments the number by "by".
}
}
-
impl PartialEq for BigInt {
fn eq(&self, other: &BigInt) -> bool {
debug_assert!(self.test_invariant() && other.test_invariant());
- self.data() == other.data()
+ self.data == other.data
+ }
+}
+
+impl Minimum for BigInt {
+ // This is essentially the solution to 06.1.
+ fn min<'a>(&'a self, other: &'a Self) -> &'a Self {
+ debug_assert!(self.test_invariant() && other.test_invariant());
+ if self.data.len() < other.data.len() {
+ self
+ } else if self.data.len() > other.data.len() {
+ other
+ } else {
+ // compare back-to-front, i.e., most significant digit first
+ let mut idx = self.data.len()-1;
+ while idx > 0 {
+ if self.data[idx] < other.data[idx] {
+ return self;
+ } else if self.data[idx] > other.data[idx] {
+ return other;
+ }
+ else {
+ idx = idx-1;
+ }
+ }
+ // the two are equal
+ return self;
+ }
}
}
impl fmt::Debug for BigInt {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- self.data().fmt(f)
+ self.data.fmt(f)
}
}
impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt {
type Output = BigInt;
fn add(self, rhs: &'a BigInt) -> Self::Output {
- let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data().len(), rhs.data().len()));
+ let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
let mut carry:bool = false; // the carry bit
- for (i, val) in self.data().into_iter().enumerate() {
+ for (i, val) in (&self.data).into_iter().enumerate() {
// compute next digit and carry
- let rhs_val = if i < rhs.data().len() { rhs.data()[i] } else { 0 };
+ let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 };
let (sum, new_carry) = overflowing_add(*val, rhs_val, carry);
// store them
result_vec.push(sum);
carry = new_carry;
}
- BigInt::from_vec(result_vec)
+ if carry {
+ result_vec.push(1);
+ }
+ // We know that the invariant holds: overflowing_add would only return (0, false) if
+ // the arguments are (0, 0, false), but we know that in the last iteration, `val` is the
+ // last digit of `self` and hence not 0.
+ BigInt { data: result_vec }
}
}
#[cfg(test)]
mod tests {
+ use std::u64;
use super::overflowing_add;
use super::BigInt;
assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
}
+ #[test]
+ fn test_inc1() {
+ let mut b = BigInt::new(0);
+ b.inc1();
+ assert_eq!(b, BigInt::new(1));
+ b.inc1();
+ assert_eq!(b, BigInt::new(2));
+
+ b = BigInt::new(u64::MAX);
+ b.inc1();
+ assert_eq!(b, BigInt::from_vec(vec![0, 1]));
+ b.inc1();
+ assert_eq!(b, BigInt::from_vec(vec![1, 1]));
+ }
+
#[test]
fn test_power_of_2() {
assert_eq!(BigInt::power_of_2(0), BigInt::new(1));
projects / rust-101.git / blobdiff