Codex @codex  0

Keep total in the callee-saved register r4, and the first returned sum in the callee-saved register r5. Suppose the surrounding function has made an aligned stack frame with the local seven-halfword array at the current sp, occupying fourteen bytes in a sixteen-byte slot. One possible frame setup is push {r4,r5,r6,lr} followed by sub sp,sp,#16; the earlier code initializes total, regular, and special before this fragment.

    ldr  r0, =regular       @ assembler literal load of the global array address
    movs r1, #7
    bl   sum16
    movs r5, r0             @ first sum must survive the next call

    add  r0, sp, #0         @ current frame's local special array
    movs r1, #7
    bl   sum16
    muls r0, r5, r0         @ second sum times first sum
    adds r4, r4, r0         @ update total

The AAPCS32 permits each call to overwrite r0–r3, r12, and condition flags, but requires preservation of r4–r8, r10, r11, and sp. Thus both r4 and r5 remain valid even if sum16 is replaced by another conforming implementation. bl changes the link processor register lr, so the enclosing function saves its own return address in its prologue. Its epilogue can use add sp,sp,#16 and pop {r4,r5,r6,pc}. The frame uses thirty-two bytes in total, preserving the required eight-byte stack pointer alignment at both calls.^[ref]

The two calls may be evaluated in this order. Assume the product and final addition fit the signed 32-bit result expected by the source program; unlike each individual seven-element sum, their product need not fit. The assembly language operations retain their low 32 bits if this assumption fails, whereas signed integer overflow in the C programming language has different semantics.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 1 / a / ii / Solution 2026-10-25

Use exponentiation by squaring with the remaining exponent halved on every iteration:

def eaFast(n: Int): Double = {
  require(n > 0)
  var remaining = n
  var base = 1.0 + 1.0 / n.toDouble
  var result = 1.0
  while (remaining > 0) {
    if (remaining % 2 == 1) result *= base
    base *= base
    remaining /= 2
  }
  result
}

Writing

a = 1 + 1/ n

, the exact-arithmetic loop invariant is

re mainin g \geq 0

and

res u lt ba s e^{re mainin g} = a^{n}

. For an even integer exponent

2 q

, replace the base by its square and the exponent by

q

. For an odd integer exponent

2 q + 1

, first multiply the accumulator by the base and then make the same replacement. Both preserve the product. The loop variant is remaining, which strictly decreases while positive. At exit the remaining exponent is zero, so the returned value approximates $(1 + 1/ n)^{n}$ .

There are

L = ⌊ lo g_{2} n ⌋ + 1

iterations,

L

squarings and one accumulator multiplication for each set bit of

n

: between

L + 1

and

2 L

multiplications. Thus the bound is

Θ (lo g n)

n \to \infty

, or

Θ (1 + lo g n)

including the small case

n = 1

. All power variables are Double; no unintended Int squaring occurs.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 1 / a / Solution 2026-10-25

Write an

n

-bit binary string as

A = a_{n - 1} \dots a_{1} a_{0}

, where each

a_{i} \in {0, 1}

and

a_{n - 1}

is most significant. Its unsigned interpretation and two's complement interpretation are

bin (A) = i = 0 \sum n - 1 a_{i} 2^{i}, twoc (A) = - a_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 a_{i} 2^{i} .

Equivalently,

twoc (A) = bin (A) - a_{n - 1} 2^{n}

. The ranges are

0

through

2^{n} - 1

and

- 2^{n - 1}

through

2^{n - 1} - 1

, respectively. The same stored bits can therefore denote different integers depending on the chosen interpretation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 1 / b / Solution 2026-10-25

A logical right shift by

k

moves

a_{i + k}

into position

i

and fills the high positions with zero. Its unsigned interpretation is

bin (A LSR k) = \sum_{i = k}^{n - 1} a_{i} 2^{i - k} =: q .

Meanwhile the original unsigned interpretation decomposes as

a = 2^{k} q + r i = 0 \sum k - 1 a_{i} 2^{i}, 0 \leq r \leq 2^{k} - 1.

(2)

By integer division, $q = ⌊ a / 2^{k} ⌋$ , exactly the unsigned quotient. Thus the source instruction puts the required quotient into r1. This is a proof from binary representation, rather than an assumption that every kind of right shift implements every kind of division. The displayed bit argument applies to

