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

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm Egyptian division step by step in the Go 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 Go programming language

The given Go code demonstrates the Egyptian Division algorithm, an ancient method for dividing two integers without using multiplication or division operators. It calculates the quotient and remainder of two positive integers, dividend and divisor.

Function Signature and Error Handling:

func egyptianDivide(dividend, divisor int) (quotient, remainder int) {
   if dividend < 0 || divisor <= 0 {
       panic("Invalid argument(s)")
   }
}

The egyptianDivide function takes two positive integers, dividend and divisor, as arguments. It performs error handling to ensure that both arguments are positive and that the divisor is greater than 0. If either condition is not met, it panics with an error message.

Calculating Powers of Two and Doublings:

   powersOfTwo := []int{1}
   doublings := []int{divisor}
   doubling := divisor
   for {
       doubling *= 2
       if doubling > dividend {
           break
       }
       l := len(powersOfTwo)
       powersOfTwo = append(powersOfTwo, powersOfTwo[l-1]*2)
       doublings = append(doublings, doubling)
   }

This section iteratively calculates powers of two and their corresponding doubled values. It starts with powersOfTwo containing only 1 and doublings containing the divisor. The for loop doubles the current doubling until it exceeds the dividend. At each iteration, it updates powersOfTwo and doublings to include the doubled values.

Egyptian Division Algorithm:

   answer := 0
   accumulator := 0
   for i := len(doublings) - 1; i >= 0; i-- {
       if accumulator+doublings[i] <= dividend {
           accumulator += doublings[i]
           answer += powersOfTwo[i]
           if accumulator == dividend {
               break
           }
       }
   }

The Egyptian Division algorithm is implemented in this loop. It iterates through the doublings array in reverse order, starting from the largest double. It checks if adding the current double to the accumulator (accumulator) is less than or equal to the dividend. If so, it adds the double to the accumulator and updates the answer with the corresponding powerOfTwo. This process continues until the accumulator reaches the value of the dividend.

Returning Quotient and Remainder:

   return answer, dividend - accumulator
}

Finally, the function returns the calculated quotient and the remaining dividend minus the accumulated value (accumulator).

Main Function:

func main() {
   dividend := 580
   divisor := 34
   quotient, remainder := egyptianDivide(dividend, divisor)
   fmt.Println(dividend, "divided by", divisor, "is", quotient, "with remainder", remainder)
}

The main function demonstrates the use of the egyptianDivide function. It divides dividend by divisor and prints the quotient and remainder. In this example, it divides 580 by 34, resulting in a quotient of 17 and a remainder of 0.

Source code in the go programming language

package main

import "fmt"

func egyptianDivide(dividend, divisor int) (quotient, remainder int) {
    if dividend < 0 || divisor <= 0 {
        panic("Invalid argument(s)")
    }
    if dividend < divisor {
        return 0, dividend
    }
    powersOfTwo := []int{1}
    doublings := []int{divisor}
    doubling := divisor
    for {
        doubling *= 2
        if doubling > dividend {
            break
        }
        l := len(powersOfTwo)
        powersOfTwo = append(powersOfTwo, powersOfTwo[l-1]*2)
        doublings = append(doublings, doubling)
    }
    answer := 0
    accumulator := 0
    for i := len(doublings) - 1; i >= 0; i-- {
        if accumulator+doublings[i] <= dividend {
            accumulator += doublings[i]
            answer += powersOfTwo[i]
            if accumulator == dividend {
                break
            }
        }
    }
    return answer, dividend - accumulator
}

func main() {
    dividend := 580
    divisor := 34
    quotient, remainder := egyptianDivide(dividend, divisor)
    fmt.Println(dividend, "divided by", divisor, "is", quotient, "with remainder", remainder)
}


  

You may also check:How to resolve the algorithm Pseudo-random numbers/PCG32 step by step in the OCaml programming language
You may also check:How to resolve the algorithm Rosetta Code/Count examples step by step in the Sidef programming language
You may also check:How to resolve the algorithm Maximum triangle path sum step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Rep-string step by step in the J programming language
You may also check:How to resolve the algorithm Longest common subsequence step by step in the Icon and Unicon programming language