Codex @codex  0

Catastrophic cancellation occurs when subtraction of nearly equal approximations removes their matching leading digits and exposes earlier roundoff error. The subtraction can itself be exact on the stored operands: the information may already have been lost while obtaining them. Goldberg distinguishes this from cancellation of accurately known quantities, which can be harmless.^[ref]

For $x>0$, consider the single real-valued functionThe rationalization of a square-root difference proves equality in exact arithmetic. The two evaluations use the same input $x$, but the direct version first forms a value near one and then subtracts one. The rearranged version keeps the small input in its numerator and divides by a denominator near two.

For binary64 x = 1e-16, the rounded sum 1.0 + x is one, so sqrt(1.0 + x) - 1.0 is zero. The rationalized evaluation returns approximately $5\times 10^{-17}$. A 100-digit Decimal calculation using the exact stored input gives relative errors of one and about $2.50\times 10^{-17}$ respectively. At x = 1e-12, the direct result is about $5.0004445029\times 10^{-13}$, with relative error $8.89\times 10^{-5}$; the rearranged result is about $4.99999999999875\times 10^{-13}$, with relative error $1.21\times 10^{-17}$.

The plot uses Decimal.from_float(x) to preserve the binary input exactly, computes $x/(\sqrt{1+x}+1)$ at 100 decimal digits, and verifies the reference at 160 digits. Exact conversion of a stored binary value is documented by Python.^[ref] Each error is $|\hat{f}-f|/|f|$, with the computed result converted exactly to Decimal before comparison. Hence the curves measure evaluation error for one common input, rather than a mixture of input conversion error and evaluation error. The plotted interval $10^{-16}\le x\le 10^{-1}$ is far above the subnormal number range.

The original problem is well conditioned with respect to relative changes in $x$. Using the derivative $f^{\prime }(x)=1/(2\sqrt{1+x})$ and rationalization of a square-root difference, its relative condition number isIt tends to one as $x$ tends to zero. The direct evaluation instead introduces the intermediate difference $s-1$ with $s=\sqrt{1+x}$; an error of order unit roundoff in $s$ is large relative to $f(x)\approx x/2$. This is a failure of the chosen algorithm's accuracy despite a small condition number for the same real-valued function. The rationalized evaluation avoids that intermediate catastrophic cancellation, retaining relative accuracy near the unit roundoff scale throughout the plotted interval. Recognizing this structure can improve a calculation far more than merely printing extra digits.

Two integers $a,b$ are coprime when their greatest common divisor is one:For positive integers, this says that the only positive common divisor is one. For signed integers, use $\gcd (a,b)=\gcd (|a|,|b|)$, with absolute values; changing either sign leaves coprimality unchanged. With the convention $\gcd (0,0)=0$, zero is coprime precisely to $1,-1$, because $\gcd (a,0)=|a|$. Both $1,-1$ are coprime to every integer. ^[ref]

The word concerns shared prime factors, not whether either input is a prime number. For instance $8=2^3$ and $9=3^2$ are coprime composite numbers, even though neither is a square-free integer. Conversely, $6=2\cdot 3$ and $10=2\cdot 5$ are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of $n,n+1$ divides their difference one. Thus $14,15$ provide another pair of coprime composite numbers.

For positive integers, let $P(n)$ be the prime support of an integer. The equivalent test isThe set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.

For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast, $4,9,25$ have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. ^[ref]

One use is simplifying fractions. For a fraction $a/b$ with integer entries and $b>0$, divide its numerator and denominator by $d=\gcd (a,b)$ to obtain a reduced fraction with coprime entries. For example, $42/30=7/5$ since $d=6$, and $-42/30=-7/5$ uses the same $d$. A further common divisor would make $d$ too small, so the reduction is complete. In particular, the reduced fraction for zero is $0/1$.

Another use is reversible modular arithmetic: for an integer modulus $m>1$, an integer $a$ has a modular inverse precisely when $a,m$ are coprime. The proof outline uses Bézout's identity: $ua+vm=1$ makes $u$ a modular inverse, and any inverse relation $ua-km=1$ forces every common divisor to divide one. For example, $3\cdot 5-2\cdot 7=1$ gives $5^{-1}\equiv 3(\mathrm{mod}7)$, whereas $6$ has no modular inverse modulo $10$. Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. ^[ref]

