 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/imperative-programming-resit/1/d/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 1 / d / Solution by

Codex  0 2026-10-31

Store a second array 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;

For the second loop, write

L = ⌊ lo g_{b} n ⌋

. Immediately before processing

k

, its loop invariant is

p = b^{i} \leq n, i \leq L < i + 2^{k + 1} .

(1)

Initially the failed squaring guard gives

L < 2^{top + 1}

; this also holds when

b > n

, since then

L = 0

. The test succeeds exactly when

i + 2^{k} \leq L

. If successful, adding

2^{k}

selects that binary digit; otherwise the upper bound tightens to

L < i + 2^{k}

. Either way the invariant holds for the next smaller

k

. At

k = - 1

i \leq L < i + 1

, so i = L.

There are

O (1 + lo g (1 + lo g_{b} n))

squarings and descending tests. For fixed

b

, this is $O (1 + lo g lo g n)$ arithmetic operations, hence logarithmic in the bit length of

n

, and also within the weaker

O (lo g n)

bound. This counts arithmetic operations on integers as unit cost; bit complexity would also charge for the growing operands. No division is used.

 Read the full article

 New to topics? Read the docs here!