From 3b6f45e080b0d90f65a74f6c9534545d726a9432 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Mon, 6 Jul 2015 17:00:56 +0200 Subject: [PATCH] implement and test subtraction --- solutions/src/bigint.rs | 88 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 86 insertions(+), 2 deletions(-) diff --git a/solutions/src/bigint.rs b/solutions/src/bigint.rs index 2c501c2..7a61b4b 100644 --- a/solutions/src/bigint.rs +++ b/solutions/src/bigint.rs @@ -37,6 +37,20 @@ fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { } } +// Subtract with carry, returning the difference and the carry +fn overflowing_sub(a: u64, b: u64, carry: bool) -> (u64, bool) { + let diff = u64::wrapping_sub(a, b); + let carry_n = if carry { 1 } else { 0 }; + if diff <= a { // the first diff did not wrap + let diff_total = u64::wrapping_sub(diff, carry_n); + let had_wrap = diff_total > diff; + (diff_total, had_wrap) + } else { // the first diff did wrap + // it is impossible for this to wrap again, as we are just substracting 0 or 1 + (diff - carry_n, true) + } +} + impl BigInt { /// Construct a BigInt from a "small" one. pub fn new(x: u64) -> Self { @@ -212,11 +226,57 @@ impl ops::Add for BigInt { } } +impl<'a, 'b> ops::Sub<&'a BigInt> for &'b BigInt { + type Output = BigInt; + fn sub(self, rhs: &'a BigInt) -> Self::Output { + let max_len = cmp::max(self.data.len(), rhs.data.len()); + let mut result_vec:Vec = Vec::with_capacity(max_len); + let mut carry:bool = false; // the carry bit + for i in 0..max_len { + // compute next digit and carry + let lhs_val = if i < self.data.len() { self.data[i] } else { 0 }; + let rhs_val = if i < rhs.data.len() { rhs.data[i] } else { 0 }; + let (sum, new_carry) = overflowing_sub(lhs_val, rhs_val, carry); + // store them + result_vec.push(sum); + carry = new_carry; + } + if carry { + panic!("Wrapping subtraction of BigInt"); + } + // We may have trailing zeroes, so get rid of them + BigInt::from_vec(result_vec) + } +} + +impl<'a> ops::Sub for &'a BigInt { + type Output = BigInt; + #[inline] + fn sub(self, rhs: BigInt) -> Self::Output { + self - &rhs + } +} + +impl<'a> ops::Sub<&'a BigInt> for BigInt { + type Output = BigInt; + #[inline] + fn sub(self, rhs: &'a BigInt) -> Self::Output { + &self - rhs + } +} + +impl ops::Sub for BigInt { + type Output = BigInt; + #[inline] + fn sub(self, rhs: BigInt) -> Self::Output { + &self - &rhs + } +} + #[cfg(test)] mod tests { use std::u64; - use super::overflowing_add; - use super::BigInt; + use super::{overflowing_add,overflowing_sub,BigInt}; #[test] fn test_overflowing_add() { @@ -227,6 +287,15 @@ mod tests { assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true)); } + #[test] + fn test_overflowing_sub() { + assert_eq!(overflowing_sub(100, 10, false), (90, false)); + assert_eq!(overflowing_sub(100, 10, true), (89, false)); + assert_eq!(overflowing_sub(10, 1 << 63, false), ((1 << 63) + 10, true)); + assert_eq!(overflowing_sub(10, 1 << 63, true), ((1 << 63) + 9, true)); + assert_eq!(overflowing_sub(42, 42 , true), (u64::max_value(), true)); + } + #[test] fn test_add() { let b1 = BigInt::new(1 << 32); @@ -242,6 +311,21 @@ mod tests { assert_eq!(&b4 + &b2 + &b3 + &b4, BigInt::from_vec(vec![0, 2, 1])); } + #[test] + fn test_sub() { + let b1 = BigInt::new(1 << 32); + let b2 = BigInt::from_vec(vec![0, 1]); + let b3 = BigInt::from_vec(vec![0, 0, 1]); + let b4 = BigInt::new(1 << 63); + + assert_eq!(&b2 - &b1, BigInt::from_vec(vec![u64::max_value() - (1 << 32) + 1])); + assert_eq!(&b3 - &b2, BigInt::from_vec(vec![0, u64::max_value(), 0])); + assert_eq!(&b2 - &b4 - &b4, BigInt::from_vec(vec![0])); + assert_eq!(&b3 - &b2 - &b4 - &b4, BigInt::from_vec(vec![0, u64::max_value() - 1])); + assert_eq!(&b3 - &b4 - &b2 - &b4, BigInt::from_vec(vec![0, u64::max_value() - 1])); + assert_eq!(&b3 - &b4 - &b4 - &b2, BigInt::from_vec(vec![0, u64::max_value() - 1])); + } + #[test] fn test_inc1() { let mut b = BigInt::new(0); -- 2.30.2