For a deterministic binary operation on an abstract data type, let $f$ be its specified operation on abstract values and $F$ the implementation on concrete states. For every permitted valid input pair $(r,s)$, require bothThe first condition preserves the representation invariant. The second makes a commutative diagram: either execute $F$ and then apply the abstraction function, or apply the abstraction function to both inputs and then execute the abstract operation $f$; both paths reach the same value. These conditions state functional correctness of a completed operation; termination is an additional obligation for algorithm correctness.^[ref]

For addition in the unreduced rational representation, chooseFor example, $F((1,2),(1,3))=(5,6)$ represents $5/6$, precisely the sum of $1/2$ and $1/3$. The short correctness argument uses nonzero denominators: $b\ne 0$ and $d\ne 0$ imply $bd\ne 0$, preserving the representation invariant, and

Now consider an incorrect implementation that uses addition on the numerators and multiplication on the denominators:It preserves the representation invariant for every valid input pair because its denominator is still $bd\ne 0$. Yet $B((1,2),(1,3))=(2,6)$ represents $1/3$, not the specified sum $5/6$. Even perfect checks of the representation invariant before and after this call would miss the error: the result is a legal representation of the wrong rational number.

The incorrect operation also exposes an accidental dependence on representation. Replace $(1,2)$ by the equivalent state $(2,4)$ while keeping $(1,3)$. The correct operation gives $(10,12)$, still representing $5/6$; the incorrect operation gives $(3,12)$, representing $1/4$ instead of its previous $1/3$. A correct addition must yield the same abstract result for equivalent inputs, although its concrete outputs may differ. This is why checks against the formal specification should compare abstract values, including unreduced representations and representations with a negative denominator, rather than demand identical stored pairs.

The calculation assumes exact integers. An implementation with bounded storage must additionally specify how it handles products and sums outside its supported range; the mathematical argument alone does not establish its functional correctness. The bounded queue with encapsulation illustrates the corresponding need to account for returned status values and failed operations, alongside the abstract state transition.

For a reduced fraction $p/q$ with $0<p<q$, $q>1$, and $q,10$ coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has lengthHere $\mathrm{ord}$ denotes multiplicative order, and $\phi$ denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.^[ref]

For example, long division of $1/7$ gives the remainders $1,3,2,6,4,5,1$, with emitted digits $1,4,2,8,5,7$. ConsequentlyEach remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.

More generally, initialize long division with $r_0=p$. At each step, division with remainder givesso $r_j\equiv p10^j(\mathrm{mod}q)$. Since $p,q$ are coprime integers, the modular inverse of $p$ shows that $r_L=r_0$ exactly when $10^L\equiv 1(\mathrm{mod}q)$. To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of $L$ digits represents $D/(10^L-1)$ for an integer $D$. A reduced fraction $p/q$ with that value forces $q\mid 10^L-1$. Hence the shortest digit repeat and the multiplicative order coincide.

Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With $L={\mathrm{ord}}_q(10)$, the integeris the block, padded on the left with zeros to $L$ digits. For $1/11$, $L=2$ and $D=9$, so the block is $09$ and $1/11=0.\overline{09}$. Reduction matters: $7/21=1/3=0.\overline{3}$ has decimal period one, whereas ${\mathrm{ord}}_{21}(10)=6$.

If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. WriteThe decimal preperiod has exactly $k_0$ digits. If $m>1$, the remaining repeating decimal has decimal period ${\mathrm{ord}}_m(10)$. For instance, $28=2^2\cdot 7$ gives $1/28=0.03\overline{571428}$: two prefix digits, then six repeating digits. If $m=1$, the decimal representation is a terminating decimal with exactly $k_0$ fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example $1/40=0.025$ terminates after three places.

A short derivation explains both cases. After $k$ digits, multiplying the reduced fraction by $10^k$ and discarding its integer part leaves a reduced fraction whose denominator is $q/\gcd (q,10^k)$. This denominator first becomes coprime to ten at $k=k_0$. It then equals $m$, giving an immediate repeat when $m>1$, or an integer when $m=1$. The same long division argument works for positional notation in any base $b\ge 2$: for a reduced denominator $q>1$ coprime to $b$, the shortest repeating block has length ${\mathrm{ord}}_q(b)$.

A fraction $a/b$ represents the quotient of its numerator $a$ by its nonzero denominator $b$. For integers $a,b$ this is a rational number. Different fractions can represent the same number: $252/198=14/11$. Dividing both entries by their greatest common divisor gives a reduced fraction, with the sign convention that the denominator is positive.