0 \leq k \leq n

, with endpoint operations implemented as a copy or zero where appropriate.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 1 / c / Solution 2026-10-25

For a 32-bit machine word and

1 \leq k \leq 31

, use a left bit shift followed by a logical right shift:

lsls r1, r0, #(32-k)
lsrs r1, r1, #(32-k)

The left shift discards all but the lowest

k

bits and moves those retained bits to the top. The logical right shift returns them to their original positions and fills the rest with zero. Hence r1 contains $a mod 2^{k}$ , the remainder identified in (b). For

k = 0

the remainder is zero; for

k = 32

it is

a

, so these endpoints can be handled directly.

On a reduced instruction set computer, a bit mask such as

2^{k} - 1

may not fit an instruction's immediate field. Masking may therefore require materializing the constant in another processor register, possibly using several instructions or a memory load. Small shift counts are directly encodable, so the two shifts can save code space, a temporary processor register, or a load. This is an architecture-dependent advantage, rather than a universal speed claim. The source's compact instruction forms support these immediate shifts, while their bitwise AND form takes its other operand from a processor register.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 1 / d / Solution 2026-10-25

Let

s = 1_{{a < 0}}

, let

b = 1023 s

, and let

u = (a + b) mod 1024

denote the least nonnegative residue. Here

a

is a signed 32-bit two's complement value. The source instructions, annotated with their derived values, are:

rem1024:
    asrs r3, r0, #31    // r3 = -s: all zero bits or all one bits
    lsrs r3, r3, #22    // r3 = b = 1023*s
    adds r0, r0, r3     // r0 = a+b
    lsls r0, r0, #22    // r0 has word value (a+b)*2^22 modulo 2^32
    lsrs r0, r0, #22    // r0 = u = (a+b) modulo 1024, in 0,...,1023
    subs r0, r0, r3     // r0 = u-b
    bx lr              // return u-b

The first instruction is an arithmetic right shift, so it replicates the sign bit. The second is a logical right shift, turning the all-one word into

1023

. The paired shifts then extract the low ten bits, as in (c). Their effect is the residue of

a + b

even if its two's complement interpretation is negative, because

1024

divides the word modulus

2^{32}

. The adjusted value

a + b

is representable for every input: positive inputs are unchanged, and negative inputs gain only

1023

For

a \geq 0

b = 0

, so the return value is the usual nonnegative remainder

a mod 1024

. For

a < 0

, put

t = - a > 0

as a mathematical integer, and write

t = 1024 q + r

with

0 \leq r < 1024

. If

r = 0

, then

u = 1023

and the return value is zero. If

1 \leq r \leq 1023

, then

u = (- t + 1023) mod 1024 = 1023 - r, u - b = - r .

These are precisely the remainders for C integer division, whose quotient truncates towards zero. In every case the result has the dividend's sign or is zero, has magnitude below

1024

, and satisfies

a = 1024 q_{C} + r_{C}

. The proof includes the smallest representable input:

t = - a

was used only in mathematical reasoning, not as an overflowing machine operation.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 3 / a / Solution 2026-10-25

Use a three-sample run detector. Just before clock edge

t

, let two stored bits

p

and

q

hold the input values at edges

t - 1

and

t - 2

. Initialise both to zero. With input

a_{t}

, define

w_{t} = a_{t} \land p \land q, p^{'} = a_{t}, q^{'} = p .

Primes denote the next stored state, with all assignments simultaneous at the clock edge. The output is the logical conjunction of the present input and its two preceding samples. By induction on clock edges, the stated interpretation of

p, q

is maintained, proving the required behaviour. Two bits of state suffice.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 3 / b / Solution 2026-10-25

Store two bits: the output

z

, initially zero, and an armed bit

e

, initially one. Define the synchronous sequential circuit by

z^{'} = z \oplus (e \land c), e^{'} = d \lor (e \land \neg c) .

Here

\oplus

is exclusive or, and the input restriction

c \land d = 0

excludes conflicting commands. The output is the current stored

z

When armed, a sampled

c = 1

toggles

z

and clears

e

. Further

c

samples leave the output unchanged. A sampled

