Algorithmic Rust

Well, I’m bored with my fake web app. Because I don’t know where to go next, because it doesn’t have a design or plan, because it is fake. I want to play (practice) writing Rust, but the weird “practice-this” sites always seem overly contrived: “replace all the capital letters in a given string with their ASCII-number”. Sigh. So, I’m trying something new – and probably will get over my head in no time. How about I dive into the world of algorithms: with Rust!

An 80’s Kid

I never had a formal computer science education – I grew up in the sweet spot of when nerdy kids just hacked on code and tried to make things work. I barely played computer games as a teenager, but it was very common for me to be up half the night typing in some code from a COMPUTE! magazine. Then, once it was finally in and working, adjusting the code to tweek how it ran. Oh wow – for instance, check out the code for RATS!. Anyway, the world is hidden with such great treasures, not all of them from the 80’s! Take, for example, a professor who, after teaching for a decade decides to revise and cleanup his lecture notes and, while doing so, turns them into a freely available book on algorithms. Sure, you can buy his book on Amazon for $30, but just visit Jeff Erickson’s site to get his 448-page PDF for free!! Little did I realize, until into the first chapter, this book/course is apparently NOT for undergraduates. Oh well, I’ll see how far I can get.

Come At Me

Anyway, as I’m reading through chapter 1 with the stress-free page turning of someone who won’t be actually tested on any of this. I come across a pseudo-code algorithm for something called “Peasant Multiplication”. But, I won’t murder the explanation here, just go download Erickson’s PDF. I will, however, show my interpretation of how to code that in Rust!

So here is what I came up for the algorithm itself and wrapped it so the user can try, plus there is a simple test:

main.rs

use std::env;

#[test]
fn check_peasant_mult() {
  use rand::Rng;
  let mut rng = rand::thread_rng();
  for _ in 0..10 {
    let n1 = rng.gen_range(1, 10000);
    let n2 = rng.gen_range(1, 10000);
    assert_eq!(peasant_multiplication(n1, n2), n1 * n2);
  }
}

/// Adapted from reading "Algorithms" by Jeff Erickson
/// freely available on http://jeffe.cs.illinois.edu/teaching/algorithms/
pub fn main() {
  let args: Vec<String> = env::args().collect();
  if args.len() != 2 {
    println!("Usage: {} x y (two positive integers)", args[0]);
    return;
  }
  let x = args[1].parse::<u32>().unwrap();
  let y = args[2].parse::<u32>().unwrap();
  let answer = peasant_multiplication(x, y);
  println!("{} x {} = {}", x, y, answer);
}

/// Peasant Multiplication
/// Section 1.2, page 23
pub fn peasant_multiplication(x: u32, y: u32) -> u32 {
  if x == 0 {
    return 0;
  }

  let x_prime = x / 2;
  let y_prime = y + y;
  let mut prod = peasant_multiplication(x_prime, y_prime);
  if x % 2 > 0 {
    prod += y;
  }
  return prod;
}

I thought it would be funny for someone to notice my multiplication algorithm required a random-number-generator if they looked into my Cargo.toml file, but TIL about the [dev-dependencies] section where you can list things you only need for testing! So:

Cargo.toml

[package]
name = "peasant_mult"
version = "0.1.0"
authors = ["Jeff Culverhouse <jeff@graystorm.com>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

[dev-dependencies]
rand = "0.7"

There is absolutely no reason to do multiplication this way, of course. But it let me practice my Rust WHILE learning about algorithms in computer science. It doesn’t do much, but at least it feels worthwhile and not contrived. THIS is how some people (long, long ago) did multiplication – and it was fun to reproduce it. Multiplication inside your computer’s CPU doesn’t happen the way you think either, but I don’t know anything about that so go off on a Google tangent if you like!

Anyway, this one is simple and short enough I think I’ll just leave you the exercise of getting his PDF and comparing his quick mention of Peasant Multiplication and my implementation. You probably see something to improve or ways in which I am not writing idiomatic Rust (like that for loop in the test). Feel free to suggest some changes here! Also, I put this up on github, because why not? And I have some more coming.

The post Algorithmic Rust appeared first on Learning Rust.