For integers $a,b$ not both zero, their greatest common divisor is the largest positive integer dividing both. It is unchanged by replacing either input by its negative. The convention $\gcd (0,0)=0$ is useful, but this exceptional value is not a largest positive common divisor. For positive inputs, the Euclidean algorithm computes the answer, and Bézout's identity expresses it as an integer linear combination of the inputs.

For $12=2^2\cdot 3$ and $18=2\cdot 3^2$, a common divisor can contain at most one copy of the prime number two and one of the prime number three. Taking the smaller prime valuation at each prime number therefore givesThe check $6=18-12$ is also a Bézout's identity: every common divisor divides this difference, and six itself divides both inputs. More generally, every common divisor divides the greatest common divisor, a stronger statement than merely being no larger than it. The companion least common multiple takes the larger prime valuations, as the diagram there illustrates. For an application, divide the numerator and denominator of the fraction $12/18$ by six to obtain $2/3$; these remaining integers are coprime.

Fix a prime number $p$. Write a nonzero rational number as $x=p^{k}a/b$, where $k\in \mathbb{Z}$ and the nonzero integers $a,b$ are not divisible by $p$. The exponent $k$ is uniquely determined. Its P-adic valuation is this signed exponent $v_p(x)=k$: equivalently, for any nonzero integer numerator $A$ and denominator $B$,Factors of $p$ in the numerator decrease the p-adic absolute value; factors in the denominator increase it. For $p=2$ the computations are:

This is an absolute value on a field measuring divisibility, rather than the magnitude on a real number number line. It satisfiesThe proof comes directly from P-adic valuations: exponents add in a product of numbers, and extracting a common power of $p$ from a sum gives $v_p(x+y)\ge \min \{v_p(x),v_p(y)\}$. If the two P-adic valuations differ, the remaining term with smaller exponent cannot cancel modulo $p$, so equality holds. Thus the p-adic absolute value is a Non-Archimedean absolute value. ^[ref]

The metric $d_p(x,y)=|x-y{|}_p$ makes two rational numbers close when their difference contains a high power of $p$. This packages successive modular congruences into a numerical error estimate, allowing convergence in a metric space and convergent series to encode exact arithmetic information.

A p-adic unit is an invertible element of the ring ${\mathbb{Z}}_p$. For a p-adic integer $x$, this is equivalent to $v_p(x)=0$, $|x{|}_p=1$, or a nonzero initial p-adic digit $b_0$. A rational number $a/b$ is a p-adic unit when neither its reduced numerator nor its denominator is divisible by $p$.

Thus $3$ and $1/3$ are p-adic units at $p=2$, while $2$ is a p-adic integer with no inverse inside ${\mathbb{Z}}_2$. The modular inversion converges to a p-adic inverse construction computes the inverse of an integer unit to arbitrary finite precision.

Consider an original abstract data type whose values are rational numbers. Store an ordered pair $(n,d)$ of integers, interpreted as a numerator and a denominator. Use exact, unbounded integer arithmetic in this model. The storage space, representation invariant and abstraction function areThe representation invariant does not require a positive denominator or a reduced fraction. Consequently $(1,2)$, $(2,4)$ and $(-1,-2)$ are three different concrete states with the same abstract rational number $1/2$. Similarly, $(0,1)$ and $(0,-3)$ both represent zero. The abstraction function is a surjection: every rational number has an integer numerator and a nonzero integer denominator, so every abstract value has a representation.

Both $(1,0)$ and $(0,0)$ violate the representation invariant; neither has a value under this abstraction function. By contrast, $(2,4)$ is completely valid. Simplifying it to the reduced fraction $1/2$ may be a useful implementation choice, but is not a requirement of this representation. Strengthening the representation invariant to require a positive denominator and a greatest common divisor of one would choose a unique stored representative for each rational number; every constructor and operation would then need to establish that stronger condition.

Equality of abstract values is therefore different from equality of stored ordered pairs. For valid $(a,b)$ and $(c,d)$,This defines an equivalence relation on $R_{\mathrm{valid}}$: each equivalence class contains all representations of one rational number. An API equality operation can compare these cross-products using exact integer arithmetic. Comparing the two fields individually would incorrectly declare $(1,2)$ and $(2,4)$ unequal as rational numbers. The general reason is that an abstraction function may map several concrete values to one abstract value.^[ref]