Because , exponentiation to base is strictly increasing. The definition of the floor function gives , so the equivalent characterization of the integer logarithm isHere is a nonnegative integer; gives .
Keep both the exponent and its power. This Oberon procedure uses only the permitted arithmetic:The loop invariant is and . It holds initially because . A successful guard permits the next power, and the two assignments preserve the relation between and . At exit, , which is exactly part (a). Each iteration increases , and only finitely many powers of are at most , proving algorithm termination. The returned value is . Its running time is arithmetic operations; integer overflow is deferred to part (e).
PROCEDURE IntLog(b, n: INTEGER): INTEGER;
VAR i, p: INTEGER;
BEGIN
i := 0; p := 1;
WHILE p*b <= n DO
p := p*b; i := i+1
END;
RETURN i
END IntLog;Use repeated squaring, including index zero:The loop invariant is for , with for every stored entry except possibly the initial entry when . Squaring gives , proving preservation. The first failed guard identifies the first larger power outside the range. If , no power with needs storing.
b2[0] := b; top := 0;
WHILE b2[top]*b2[top] <= n DO
b2[top+1] := b2[top]*b2[top];
top := top+1
END;Index zero is deliberately included. The original paper asks for indices but then claims that their products represent every allowable power. Taken without , that claim fails for odd exponents, since every available exponent would be even. The extra initialized entry makes the intended binary expansion argument valid without changing the requested entries.
Let be the largest representable positive integer. The worst case is , requiring indices through . Thus
enough = 5 for signed 32-bit integers, or 6 for signed 64-bit integers, suffices for stored powers that fit; a larger convenient constant is harmless. This counts slots starting at zero and does not reserve a slot for an out-of-range sentinel. The multiplication in the guard can still suffer integer overflow, independently of this array capacity bound.Store a second array For the second loop, write . Immediately before processing , its loop invariant isInitially the failed squaring guard gives ; this also holds when , since then . The test succeeds exactly when . If successful, adding selects that binary digit; otherwise the upper bound tightens to . Either way the invariant holds for the next smaller . At , , so
weight with weight[k] = 2^k. Descending through the binary digits of the answer gives this greedy algorithm:PROCEDURE FastLog(b, n: INTEGER): INTEGER;
VAR b2, weight: ARRAY enough OF INTEGER;
top, k, i, p: INTEGER;
BEGIN
b2[0] := b; weight[0] := 1; top := 0;
WHILE b2[top]*b2[top] <= n DO
b2[top+1] := b2[top]*b2[top];
weight[top+1] := weight[top]+weight[top];
top := top+1
END;
i := 0; p := 1; k := top;
WHILE k >= 0 DO
IF p*b2[k] <= n THEN
p := p*b2[k]; i := i+weight[k]
END;
k := k-1
END;
RETURN i
END FastLog;i = L.There are squarings and descending tests. For fixed , this is arithmetic operations, hence logarithmic in the bit length of , and also within the weaker bound. This counts arithmetic operations on integers as unit cost; bit complexity would also charge for the growing operands. No division is used.
Let be the maximum positive machine integer. A positive product suffers integer overflow when . The vulnerable expressions are
p*b in part (b), b2[top]*b2[top] in the table guard, and p*b2[k] in the descending search. Even a rejected candidate must be evaluated before its comparison with .The table guard becomes dangerous as soon as its current entry exceeds : approximately for signed 32-bit integers, or for signed 64-bit integers. These are thresholds for the intermediate power, not for alone. For example, with 32-bit arithmetic, and reach the stored power and then try its overflowing square . If , even the initial square may overflow for a tiny . In part (b), the final test can overflow when the next power above exceeds ; at , this already happens for .
For positive operands, integer division gives the exact equivalence . Therefore replace the three guards respectively byand perform each multiplication only after its guard succeeds. Every accepted product is then at most . With these guarded products and sufficient table capacity, the algorithms work throughout , . The stored exponents and weights also fit in those machine ranges. Checking for overflow after multiplying would be too late.
p <= n DIV b
b2[top] <= n DIV b2[top]
p <= n DIV b2[k] Articles by others on the same topic
There are currently no matching articles.