= Computation
A <computation> applies specified rules to represented information to obtain a result. The rules may operate on exact integers, symbolic expressions or approximate numerical values; the representation determines which operations and errors must be considered.
The <Euclidean algorithm> computes a greatest common divisor by replacing $(a,b)$ with $(b,a\bmod b)$ until the second entry is zero. For $(30,18)$ the pairs become $(18,12)$, $(12,6)$ and $(6,0)$, yielding six. The identity $\gcd(a,b)=\gcd(b,a\bmod b)$ proves correctness, while decreasing positive remainders prove termination. <Computability theory> asks whether a suitable <algorithm> exists; computational complexity asks what resources it requires.
Back to article page
