How to resolve the algorithm Egyptian division step by step in the Rust programming language

Published on 12 May 2024 09:40 PM
#Rust

How to resolve the algorithm Egyptian division step by step in the Rust programming language

Table of Contents

Problem Statement

Egyptian division is a method of dividing integers using addition and doubling that is similar to the algorithm of Ethiopian multiplication Algorithm: Given two numbers where the dividend is to be divided by the divisor:

Example: 580 / 34 Table creation: Initialization of sums: Considering table rows, bottom-up: When a row is considered it is shown crossed out if it is not accumulated, or bold if the row causes summations. So 580 divided by 34 using the Egyptian method is 17 remainder (578 - 580) or 2.

The task is to create a function that does Egyptian division. The function should closely follow the description above in using a list/array of powers of two, and another of doublings.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Egyptian division step by step in the Rust programming language

Source code in the rust programming language

fn egyptian_divide(dividend: u32, divisor: u32) -> (u32, u32) {
    let dividend = dividend as u64;
    let divisor = divisor as u64;
    
    let pows = (0..32).map(|p| 1 << p);
    let doublings = (0..32).map(|p| divisor << p);
    
    let (answer, sum) = doublings
        .zip(pows)
        .rev()
        .skip_while(|(i, _)| i > &dividend )
        .fold((0, 0), |(answer, sum), (double, power)| {
            if sum + double < dividend {
                (answer + power, sum + double)
            } else {
                (answer, sum)
            }
        });
    
    (answer as u32, (dividend - sum) as u32)
}

fn main() {
    let (div, rem) = egyptian_divide(580, 34);
    println!("580 divided by 34 is {} remainder {}", div, rem);
}

You may also check:How to resolve the algorithm Entropy step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Greatest common divisor step by step in the Java programming language
You may also check:How to resolve the algorithm Quickselect algorithm step by step in the 11l programming language
You may also check:How to resolve the algorithm Symmetric difference step by step in the Clojure programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Clay programming language