Code Excursion

Egyptian Multiplication Algorithm

I have started reading the book From Mathematics to Generic Programming. In the second chapter the authors discuss an Egyptian method of multiplication that involves the use of a table. First you make the table and then you use it to perform multiplication. Below is a table for multiplying 21 by 23. 21 is our Multiplier and 23 is our Multiplicand. Start with 1 and 23. Then double them for every following row. 23 + 23 is 46, 46 + 46 is 92 and so on.

This leverages the ease of adding something to itself to create the table. The algorithm uses addition to get the final result. We add 16 + 4 + 1 in the first column to get 21. Then we add the corresponding values in the second column to get the correct answer. 23 + 92 + 368 = 483.

Having read through the chapter I will now code my own implementation. Followed by an implementation of the authors version. My naive first look into the problem is to code a solution that mimics how a human would approach the problem. Below is my solution. In the end I used recursion and tuples to solve the problem. Without tuples I likely would have developed a solution using multiple methods and many more lines of code. Loving the tuples!

My Solution Egyptian Multiplication

fn main() {
    let multiplier: i32 = 21;
    let multiplicand: i32 = 23;
    let (result, end_multiplier) = find_result(1,multiplier, multiplicand);
    println!("\nResult:  {}", result);
}


fn find_result(start_multiplier: i32, multiplier: i32, multiplicand: i32) -> (i32, i32) {
	let mut return_values: (i32, i32) = (0,0);
    if start_multiplier * 2 <= multiplier {
		return_values = find_result(start_multiplier * 2, multiplier, multiplicand);
    } else {
        return_values.1 = multiplier;
    }   
    println!("In progress: {}-{}", return_values.0, return_values.1);
    if return_values.1 >= start_multiplier {
		return_values.1 = return_values.1 - start_multiplier;
		return_values.0 = return_values.0 + (start_multiplier * multiplicand);
    }	
    return (return_values.0, return_values.1);
}

Russan Peasant Algorithm

While the Russian Peasant Algorithm is related to Egyptian Multiplication, mathematically, the algorithmic steps are different. First we start with our multiplier (21) and our multiplicand (23) and place them in the first row of a two column table. Then divide the first column by two and drop the remainders until the value one is reached. Double the value in the second column for each row. To get the correct result discard any row that has an even value in the first column. Adding the remaining values in the second column will give you your result. 23 + 92 + 368 = 483. Shown below.

The Russian Peasant version was simpler and easier to implement.

My Solution Russian Peasant

fn main() {
    println!("Result: {}", find_result(21, 23, 0));
}

fn find_result(multiplier: i32, multiplicand: i32, result: i32) -> i32 {
    let mut new_result = result;
    if multiplier.trailing_zeros() < 1 {
       println!("Odd : {} - {}", multiplier, multiplicand);
       new_result = result + multiplicand;   
    }
    if multiplier > 1 {
      new_result = find_result(multiplier /2, multiplicand * 2, new_result);
    }
    new_result
}