An Egyptian fraction need not be proper: several positive unit fractions may sum to at least one. Accordingly, accumulate a general nonnegative reduced fraction, rather than calling the proper-input-only The loop invariant is , , , , andWriting , the fraction for the extended prefix has numerator and denominator . These are the
Reduce on every intermediate value. First define an exact helper:def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
var n = BigInt(0)
var d = BigInt(1)
var i = 0
while (i < e.length) {
require(e(i) > 0)
val x = BigInt(e(i))
val g = d.gcd(x)
val nextN = n * (x / g) + d / g
val nextD = d * (x / g)
val h = nextN.gcd(nextD)
n = nextN / h
d = nextD / h
i += 1
}
(n, d)
}
def toRat(e: Array[Int]): (Int, Int) = {
val result = toRatExact(e)
require(result._1.isValidInt && result._2.isValidInt,
"Reduced result does not fit (Int, Int)")
(result._1.toInt, result._2.toInt)
}nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is . At exit the helper returns the exact sum in lowest terms, including for the empty array.There are three distinct ways to control integer overflow: cancel the common denominator factor before multiplication, reduce after each addition, and use arbitrary-precision arithmetic when the remaining values still exceed fixed-width bounds. Cancellation reduces intermediate size but cannot guarantee that an exact answer fits
(Int, Int). For example, the sum is in lowest terms, whose denominator exceeds Int.MaxValue. No implementation returning that fixed type can represent every permitted input exactly. The wrapper therefore checks this unavoidable result-type limitation instead of silently truncating; toRatExact supplies the unrestricted mathematical result.[ref]Scala 2.12 BigInt API documentation. Checked representability with isValidInt before the potentially truncating toInt conversion
Articles by others on the same topic
There are currently no matching articles.