OK, now that we have an environment created, let’s start writing some code. For this project I will be using Visual Studio Code, but have also tried IntelliJ IDEA with the Rust Plugin.
Step 1 – Create and project and run it
There is an associated github project to parallel this set of blog posts. There will be a directory for each day’s post. Then there will also be tags for each step of each day. Here is the code for this step. I will not always be including these links, but I will try to were the code is more complex or interesting.
$cargo new --bin day2
Created binary (application) `day2` package// Initial main.rs
fn main() {
println!("Hello, world!");
}$cargo run
Compiling day2 v0.1.0 (/my-tour-of-rust/day2)
Finished dev [unoptimized + debuginfo] target(s) in 5.81s
Running `target/debug/day2`
Hello, world!
Step 2 – Some Simple Project Euler
I chose one of the early problems. I picked Largest prime factor. This is a pretty easy problem, so it should be simple enough to demonstrate basic functionality.
The prime factors of 13195 are 5, 7, 13 and 29.
Project Euler Problem 3
What is the largest prime factor of the number 600851475143 ?
Step 2.1 – Simple Solution
To start I wrote a simple, unoptimized solution to the problem that works for 13195 in the example that is provided. However the left the program running overnight and it did not find a solution for 600851475143.
I again want to reiterate that this is not a code tutorial, but just my observations while learning some of the language. Here I am just writing the functions.
One interesting thing is the implicit return from block when a semicolon is omitted in a statement. I also like the arrow notation for the return value of the function.
A lot of this code looks similar to Java for C++ in regards to the if and for loop structure, the main different is using the range 2..=(number/2). This is similar to Python and several other languages.
fn is_prime(number : i64) -> bool {
for candidate in 2..=(number/2) {
if number % candidate == 0 {
return false;
}
}
true
}
fn largest_prime_factor(number : i64) -> i64 {
let mut prime = 1;
for factor in 1..number {
if number % factor == 0 && is_prime(factor){
prime = factor
}
}
prime
}
fn main() {
let number = 13195;
// Largest prime factor of 13195: 29
println!("Largest prime factor of {}: {}", number, largest_prime_factor(number));
let number : i64 = 60085143;
// Largest prime factor of 60085143: 13597
println!("Largest prime factor of {}: {}", number, largest_prime_factor(number));
let number : i64 = 600851475143;
// Largest prime factor of 600851475143: 6857
println!("Largest prime factor of {}: {}", number, largest_prime_factor(number));
}Step 2.2 – Some Optimization
Ok, let’s add some optimizations. I was hoping that there may be some default tooling for profiling as part of the standard Rust install, but there was not. So instead I just visually analyzed the code.
The first is to the is_prime function, since it is called a lot. I also noted that I was adding an initial optimization that divided the number by 2 and started a 2 instead of one. I decided that optimization could be generalized for the up limit of numbers that needed to be checked.
The second one is to start with the larger factor found while checking for the largest prime factor and stop once one is found. The original solution, looped through every single possibility and kept the largest one.
With the solution below the whole thing ran in around 6 seconds on my old MacBook Pro, so I will call that victory and continue .
pub fn is_prime(number : i64) -> bool {
let mut candidate : i64 = 2;
let mut limit = number / 2;
while candidate <= limit {
if number % candidate == 0 {
return false;
}
limit = number / candidate;
candidate += 1;
}
true
}
pub fn largest_prime_factor(number : i64) -> i64 {
let mut prime = 1;
for factor in 2..number {
if number % factor == 0 && is_prime(number / factor) {
prime = number / factor;
break;
}
}
prime
}Step 2.3 – Adding Documentation
Now that our code is working, we should add some documentation. This is done with the three slashes. Within the three slashes, you can add formatted documentation using Markdown.
/// Return true if the number is prime
///
/// # Arguments
///
/// * `number` - The number to check
pub fn is_prime(number : i64) -> bool {
let mut candidate : i64 = 2;
let mut limit = number / 2;
while candidate <= limit {
if number % candidate == 0 {
return false;
}
limit = number / candidate;
candidate += 1;
}
true
}
/// Return the largest factor for the number that is also prime.
///
/// # Arguments
///
/// * `number` - The number to check
pub fn largest_prime_factor(number : i64) -> i64 {
let mut prime = 1;
for factor in 2..number {
if number % factor == 0 && is_prime(number / factor) {
prime = number / factor;
break;
}
}
prime
}Once your documentation is finished, you can build the documentation using rustdoc or cargo. See the command below.
Note: The first time that ran this it did not give any output due to the fact that none of my functions were declared public. However, once I changed that I got the expected documentation.
$cargo doc --open
Documenting day2 v0.1.0 (/my-tour-of-rust/day2)
Finished dev [unoptimized + debuginfo] target(s) in 2.70s
Opening /rushtonality/rust/my-tour-of-rust/day2/target/doc/day2/index.htmlStep 2.4 – Adding Testing
To be a good software developer, you should be writing unit tests for your code, so let’s explore what Rust offers. There is build in support for testing using the attributes you see below. Here we create a tests module and import all of the functions from the parent namespace. Then you create tests with the test attribute.
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_prime_1() {
assert_eq!(true, is_prime(1));
}
#[test]
fn test_prime_2() {
assert_eq!(true, is_prime(2));
}
#[test]
fn test_prime_3() {
assert_eq!(true, is_prime(3));
}
#[test]
fn test_prime_4() {
assert_eq!(false, is_prime(4));
}
#[test]
fn test_prime_5() {
assert_eq!(true, is_prime(5));
}
#[test]
fn test_prime_large() {
assert_eq!(true, is_prime(67_280_421_310_721));
}
#[test]
fn test_largest_prime_factor_13195() {
let number = 13195;
let answer = 29;
assert_eq!(answer, largest_prime_factor(number));
}
#[test]
fn test_largest_prime_factor_60085143() {
let number = 60085143;
let answer = 13597;
assert_eq!(answer, largest_prime_factor(number));
}
#[test]
fn test_largest_prime_factor_600851475143() {
let number = 600851475143;
let answer = 6857;
assert_eq!(answer, largest_prime_factor(number));
}
}Running the tests produces the results below and everything seems to be looking good.
$cargo test
Compiling day2 v0.1.0 (/my-tour-of-rust/day2)
Finished dev [unoptimized + debuginfo] target(s) in 1.38s
Running target/debug/deps/day2-ae8bb176d077eb46
running 9 tests
test tests::test_largest_prime_factor_13195 ... ok
test tests::test_prime_1 ... ok
test tests::test_prime_2 ... ok
test tests::test_prime_3 ... ok
test tests::test_prime_4 ... ok
test tests::test_prime_5 ... ok
test tests::test_largest_prime_factor_60085143 ... ok
test tests::test_prime_large ... ok
test tests::test_largest_prime_factor_600851475143 ... ok
test result: ok. 9 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Step 3 – Factorial and Recursion
When talking about functions, one of the things you learn early is usually the idea of recursion. Usually to do this you start with either factorial sequence or the fibonacci sequence. I will explore that here, and I will also dive into Tail Recursion optimizations otherwise know as Tail Call Optimization.
Step 3.1 – Simple Solution
/// Return value in the Factorial Sequence for the given position.
/// 1, 1, 2, 6, 24, 120, 720, ...
///
/// # Arguments
///
/// * `number` - The position to evaluate
pub fn factorial_ver1(number : i64) -> i64 {
if number == 0 {
return 1;
}
return number * factorial_ver1(number-1);
}Step 3.2 – Let’s try to get a stack overflow
#[test]
fn test_factorial_ver1_large() {
let number = i64::max_value();
let answer = -1; // Expecting Stack Overflow
let result = std::panic::catch_unwind(|| factorial_ver1(number));
assert!(result.is_err());
}We have gotten it to fail. This is the what we need to test if tail recursion fixes this issue.
Note: When running this on my desktop that has a lot more memory than this laptop, the following test fails, but with integer overflow. I had to add some extra junk, i.e. a big array of integers, to make the stack memory footprint of each call bigger to cause this. I added “let a: [i64; 10000];” to the factorial_ver1 function.
...
thread 'tests::test_factorial_ver1_large' has overflowed its stack
fatal runtime error: stack overflow
error: process didn't exit successfully: `/my-tour-of-rust/day2/target/debug/deps/day2-ae8bb176d077eb46` (signal: 6, SIGABRT: process abort signal)Step 3.3 – Let’s see if Tail Recursion fixes it
Here is what Wikipedia has to say about Tail Recursion or Tail Call. I am not going to go into a big discussion of this, but basically the idea is that if the last instruction of a function is the recursive call, then the complier or interpreter and optimize by removing the previous function stack and replacing it with the new one.
I first learned about this many years ago when my sophomore level LISP professor Kurt Eiselt introduced it as a response to stability of systems using recursion. Basically saying that it was a safer way to do recursion so that you did not need to worry about stack overflows. That stuck with me, and I relay it to you.
/// Return value in the Factorial Sequence for the given position.
/// 1, 1, 2, 6, 24, 120, 720, ...
///
/// # Arguments
///
/// * `number` - The position to evaluate
pub fn factorial_ver2(number : i64) -> i64 {
factorial_ver2_internal(number, 1)
}
fn factorial_ver2_internal(number : i64, acc : i64) -> i64 {
if number == 0 {
return acc;
}
factorial_ver2_internal(number - 1, acc * number)
}
...
mod tests {
...
#[test]
fn test_factorial_ver2_large() {
let number = i64::max_value();
let result = std::panic::catch_unwind(|| factorial_ver2(number));
assert!(result.is_err());
}
...
}Based on this experiment it does look like Tail Call Optimization is working in Rust. Stack Overflow can not be catch/trapped, but integer overflow can be. That is what is happening in the above test that passes. I will go into error handling in more detail in a later port. Since it appears to work, I decided to take a deeper look.
Step 3.4 – Rabbit Hole of Tail Call Optimization in Rust
So I did decided to search for “Rust Tail Recursion”. That brought me here and then here. Then I found the this. After following this around for a while, I was confused. Was the ever implemented? If it was, it appears that some scenarios are still not, because there is still fairly recent talk about this. So, I do not know of the state of this in Rust, but my experiment above seems to show that there is some optimization for this. I you know and can give me a brief explanation, please send me a note on twitter @rushtonality.
The one thing that I did learn, was the idea of Trampolines and how Tail Call Optimization can be implemented or tricks to handle most/some scenarios. I found this page and then this fairly old post on it also. It was an interesting rabbit hole that I did not expect to go down.
Conclusions
That took a little longer to write up than I expected. I would love to hear any feedback, either good or bad regarding the series or this post. Please hit me up on twitter @rushtonality and follow me on twitter if you would like what you see, Thank you.