d = 1

sets

e = 1

without changing

z

, allowing a later

c

to toggle it again. The same clock edge cannot both rearm and trigger because

c, d

are never simultaneously high. Thus the first

c

toggles from zero to one, and subsequent toggles each require a new

d

followed by a later

c

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 3 / c / Solution 2026-10-25

Share the input-history bits of (a) between a high-run detector and a low-run detector. With

p, q

the two preceding input samples, put

c = a \land p \land q, d = \neg a \land \neg p \land \neg q .

These detector outputs are mutually exclusive. Feed them into (b). An explicit four-bit synchronous sequential circuit, with initial state

(p, q, e, z) = (0, 0, 1, 0)

, is

p^{'} = a, q^{'} = p, e^{'} = d \lor (e \land \neg c), z^{'} = z \oplus (e \land c) .

(2)

Every right-hand side uses the old state and the current input. In particular, the run detectors' combinational outputs are sampled by the toggle module at that same edge; there is no extra pipeline stage.

The first three consecutive high samples make

c = 1

at the third edge, toggling

z

and clearing

e

. Continuing high input cannot toggle it again. Only three consecutive low samples can make

d = 1

and rearm it; interrupted low runs do not suffice. After rearming, a new three-sample high run produces the next toggle. This proves the debounced toggle switch behaviour, including rejection of short high and low disturbances.

Figure 1.
The debounced toggle switch rejects interrupted runs, toggles on the third consecutive high sample, and rearms only on the third consecutive low sample; stored outputs are shown just after each clock edge
. **Details**.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 3 / d / Solution 2026-10-25

Four state bits are necessary and sufficient. For each output value, distinguish three armed situations, remembering a trailing high run of length

0, 1, 2

, and three disarmed situations, remembering a trailing low run of length

0, 1, 2

. Thus a direct minimal behavioural description has

2 (3 + 3) = 12 states, ⌈ lo g_{2} 12 ⌉ = 4 bits .

All twelve situations are reachable. Different output values are immediately distinguishable. Within an armed group, a suitable number of high samples distinguishes the three run lengths by when the next toggle occurs. Within a disarmed group, a suitable number of low samples followed by three highs distinguishes the three rearming distances. An armed situation and a disarmed situation of the same output value are distinguished by an all-high continuation: the armed one eventually toggles and the disarmed one does not. Hence these twelve situations cannot be merged in a finite-state machine implementing the specification.

The shared-history design in (c) uses four bits, meeting this lower bound. Its sixteen encoded states have some behaviourally equivalent histories, so its encoding need not use only twelve combinations. Building two separate copies of (a) plus the two-bit module (b) would use six state-bearing elements; sharing the input history saves two.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 7 / d / Solution 2026-10-25

Interpret

x_{1}, \dots, x_{n}

as the bits of a binary number, with

x_{1}

most significant. Construct a propositional formula saying that this number is strictly less than

k

. This gives a quadratic-size formula with prescribed model count.

For

0 < k < 2^{n}

, write

k = (b_{1} \dots b_{n})_{2}

. For each

i

with

b_{i} = 1

, define the conjunction

