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