From 17ab30e2988868e5f59b36bb0364cadb0a1c42f8 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Mon, 15 Jun 2015 22:46:30 +0200 Subject: [PATCH] start doing the course-part of BigInt --- solutions/src/bigint.rs | 123 ++++++++++++++++++------------------ src/main.rs | 3 +- src/part05.rs | 135 ++++++++++++++++++++++++++++++++++++++++ src/part06.rs | 89 ++++++++++++-------------- src/part07.rs | 30 +++++++++ 5 files changed, 270 insertions(+), 110 deletions(-) create mode 100644 src/part07.rs diff --git a/solutions/src/bigint.rs b/solutions/src/bigint.rs index e9dfdf0..0abb6b3 100644 --- a/solutions/src/bigint.rs +++ b/solutions/src/bigint.rs @@ -2,30 +2,41 @@ use std::ops; 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(v: &Vec) -> 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, // 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 { @@ -53,43 +64,6 @@ impl BigInt { 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; - } - } - // 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[..] - } - /// Increments the number by "by". pub fn inc(&mut self, mut by: u64) { let mut idx = 0; @@ -129,34 +103,65 @@ impl Clone for BigInt { } } - 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 { + 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 = Vec::with_capacity(cmp::max(self.data().len(), rhs.data().len())); + let mut result_vec:Vec = 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 } } } diff --git a/src/main.rs b/src/main.rs index 06ad4b2..15b798c 100644 --- a/src/main.rs +++ b/src/main.rs @@ -70,7 +70,7 @@ // * [Part 03](part03.html) // * [Part 04](part04.html) (WIP) // * (to be continued) -#![allow(dead_code, unused_imports, unused_variables)] +#![allow(dead_code, unused_imports, unused_variables, unused_mut)] mod part00; mod part01; mod part02; @@ -78,6 +78,7 @@ mod part03; mod part04; mod part05; mod part06; +mod part07; // To actually run the code of some part (after filling in the blanks, if necessary), simply edit the `main` // function. diff --git a/src/part05.rs b/src/part05.rs index 274e3b5..25c98e2 100644 --- a/src/part05.rs +++ b/src/part05.rs @@ -1,2 +1,137 @@ // Rust-101, Part 05: Copy, Clone // ============================== + +use std::cmp; +use std::ops; + +// In the course of the next few parts, we are going to build a data-structure for +// computations with *bug* numbers. We would like to not have an upper bound +// to how large these numbers can get, with the memory of the machine being the +// only limit. +// +// We start by deciding how to represent such big numbers. One possibility here is +// to use a vector of "small" numbers, which we will then consider the "digits" +// of the big number. This is like "1337" being a vector of 4 small numbers (1, 3, 3, 7), +// except that we will use `u64` as type of our base numbers. Now we just have to decide +// the order in which we store numbers. I decided that we will store the least significant +// digit first. This means that "1337" would actually become (7, 3, 3, 1).
+// Finally, we declare that there must not be any trailing zeros (corresponding to +// useless leading zeros in our usual way of writing numbers). This is to ensure that +// the same number can only be stored in one way. + +// To write this down in Rust, we use a `struct`, which is a lot like structs in C: +// Just a collection of a bunch of named fields. Every field can be private to the current module +// (which is the default), or public (which would be indicated by a `pub` in front of the name). +// For the sake of the tutorial, we make `dat` public - otherwise, the next parts of this +// course could not work on `BigInt`s. Of course, in a real program, one would make the field +// private to ensure that the invariant (no trailing zeros) is maintained. +pub struct BigInt { + pub data: Vec, +} + +// Now that we fixed the data representation, we can start implementing methods on it. +impl BigInt { + // Let's start with a constructor, creating a `BigInt` from an ordinary integer. + // To create an instance of a struct, we write its name followed by a list of + // fields and initial values assigned to them. + pub fn new(x: u64) -> Self { + if x == 0 { + BigInt { data: vec![] } + } else { + BigInt { data: vec![x] } + } + } + + // It can often be useful to encode the invariant of a data-structure in code, so here + // is a check that detects useless trailing zeros. + pub fn test_invariant(&self) -> bool { + if self.data.len() == 0 { + true + } else { + self.data[self.data.len() - 1] != 0 + } + } + + // We can convert any vector of digits into a number, by removing trailing zeros. The `mut` + // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally + // change the vector `v`. In this case, we need to make that annotation to be able to call `pop` + // on `v`. + pub fn from_vec(mut v: Vec) -> Self { + while v.len() > 0 && v[v.len()-1] == 0 { + v.pop(); + } + BigInt { data: v } + } +} + +// If you have a close look at the type of `BigInt::from_vec`, you will notice that it +// consumes the vector `v`. The caller hence loses access. There is however something +// we can do if we don't want that to happen: We can explicitly `clone` the vector, +// which means that a full (or *deep*) copy will be performed. Technically, +// `clone` takes a borrowed vector, and returns a fully owned one. +fn clone_demo() { + let v = vec![0,1 << 16]; + let b1 = BigInt::from_vec(v.clone()); + let b2 = BigInt::from_vec(v); +} + +// To be clonable is a property of a type, and as such, naturally expressed with a trait. +// In fact, Rust already comes with a trait `Clone` for exactly this purpose. We can hence +// make our `BigInt` clonable as well. +impl Clone for BigInt { + fn clone(&self) -> Self { + BigInt { data: self.data.clone() } + } +} +// Making a type clonable is such a common exercise that Rust can even help you doing it: +// If you add `#[derive(Clone)]' right in front of the definition of `BigInt`, Rust will +// generate an implementation of `clone` that simply clones all the fields. Try it! +// +// To put this in perspective, `clone` in Rust corresponds to what people usually manually do in +// the copy constructor of a C++ class: It creates new, independent instance containing the +// same values. Contrary to that, if you pass something to a function normally (like the +// second call to `from_vec` in `clone_demo`), only a *shallow* copy is created: The fields +// are copied, but pointers are simply duplicated. This corresponds to the default copy +// constructor in C++. Rust assumes that after such a copy, the old value is useless +// (as the new one uses the same pointers), and hence considers the data semantically +// moved to the copy. That's another explanation of why Rust does not let you access +// a vector anymore after you passed ownership to some function. + +// With `BigInt` being about numbers, we should be able to write a version of `vec_min` +// that computes the minimum of a list of `BigInt`. We start by writing `min` for +// `BigInt`. Now our assumption of having no trailing zeros comes in handy! +impl BigInt { + fn min(self, other: Self) -> Self { + // Just to be sure, we first check that both operands actually satisfy our invariant. + // `debug_assert!` is a macro that checks that its argument (must be of type `bool`) + // is `true`, and panics otherwise. It gets removed in release builds, which you do with + // `cargo build --release`. + // + // If you carefully check the type of `BigInt::test_invariant`, you may be surprised that + // we can call the function this way. Doesn't it take `self` in borrowed form? Indeed, + // the explicit way to do that would be to call `(&other).test_invariant()`. However, the + // `self` argument of a method is treated specially by Rust, and borrowing happens automatically here. + debug_assert!(self.test_invariant() && other.test_invariant()); + // If the lengths of the two numbers differ, we already know which is larger. + if self.data.len() < other.data.len() { + self + } else if self.data.len() > other.data.len() { + other + } else { + // **Exercise**: Fill in this code. + panic!("Not yet implemented."); + } + } +} + +fn vec_min(v: &Vec) -> Option { + let mut min: Option = None; + for e in v { + // In the loop, `e` now has type `&i32`, so we have to dereference it. + min = Some(match min { + None => e.clone(), + Some(n) => e.clone().min(n) + }); + } + min +} diff --git a/src/part06.rs b/src/part06.rs index 3b867aa..21046c6 100644 --- a/src/part06.rs +++ b/src/part06.rs @@ -1,67 +1,56 @@ -// Rust-101, Part 06: Abstract Datastructure, Testing -// ================================================== +// Rust-101, Part 06: Lifetimes, Testing +// ===================================== use std::cmp; use std::ops; +use std::fmt; +use part05::BigInt; -pub struct BigInt { - data: Vec, // least significant digits first. The last block will *not* be 0. -} -impl BigInt { - pub fn new(x: u64) -> Self { - if x == 0 { - BigInt { data: vec![] } - } else { - BigInt { data: vec![x] } - } +impl PartialEq for BigInt { + fn eq(&self, other: &BigInt) -> bool { + debug_assert!(self.test_invariant() && other.test_invariant()); + self.data == other.data } } -/// 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) - } - } +fn call_eq() { + let b1 = BigInt::new(13); + let b2 = BigInt::new(37); + println!("b1 == b1: {} ; b1 == b2: {}; b1 != b2: {}", b1 == b1, b1 == b2, b1 != b2); } -#[test] -fn test_overflowing_add() { - assert_eq!(overflowing_add(10, 100, false), (110, false)); - assert_eq!(overflowing_add(10, 100, true), (111, false)); - assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true)); - assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true)); - assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true)); + +impl fmt::Debug for BigInt { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.data.fmt(f) + } } -impl ops::Add for BigInt { - type Output = BigInt; - fn add(self, rhs: BigInt) -> Self::Output { - let mut result_vec:Vec = 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() { - // compute next digit and carry - 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 { data: result_vec } + + +impl BigInt { + pub fn inc(&mut self, mut by: u64) { + panic!("Not yet implemented."); } } +#[test] +fn test_inc() { + let mut b = BigInt::new(1337); + b.inc(1337); + assert!(b == BigInt::new(1337 + 1337)); + + b = BigInt::new(0); + assert_eq!(b, BigInt::from_vec(vec![0])); + b.inc(1 << 63); + assert_eq!(b, BigInt::from_vec(vec![1 << 63])); + b.inc(1 << 63); + assert_eq!(b, BigInt::from_vec(vec![0, 1])); + b.inc(1 << 63); + assert_eq!(b, BigInt::from_vec(vec![1 << 63, 1])); + b.inc(1 << 63); + assert_eq!(b, BigInt::from_vec(vec![0, 2])); +} diff --git a/src/part07.rs b/src/part07.rs new file mode 100644 index 0000000..e9715e0 --- /dev/null +++ b/src/part07.rs @@ -0,0 +1,30 @@ +use std::cmp; +use std::ops; +use part05::BigInt; + +// Add with carry, returning the sum and the carry +fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { + let sum = u64::wrapping_add(a, b); + if sum >= a { + panic!("First addition did not overflow. Not implemented."); + } else { + panic!("First addition *did* overflow. Not implemented."); + } +} + +/*#[test]*/ +fn test_overflowing_add() { + assert_eq!(overflowing_add(10, 100, false), (110, false)); + assert_eq!(overflowing_add(10, 100, true), (111, false)); + assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true)); + assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true)); + assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true)); +} + +impl ops::Add for BigInt { + type Output = BigInt; + fn add(self, rhs: BigInt) -> Self::Output { + let mut result_vec:Vec = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len())); + panic!("Not yet implemented."); + } +} -- 2.30.2