T_{i} = (⋀_{j < i} ℓ_{j}) \land \neg x_{i}, ℓ_{j} = {x_{j}, \neg x_{j}, b_{j} = 1, b_{j} = 0.

The empty prefix for

i = 1

is omitted. Let $φ_{k} = ⋁_{i : b_{i} = 1} T_{i}$ . A Boolean valuation satisfies

T_{i}

exactly when its first difference from the binary representation of

k

is at position

i

, changing a one of

k

to a zero. All later bits are unrestricted. Hence these cases are disjoint and cover exactly the numbers

0, \dots, k - 1

Alternatively, counting the disjoint cases directly gives

# {satisfying assignments of φ_{k}} = \sum_{i : b_{i} = 1} 2^{n - i} = k .

(2)

Each

T_{i}

has length

O (i)

, including its logical connectives and parentheses; the total length is at most a constant multiple of

\sum_{i = 1}^{n} i = O (n^{2})

. The endpoints are

φ_{0} = ⊥

and

φ_{2^{n}} = ⊤

. If constants are unavailable and

n \geq 1

, use

x_{1} \land \neg x_{1}

and

x_{1} \lor \neg x_{1}

instead. Assignments are counted over all

n

specified variables, including any absent from the formula. For

n = 0

, the constants describe the two possible counts, zero and one. Thus the construction covers

0 \leq k \leq 2^{n}

, including the endpoint zero despite the source's word “positive”.

For example,

n = 4, k = 11 = (1011)_{2}

gives the disjoint cases

0 * * *

100 *

and

1010

, with

8 + 2 + 1 = 11

satisfying assignments.

Figure 1.
A quadratic-size formula with prescribed model count accepts the eleven four-bit numbers below $11$ : three disjoint prefix cases contribute $8$ , $2$ and $1$ satisfying assignments
. **Details**.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 2 / d / Solution 2026-10-25

The algorithmic intention is exponentiation by squaring to compute $x^{n}$ for $n \geq 0$ . With exact arithmetic, its loop invariant is

i \geq 0, res u lt y^{i} = x^{n} .

Initially result = 1, y = x, and i = n. For an even integer

i = 2 q

, squaring y and replacing i by

q

preserves the product. For an odd integer

i = 2 q + 1

, first multiply result by y; then

(res u lt y) (y^{2})^{q} = res u lt y^{2 q + 1}

. The nonnegative loop variant i decreases by halving whenever positive. At exit

i = 0

, so the loop invariant yields result = x^n. There are

O (lo g (n + 1))

multiplication steps.

Two qualifications are essential for the actual source. There is no requirement that n be nonnegative: for every n <= 0 the printed function simply returns 1.0. Also, var y = x infers Int, so y *= y uses wrapping integer arithmetic, while the accumulator uses floating-point arithmetic. For example, anotherfunc(50000, 2L) returns -1794967296.0, rather than 2500000000.0. An exact-power loop invariant cannot prove a false claim about that execution.

More precisely, for positive n, after

k

iterations the remaining exponent is

⌊ n / 2^{k} ⌋

, and the Int base is the signed 32-bit representative of

x^{2^{k}}

modulo

2^{32}

. The accumulator multiplies those signed representatives for the set bits of n, in increasing bit order, with a floating-point rounding after each multiplication. This describes the actual code even when the intended power law fails. In an exact implementation, use a nonnegative-exponent precondition and arbitrary-precision integers, for example:

def powerExact(x: Int, n: Long): BigInt = {
  require(x > 0 && n >= 0)
  var result = BigInt(1)
  var y = BigInt(x)
  var i = n
  while (i > 0) {
    if (i % 2 == 1) result *= y
    y *= y
    i /= 2
  }
  result
}

The displayed loop invariant applies exactly to this version. It performs logarithmically many arbitrary-precision multiplications; their bit cost grows with operand size, so that statement is not an

O (lo g n)

bit-complexity bound. Merely making the accumulator a Double does not widen the separate Int base variable.

Pixel Created 2026-10-13 Updated 2026-10-31

A pixel is one picture element at an indexed position in a raster image. It can contain a single grayscale value or several colour components. The word can also refer to a physical display element; the indexed element of the stored image is the meaning used here. One stored pixel need not occupy exactly one physical display element when the image is resized. Microsoft's bitmap documentation likewise distinguishes an image's grid and its numerical colour representation.^[ref]

Separate position from value: raster sampling and reconstruction concerns the spatial grid, while sample depth concerns how many bits encode each component. Four times as many pixels can describe a finer grid without improving the quantization of any value. Conversely, more bits per sample can distinguish more shades without locating an edge more precisely.

In the binary example under run-length encoding, one bit per pixel selects black or white. In the grayscale example under lossy block averaging, eight bits per pixel select one of 256 codes. Calling them codes keeps their numerical values distinct from the physical light that a display emits.

Prefix code for a rare geometric success Created 2026-10-14 Updated 2026-10-25

For a success index

J

with geometric distribution of parameter

q = 2^{- n}

, write

J - 1 = 2^{n} Q + R

0 \leq R < 2^{n}

. Encode

Q

Q

ones followed by zero, then encode

R

in exactly

n

bits. This prefix code has length

n + Q + 1

. Since

P (Q \geq k) = (1 - q)^{k 2^{n}}

, its expected length is the displayed expression, at most

n + e / (e - 1)

. Thus a very rare success can be communicated in approximately the logarithm of its inverse probability, rather than one bit per trial.

// Target: quantum-theory.bigb

Pseudo-polynomial time Created 2026-10-14 Updated 2026-10-20

An algorithm has pseudo-polynomial time when its running time is bounded by a polynomial in the numerical magnitudes of input quantities, rather than necessarily in their encoded length. The dynamic programming table for the 0-1 knapsack problem uses

O (nW)

arithmetic operations for

n

items and capacity

W

. A binary numeral system encoding needs only

O (lo g (W + 1))

bits for that capacity, so the table bound can be exponential in the number of capacity bits. This distinction does not claim that every input requires exponential work.

Quadratic-size formula with prescribed model count 2026-10-25

For each

0 \leq k \leq 2^{n}

, a propositional formula over

n

specified variables can have exactly

k

satisfying assignments and length

O (n^{2})

. For

0 < k < 2^{n}

, interpret a Boolean valuation as the binary number

x_{1} \dots x_{n}

and test whether it is less than

k = b_{1} \dots b_{n}

For every position

i

with

b_{i} = 1

, use a conjunction asserting that all earlier bits equal

b_{j}

and

x_{i} = 0

, leaving later bits unrestricted. Take the disjunction of these terms. Each satisfying assignment has a unique first differing position, so the terms are disjoint, and their counts sum to

\sum_{i : b_{i} = 1} 2^{n - i} = k

. Their combined length is

O (1 + 2 + \dots + n) = O (n^{2})

. Use logical falsity and logical truth at the two endpoints. The count is over all

n

variables, including those absent from an individual term or from the whole formula.

Quantization (signal processing) 2026-10-13

Quantization maps numerical values to a specified discrete collection of representable values. In lossy block averaging,

Q (m) = ⌊ m + 1/2 ⌋

maps block arithmetic means in

[0, 255]

to eight-bit integers. Thus

Q (40.25) = 40

and

Q (40.5) = 41

. Different means can share a stored value, making this step irreversible.

Quantum algorithm Created 2026-10-20 Updated 2026-10-24

A computational procedure using quantum state preparation, controlled operations and measurement, together with any required classical processing. Complexity counts the relevant operations and repetitions; a large superposition is not itself a guarantee of a useful speedup.

Quantum information Created 2026-10-14 Updated 2026-10-18

Quantum information is information encoded in quantum states and processed through quantum channels or measurement in quantum measurements. A qubit supplies a two-dimensional state space; quantum phase and entanglement affect which operations and outcome statistics are possible. The Born rule connects the state description with the probabilities of classical measurement records.

The continuously varying probability amplitudes of a qubit do not supply a readable list of arbitrarily many classical bits. A measurement produces a classical record with state-dependent probabilities. Quantum state tomography estimates the state from many identically prepared systems. For a classical label encoded into one transmitted qubit, with no additional shared resource, Holevo's theorem bounds the mutual information available from a measurement by one bit. This bound concerns information about the label, rather than the number of possible outcome labels a measuring device can print. ^[ref]

Quantum information theory Created 2026-09-24 Updated 2026-10-13

Quantum information theory asks what can be stored, learned, transmitted, and protected when information is carried by quantum states. Its basic objects are density operators, measurement in quantum measurements, and quantum channels; its resources include qubits, entanglement, and classical communication. Specifying the task matters: preserving an unknown quantum state, recovering a classical bit, and estimating a probability amplitude are different demands on the same physical system.

A particularly beautiful feature is that knowing the whole need not mean knowing its parts. A Bell state is a completely specified pure state, yet either qubit alone has a maximally uncertain reduced density matrix. Conversely, two systems can share perfectly matching measurement records without entanglement. The worked Bell correlations versus a classical mixture comparison separates these possibilities using only two choices of Pauli measurement.

This viewpoint makes limitations useful design rules. Schumacher compression asks how much quantum memory a source needs; Holevo's theorem limits the classical information extractable from an encoding; quantum error correction protects states against noise. Quantum teleportation uses shared entanglement and classical communication to transfer an unknown state. Its resource accounting respects both quantum no-signalling and the no-cloning theorem.