A suitable precondition, including the empty array case, isA base of one is allowed: its only valid digit is zero. The empty product is one, so permits exactly . Each Euclidean division extracts the next least significant digit.The expensive precondition is a caller obligation, rather than a separately computed product inside the conversion. Define . The loop invariant istogether with for each processed digit. The Euclidean division identity proves preservation of the reconstruction equality. Positivity of the bases gives the digit bounds and the next bound on the quotient. The loop variant is . At exit, forces , henceThere are exactly remainder operations and divisions, hence counted operations. The returned array occupies space and the remaining auxiliary space is constant. A represented value can never exceed , as follows either by the same nested expansion or by telescoping ; thus the stated range is also necessary for positive bases.
def intToDigs(n: Int, bs: Array[Int]): Array[Int] = {
// Pre: every base is positive, and 0 <= n < product(bs).
val N = bs.length
val xs = new Array[Int](N)
var i = 0
var q = n
while (i < N) {
xs(i) = q % bs(i)
q = q / bs(i)
i += 1
}
xs
} Articles by others on the same topic
There are currently no matching articles.