Keep a running product of the fixed base. In particular, The loop invariant is and . Initially the empty product is one. Multiplication by
1.0/n uses floating-point arithmetic, avoiding the truncation that integer division would introduce:def eaLinear(n: Int): Double = {
require(n > 0)
val base = 1.0 + 1.0 / n.toDouble
var k = 0
var result = 1.0
while (k < n) {
result *= base
k += 1
}
result
}base and incrementing k preserve the invariant. The loop variant decreases by one. On exit , so the result is , with exactly multiplications and time complexity. With Double, the operational result is the rounded recurrence, rather than an exact real power; this distinction applies to the next two power computations too.Use exponentiation by squaring, retaining the unprocessed exponent in Writing , the loop invariant is and . If the old exponent is , , multiplying the accumulator by and replacing the remaining power by preserves the invariant. When , the unused squaring may be omitted. The nonnegative integer
k:def eaBinary(n: Int): Double = {
require(n > 0)
var base = 1.0 + 1.0 / n.toDouble
var k = n
var result = 1.0
while (k > 0) {
if ((k & 1) != 0) result *= base
k = k / 2
if (k > 0) base *= base
}
result
}k is a loop variant, since for . At exit the remaining power is one, giving . There are iterations, at most one accumulator multiplication and one squaring per iteration, hence multiplications and constant space.Generate each reciprocal factorial from the preceding one, instead of recomputing a factorial for every summand:The loop invariant is , , and . Initially and . The division produces , which is then added to the previous partial sum. The loop variant is . Consequently the returned value is , using exactly divisions and additions, no multiplications, and time complexity. The slightly weaker precondition also permits the useful zero-term boundary case. For
def eb(n: Int): Double = {
require(n >= 0)
var i = 0
var term = 1.0
var sum = 1.0
while (i < n) {
i += 1
term /= i.toDouble
sum += term
}
sum
}Double, small positive terms eventually cease to change sum because of floating-point rounding.First rearrange the ratios so that the intermediate powers remain moderate:This avoids separately forming enormous powers such as . Perform the two instances of exponentiation by squaring in one while loop, using coupled binary exponentiation:With and , the loop invariant is , , and . Each active branch preserves its own power identity by the parity argument in part (a)(ii), and an inactive branch changes nothing. The loop variant is the mathematical integer , which need not be computed in a fixed-width variable: it decreases whenever either exponent is positive. At exit , , proving the returned expression is . There are iterations, at most four loop multiplications each, and two final multiplications. Converting
def ec(n: Int): Double = {
require(n > 1)
val dn = n.toDouble
var x = 1.0 + 1.0 / dn
var y = 1.0 + 1.0 / (dn - 1.0)
var k = n
var l = n - 1
var p = 1.0
var q = 1.0
while (k > 0 || l > 0) {
if (k > 0) {
if ((k & 1) != 0) p *= x
k /= 2
if (k > 0) x *= x
}
if (l > 0) {
if ((l & 1) != 0) q *= y
l /= 2
if (l > 0) y *= y
}
}
(dn + 1.0) * p - dn * q
}n before adding one avoids integer overflow at Int.MaxValue.The rearrangement avoids floating-point overflow in the original powers, but subtraction still combines two quantities of order to obtain one of order one. Catastrophic cancellation can amplify their accumulated roundoff error. The mathematical approximation error therefore does not imply that the
Double implementation improves indefinitely as n grows.Choose the reciprocal-factorial summation
eb for asymptotically high accuracy, counting multiplications and divisions as arithmetic work. For tolerance , linear powering in part (a)(i) takes multiplications; binary exponentiation in part (a)(ii) reduces this to . Part (c) also has arithmetic work, since its required grows like , though its constants and cancellation error differ.By the reciprocal-factorial series remainder bound, the omitted positive tail satisfiesThus the factorial denominator grows much faster than an exponential in the number of iterations. For decimal places, setting of order gives by Stirling's approximation, rather than binary-power arithmetic steps. This is a comparison in an exact-arithmetic operation-count model; the stated Big O notation does not determine the exact winner for every small tolerance. Taken literally,
eb uses zero multiplications and only divisions. Fixed double-precision floating-point format cannot deliver arbitrarily many correct decimal places, and the precision-dependent cost of arbitrary-precision arithmetic is a separate issue. Articles by others on the same topic
There are currently no matching articles.