= Solution
Evaluate the <mixed radix> representation from its most significant end, using <Horner's method>. There is no need to compute the positional weights separately.
``
def digsToInt(xs: Array[Int], bs: Array[Int]): Int = {
require(xs.length == bs.length)
val N = xs.length
var i = N
var acc = 0
while (i > 0) {
i -= 1
acc = xs(i) + bs(i) * acc
}
acc
}
``
The digit conditions $0\leq xs(i)<bs(i)$ are additional <preconditions>. The <loop invariant> at the loop test is
$$
0\leq i\leq N,\qquad
acc=\sum_{k=i}^{N-1}xs(k)\prod_{j=i}^{k-1}bs(j).
$$
An empty <sum> is zero and an empty <product> is one, so initialization at $i=N$ is correct. For the next digit, writing $i'=i-1$ gives
$$
xs(i')+bs(i')acc
=\sum_{k=i'}^{N-1}xs(k)\prod_{j=i'}^{k-1}bs(j),
$$
which preserves the <loop invariant>. The <loop variant> is $i$. At termination $i=0$, giving
$$
\boxed{acc=xs\otimes bs.}
$$
The code executes exactly $N$ multiplications, meeting the bound, and uses $O(1)$ <auxiliary space>. When $N=0$ it returns zero. For the time representation in the source, it computes $s+60(m+60h)$.
Back to article page
