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

Published on 12 May 2024 09:40 PM
#Swift

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

Source code in the swift programming language

extension BinaryInteger {
  @inlinable
  public func egyptianDivide(by divisor: Self) -> (quo: Self, rem: Self) {
    let table =
      (0...).lazy
        .map({i -> (Self, Self) in
          let power = Self(2).power(Self(i))

          return (power, power * divisor)
        })
        .prefix(while: { $0.1 <= self })
        .reversed()

    let (answer, acc) = table.reduce((Self(0), Self(0)), {cur, row in
      let ((ans, acc), (power, doubling)) = (cur, row)

      return acc + doubling <= self ? (ans + power, doubling + acc) : cur
    })

    return (answer, Self((acc - self).magnitude))
  }

  @inlinable
  public func power(_ n: Self) -> Self {
    return stride(from: 0, to: n, by: 1).lazy.map({_ in self }).reduce(1, *)
  }
}

let dividend = 580
let divisor = 34
let (quo, rem) = dividend.egyptianDivide(by: divisor)

print("\(dividend) divided by \(divisor) = \(quo) rem \(rem)")

You may also check:How to resolve the algorithm Sorting algorithms/Merge sort step by step in the Groovy programming language
You may also check:How to resolve the algorithm Sum and product of an array step by step in the Quackery programming language
You may also check:How to resolve the algorithm Non-decimal radices/Input step by step in the Scheme programming language
You may also check:How to resolve the algorithm Partition function P step by step in the Raku programming language
You may also check:How to resolve the algorithm CRC-32 step by step in the J programming language