Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof resit / 1 / c / Solution

Count executed instructions, excluding the caller's branch-with-link and assuming the register-return and stack instructions shown above. The shift loop executes six instructions per iteration, plus four entry instructions and three exit instructions: $6\cdot 32+7=199$ instructions. The unrolled table subroutine executes 21 instructions, including four byte loads.

If every instruction, including a table load and a branch, costs one time unit, the ratio is $199/21\approx 9.48$ in favour of the table version. A more informative simple model assigns cost $L$ to each table load and unit cost to the other displayed instructions: its cost is $17+4L$, versus 199 for the loop under the same unit branch assumption. Thus this model favours lookup when $L<45.5$.

Real running time depends on the processor and memory system. Taken branches can incur extra instruction-fetch or pipeline costs, favouring the unrolled version; slow flash or cache miss events on the 256-byte table can erode that advantage. Instruction and table placement also matter. These assumptions prevent instruction counts from becoming an unsupported universal cycle claim. For a fixed 32-bit argument both implementations have constant worst-case work; the gain is a constant factor, not a different asymptotic class.