 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/imperative-programming/1/b/solution

Let point be the known point index. Work backwards so that each step uses just one division, rather than separately computing positional weights:

var j = bin.length - 1
var fractionalPart = 0.0
while (j > point) {
  fractionalPart = (fractionalPart + (bin(j) - '0')) / 2.0
  j -= 1
}

f r a c t i o na lP a r t = \sum_{t = j + 1}^{bin . l e n g t h - 1} (bin (t) -^{'} 0^{'}) 2^{j - t} .

Initially the suffix is empty. Incorporating digit

j

and dividing by two gives exactly the same formula with

j

replaced by

j - 1

. At exit

j = p o in t

, the result is $\sum_{t > p o in t} (bin (t) -^{'} 0^{'}) 2^{p o in t - t}$ . The loop variant is

j - p o in t

when a point exists. If a no-point input is handled by setting point=bin.length, the loop is skipped and the fractional contribution is zero;

max (0, j - p o in t)

is a loop variant covering that convention too. Trailing zeroes and an empty fractional suffix require no special arithmetic. Floating-point rounding qualifies the exact formula for long inputs.

 New to topics? Read the docs here!