= Solution
Maintain an accumulated <array> of denominators and an exact remaining <fraction>. The usual <greedy algorithm> can require a denominator larger than `Int.MaxValue`, even for an input with `Int` components. The following implementation uses <arbitrary-precision integers> internally. If that representational limit is reached, it returns the always-valid alternative consisting of `num` copies of $1/den$. Repeated denominators are permitted by the given <Egyptian fraction> representation.
``
def fromRat(num: Int, den: Int): Array[Int] = {
require(0 <= num && num < den)
val start = Reduce(num, den)
var n = BigInt(start._1)
var d = BigInt(start._2)
var e = Array.empty[Int]
while (n > 0) {
val q = (d + n - 1) / n
if (!q.isValidInt) return Array.fill(num)(den)
e = e :+ q.toInt
val nextN = n * q - d
val nextD = d * q
val g = nextN.gcd(nextD)
n = nextN / g
d = nextD / g
}
e
}
``
The <loop invariant> is $d>0$, $0\leq n<d$, all entries of `e` are positive, and
$$
\sum_{0\leq j<e.length}\frac1{e(j)}+\frac nd=\frac{num}{den}.
$$
Appending $q$ and replacing the residual by $(nq-d)/(dq)$ preserves this equality; division by the <greatest common divisor> preserves the residual's value. The <loop variant> is $n$, by the proof in part (b). If `nextN` is zero, its <greatest common divisor> with `nextD` is `nextD`, giving residual $0/1$. On normal exit the residual is zero and \b[the returned <array> has exactly the required value]. On the early-return branch, `num` copies of $1/den$ have that same value directly; the partial <greedy Egyptian fraction expansion> is discarded. `num=0` returns an empty <array>.
The fallback is a correctness provision for the fixed result type, not an efficiency claim: a large repeated-term <array> can be impractical. An <array> of <arbitrary-precision integers> would retain the <greedy Egyptian fraction expansion> without this fallback. Allocation, as with any output-producing program, requires enough available memory. The `BigInt` remainder, <greatest common divisor> and checked conversion operations are documented in <Scala 2.12 BigInt API documentation>[Methods gcd, isValidInt and toInt]{ref}.
Back to article page
