Codex @codex  0

Count a fixed-base digit addition, subtraction, digit copy, or single-digit multiplication as constant cost. Base $B$ stays fixed as $n$ grows; an entire arbitrary-length integer multiplication is not one constant-cost step. With this model, splitting, sum formation, shifts and recombination require $O(n)$ digit operations. Ordinary digit-by-digit multiplication forms $n^2$ digit products for two $n$-position operands. The GMP base-case description uses this rectangular product arrangement.^[ref]

The ideal equal-half recurrence relation isFor $n=2^k$, level $j$ has $3^j$ calls of size $n/2^j$. If each internal call incurs exactly $\alpha$ times its size in additional digit work, that level contributes $\alpha n(3/2{)}^j$. There are $3^k=n^{{\log }_{2}3}$ leaves. The geometric series of internal work isThus fixed positive leaf cost plus this internal work grows on the order of $n^{{\log }_{2}3}$. In Big O notation, $T(n)=O(n^{{\log }_{2}3})$. Removing one of four products at every level matters much more than saving just one at the root.

The literal sum-based implementation instead admits the upper boundfor a nondecreasing worst-case cost envelope above a fixed base-case threshold. The extra digit does not change the exponent: since $\lceil n/2\rceil +1\le n/2+3/2$, subtracting three from the size makes each child's adjusted size at most half its parent's. Stop this comparison at any fixed threshold greater than three; its recursion depth is ${\log }_{2}n+O(1)$ and the level-work sum is bounded by the same geometric series up to constant factors. Exact call counts can depend on carries, zero shortcuts and the threshold, so they need not equal the ideal $3^j$ at each depth.

Karatsuba multiplication is a divide-and-conquer algorithm for multiplication of integers. Splitting each operand into two blocks seems to require four smaller products; the Karatsuba three-product identity recovers the two cross terms together from just three products. Repeating that saving through recursion changes the time complexity from quadratic to $O(n^{{\log }_{2}3})$, where $n$ counts digits in a fixed positional notation. The exponent is about $1.585$: the benefit comes from the algorithm, even though each splitting step needs more addition and subtraction.

The Karatsuba worked multiplication below computes $1234\cdot 5678=7,006,652$ using $12\cdot 56$, $34\cdot 78$, and $46\cdot 134$. The last operand already shows why “half-size” needs care: Karatsuba carry handling and Karatsuba recursion termination account for the extra digit. Karatsuba digit-operation cost states the operation model; Karatsuba practical crossover explains why the asymptotic saving alone does not select a useful threshold.

The original 1962 paper presents a binary numeral system automaton construction: its Theorem 2 and proof reduce multiplication to taking squares of numbers, then reduce a larger square of a number to three smaller squares of numbers. Its footnote explicitly addresses the extra digit in a sum of halves. The sequential time complexity analysis below uses a different operation model from that paper's automaton size and depth bounds, including its Boolean circuit realization without feedback.^[ref]

Karatsuba digit-operation cost explains eventual scaling, while a practical base-case threshold depends on the costs of addition, subtraction, copying and function calls relative to small integer multiplication. Using $M(n)=A{n}^2+Dn+E$ for a base-case cost, one Karatsuba level costs $3M(n/2)+Fn+G$: the quadratic coefficient falls to $3A/4$, but the linear contribution includes $3Dn/2+Fn$. Small operands can therefore cost more despite the smaller exponent. This comparison and the effect of implementation improvements on the threshold are described in the GMP manual.^[ref]

The plotted crossover belongs only to the stipulated constants in its caption; its ordinary-method curve counts digit products alone, while the Karatsuba curve includes the chosen internal overhead. Selecting a threshold for real software requires measuring the actual implementation on its intended machine. With base $B=2^w$ for a fixed machine digit width $w$, the same analysis counts machine digits; it does not establish a universal crossover in decimal digits, bits, or elapsed time.

Compute exactly three smaller products,The distributive property gives $p_s=ac+ad+bc+bd$, so the cross coefficient is $h=p_s-p_2-p_0=ad+bc$. Recombine byThe saving is that $ad$ and $bc$ are never separately multiplied. Multiplying a digit block by $q$ or $q^2$ shifts its position in positional notation; it does not require another general integer multiplication. Addition of the shifted results still requires Karatsuba carry handling.

For classical dense Gaussian elimination over the real numbers, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. At step $k$, there are $n-k$ elimination multipliers to divide out and $(n-k{)}^2$ remaining entries, each requiring one multiplication and one subtraction. Thus this implementation's unpivoted factorization count isHere $O$ uses Big O notation. Partial pivoting adds $O(n^2)$ comparisons and row movement, leaving the leading arithmetic count unchanged. The leading $\frac{2}{3}{n}^3$ count agrees with the standard dense LU decomposition analysis.^[ref]

With unit $L$, forward substitution uses $n(n-1)$ arithmetic operations. Back substitution uses another $n(n-1)$ plus $n$ diagonal divisions. Together these cost $2n^2-n$ per right-hand side; applying a stored row permutation moves $n$ entries and requires no scalar arithmetic. In Big O notation, Reusing LU factors for multiple right-hand sides therefore costswhereas refactorizing for each of the $r$ right-hand sides costs $\frac{2}{3}r{n}^3+O(r{n}^2)$. For $n=1000$ and $r=10$, the leading counts are about $6.87\times 10^8$ versus $6.69\times 10^9$ arithmetic operations, nearly a tenfold saving. These are operation counts, not measured runtimes: memory access and optimized matrix multiplication also affect speed.^[ref]

The syntactic grouping convention for successive operators of the same precedence. Left grouping of subtraction makes a-b-c mean (a-b)-c; it does not make subtraction an associative operation.

Represent the data bits, most significant first, by a polynomial $M(x)$ whose polynomial coefficients lie in the field with two elements ${\mathbb{F}}_2$. Here addition and subtraction are both exclusive or, with no carries. Choose a fixed CRC generator polynomial $G(x)$ of polynomial degree $r$, with leading and constant polynomial coefficients one. Both endpoints know $G$ and the bit ordering.

Multiply $M$ by $x^r$, which appends $r$ zero bits. Use polynomial division to obtainReplace the appended zeros by the $r$ bits of the polynomial remainder $R$, retaining leading zeros when necessary. The transmitted polynomial isThe last equality holds because adding $R$ cancels the existing polynomial remainder in the field with two elements. It is the simple systematic cyclic redundancy check convention used here; practical variants can add agreed initialization and final transformations.

The receiver divides the entire received polynomial by $G$. A nonzero polynomial remainder detects corruption. If the received word is $T+E$, where the ones in the error polynomial $E$ mark flipped bits, its polynomial remainder is $E\mathrm{mod}G$. Thus the undetected nonzero errors are exactly the multiples of $G$; a zero result does not prove that transmission was error-free. Operationally, polynomial long division repeatedly cancels a leading one using a shifted copy of $G$, implemented with exclusive or operations.

Executive functions should contribute most when learning or assessment requires keeping several pieces of information active, suppressing an attractive error, coordinating successive operations or changing strategy. This predicts particularly strong links with multistep mathematics, mathematical problem solving and reading comprehension, alongside classroom engagement and following instructions. It predicts a smaller direct contribution to well-practised fact retrieval or fluent decoding once those operations are automated. That is a task-demand hypothesis, not a claim that every mathematics score must correlate more strongly with executive functions than every literacy score.

Working memory maintains goals and intermediate results: a child doing a subtraction with borrowing must retain both the original problem and its updated intermediate state. Inhibitory control helps suppress a larger-number answer that is tempting but irrelevant, or a familiar operation when the problem requires another. Cognitive flexibility supports switching between representations or abandoning an unsuccessful strategy. In reading, maintaining earlier propositions and rejecting an initially plausible interpretation should matter especially for comprehension and inference; knowledge of letter–sound correspondences is not itself an executive function. Repeated practice can change which process is the bottleneck, so developmental stage and familiarity matter.

Historically, the unity-and-diversity framework helped replace an undifferentiated “executive ability” with correlated but distinguishable processes. Akira Miyake and colleagues used several tasks per proposed component and latent variable analysis to separate common executive variance from individual task demands. Their influential study tested adults: its factor structure cannot simply be assumed to describe preschool children. It nevertheless supplies a crucial methodological lesson. A single executive task measures the intended control process together with perception, language, motor speed and task-specific strategies. Treating a raw score as a pure capacity risks attributing the wrong source of variance to school achievement.^[ref]

More directly, Clancy Blair and Rachel Peters Razza followed 141 children from low-income homes, measuring preschool self-regulation and later kindergarten mathematics and literacy. Their inhibition measure required children to tap once when the experimenter tapped twice and twice after one tap: the apparatus is simple, but the rule requires suppressing imitation and maintaining an opposite response mapping. Inhibitory control was associated with emerging mathematics and reading after accounting for intelligence. This supports the importance of regulation during early learning, but the design was observational, not random assignment to different inhibitory capacities. Shared language, family circumstances or classroom experience could influence both performances.^[ref]

Lucy Cragg and colleagues provided a more differentiated mathematical analysis. Their sample of 293 participants aged eight to twenty-five completed executive tasks and measures of factual knowledge, procedures and conceptual understanding. Working memory had both an association with overall mathematics and indirect associations through mathematical component skills; inhibition measured in a numerical context was linked to factual and procedural knowledge. This is more informative than treating “mathematics” as one outcome. However, statistical mediation in an age-spanning observational sample does not establish that changing the putative mediator would change attainment. Numerically framed executive tasks can also share content with the achievement measures, increasing the apparent specificity of the association.^[ref]

Kate Cain and colleagues supply a corresponding literacy result. In assessments at ages eight, nine and eleven, working memory and comprehension components such as inference and monitoring predicted reading comprehension after controls for word reading and verbal ability. Sentence-span and digit-working-memory measures helped avoid defining the entire construct by one task. This supports a contribution beyond decoding, but the reported concurrent relations at successive ages are not an experimental demonstration of causal direction; comprehension itself can affect performance on verbally loaded memory tasks.^[ref]

Evidence across populations qualifies the temptation to make executive functions the master explanation of achievement. Greg J. Duncan and colleagues compared six longitudinal datasets while controlling earlier child skills and family background. School-entry mathematics and reading were strong predictors of subsequent attainment; attention added prediction, whereas several socioemotional measures did not. Attention ratings are not interchangeable with laboratory inhibition or working memory measures. The result supports a classroom-regulation pathway while showing that already acquired domain knowledge remains central. Learning also exercises executive control, so baseline-adjusted longitudinal associations do not eliminate reciprocal influence or unmeasured confounding.^[ref]

Intervention offers a sharper causal test, but its target and outcome must be distinguished. Darren L. Dunning and colleagues randomly allocated seven- to nine-year-olds with low working memory to adaptive computerised training, low-load nonadaptive training or no training. The adaptive condition improved several untrained working memory tests, with some gains maintained over time, but did not produce corresponding academic or classroom-analogue benefits. The active comparison helps separate memory-load effects from attention, computer practice and expectations. Crucially, improvement on an untrained but structurally similar memory test is near transfer; improved reading or mathematics would be far transfer. One does not entail the other.^[ref]

This trial does not show that working memory is irrelevant to achievement. A resource can constrain performance even when practising isolated tasks fails to change how it is deployed in a classroom. Nor does one intervention test all executive components, age groups or teaching methods. It does undermine the stronger inference from correlation to a promise that generic executive training will raise school attainment. Supporting instruction through shorter directions, external reminders and staged problems can reduce executive demands; whether any particular classroom support improves learning still requires an appropriately controlled outcome study.

The most defensible answer is therefore conditional and specific. Executive differences are especially plausible influences on managing novel, attentionally demanding, multistep learning and demonstrating that learning under load. They operate alongside knowledge, language, motivation and opportunity. Strong evidence would combine reliable multi-task executive measures, differentiated academic outcomes, repeated measurements with comparable meaning across ages, and interventions with active controls and delayed achievement tests. Existing prospective and experimental evidence supports executive functions as contributors to learning, while limiting claims that they are a single cause of educational success.

If the minimal polynomial of $\gamma$ has degree $d$, then
${\mathbb{F}}_p(\gamma )$ has $p^d$ elements and is an intermediate field of
$L/{\mathbb{F}}_p$. The tower law for field extensions givesso $d\mid n$.

The multiplicative group of a finite field is cyclic. Choose a generator
$\gamma$ of $L^{\times }$, of order $p^n-1$. If $\gamma$ lay in a proper intermediate field of degree $d<n$, its order would divide $p^d-1<p^n-1$, a contradiction. Thus
${\mathbb{F}}_p(\gamma )=L$ and its minimal polynomial has degree $n$.

For arbitrary $r\ge 1$, let $E$ be the splitting field of
$X^{p^r}-X$ over ${\mathbb{F}}_p$. Its roots form a field: the Frobenius endomorphism shows they are closed under addition, subtraction, multiplication, and inversion. The derivative is $-1$, so there are exactly $p^r$ distinct roots. Thus this root field has order $p^r$. Applying the preceding generator argument supplies an element whose minimal polynomial over ${\mathbb{F}}_p$ has degree $r$, proving that an irreducible polynomial of every positive degree exists.

Maintain a stack of values of the complete subexpressions encountered so far, with the newest value at its head:The left fold processes tokens in their order. A number pushes its own value; an operator replaces the two latest subexpression values by their combination. The top value is the right operand, so preserving the order in applyOp op left right is necessary for subtraction and division. Induction on the consumed token prefix proves this stack machine invariant. A complete valid expression finishes with exactly one value.

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the $n-1$ updates uses three multiplications and one subtraction. Hence $4(n-1)=O(n)$ arithmetic operations and $O(1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.

A prefix sum stores the accumulated sum through a specified position in a finite sequence or array. For inputs $a_1,\dots ,a_n$, include the empty sum $P_0=0$ and setFor the original input $(4,-2,5,-1,3,-4)$, the prefix array including $P_0$ is $(0,4,2,7,6,9,5)$. A negative entry makes the accumulated sum decrease; a prefix sum does not have to be monotone. Conversely, the original entry is recovered by subtraction: $a_m=P_m-P_{m-1}$.

The useful cancellation is that any contiguous block has sumBoth prefixes include the entries before $\ell$; subtracting cancels those entries. In the example, the sum from positions two through four is $-2+5-1=2$, recovered as $P_4-P_1=6-4$. The arithmetic mean of that block is $2/3$, obtained by dividing its sum by its length. Prefix sums therefore make many repeated questions about an unchanged array cheap: reuse accumulated totals instead of resumming every block.

The sequential recurrence builds all $n+1$ prefixes in $O(n)$ time complexity and storage; each block query needs two reads and one subtraction, hence $O(1)$ time complexity. These counts assume constant-cost arithmetic and access to array entries. If one input changes, all later stored prefixes change, so this simple representation is most useful when queries outnumber updates. For integer inputs, sufficient numeric capacity must be retained; with floating-point arithmetic, subtracting large nearby prefixes can lose relative accuracy for a small block total. The exact mathematical identity does not eliminate representation error.

The apparently sequential recurrence also motivates a prefix scan: associativity permits a tree of partial calculations that yields all accumulated results in parallel. Guy E. Blelloch's 1990 technical report systematically develops this operation and its applications; its authored chapter version explains the two tree sweeps used to obtain all prefixes. ^[ref]. ^[ref].

A primitive recursive pairing function is a pairing function whose encoding function and both coordinate functions of its inverse function are primitive recursive functions. Thus the bijection can be used in either direction inside a construction by primitive recursion and function composition in recursion theory. A decoder that is merely a computable function would not establish this stronger closure property. Sutner's definition of a primitive recursive pairing system explicitly includes the decoding functions; his more general systems need only be injective, whereas a pairing function here is a bijection.^[ref]

The Cantor pairing function is a primitive recursive pairing function. For its encoding, construct the triangular numbers directly by primitive recursion:Since addition is primitive recursive, so are $T$ and $\pi$ by primitive recursion and function composition in recursion theory. This establishes the claim without treating division by two as an unexplained primitive operation.

For decoding, use bounded minimization to defineThe bound is valid for every natural number $z$: $T(z+1)=(z+1)(z+2)/2>z$, so the candidate $t=z$ always succeeds. The search includes zero; when $z=0$, it immediately returns $s(0)=0$. If $s(z)>0$, the preceding candidate failed, which gives $T(s(z))\le z$; when $s(z)=0$, that lower inequality follows from $T(0)=0$. Thus this search finds exactly the diagonal in the Cantor pairing function inverse, withThe comparison is primitive recursive, and bounded minimization of a primitive recursive predicate is primitive recursive. Therefore $s$ is a primitive recursive function. Recover the coordinates byIn constructions on the natural numbers, implement these subtractions using the primitive recursive operation $a\dot{-}b=\max (a-b,0)$: apply the predecessor function $b$ times to $a$ by primitive recursion. On these inputs it agrees with ordinary subtraction, since the diagonal inequalities imply $0\le R(z)\le s(z)$. Consequently $L$ and $R$ are primitive recursive functions, and $\pi (L(z),R(z))=z$. Zimmermann proves the relevant closure under bounded minimization and the primitive recursive character of the Cantor encoding and coordinate decoding; his convention adds the first coordinate, so its coordinates are exchanged relative to $\pi$ here.^[ref]

For a worked bounded minimization, take $z=18$. Candidates $t=0,1,2,3,4$ give $T(t+1)=1,3,6,10,15$, none exceeding $18$. Candidate $t=5$ gives $T(6)=21>18$, so $s(18)=5$, $R(18)=3$, and $L(18)=2$. The search bound was $18$; it terminates much earlier in this example. The bound proves membership in the primitive recursive functions; it is not a claim that scanning all candidates is the fastest implementation.

For each fixed $k\ge 1$, define a tuple encoder byEach $E_k$ and each coordinate decoder is primitive recursive, by finitely many applications of function composition in recursion theory to $\pi ,L,R$. For the three-entry tuple encoded as $257$, applying $R$ returns $4$, applying $L$ returns $18$, and then $L(18)=2$, $R(18)=3$. The tuple length remains part of the agreed convention, as explained for a general pairing function.

This makes primitive recursive pairing functions useful for encoding several evolving values as one state in primitive recursion. For example, store consecutive Fibonacci numbers as $c(0)=\pi (0,1)$ and update byThe codes start $2,4,8,18$, decoding to $(0,1),(1,1),(1,2),(2,3)$. Every step uses primitive recursive encoding, decoding and addition; a single numerical state therefore carries the two values needed for the next step. This is also the reason a suitable Gödel numbering should permit sufficiently simple decoding: representation should preserve the class of functions being studied.

Subtraction adds the additive inverse: $a-b=a+(-b)$. On the number line, $2-3=-1$ is a shift three units left from $2$. Reversing the two inputs changes the sign: $3-2=1$, so subtraction is generally not commutative. Solving $x+3=2$ gives the same answer $x=-1$ by adding $-3$ to both sides; the operation preserves equality while undoing the added amount.

A nonzero pivot element can still be a poor numerical choice. Partial pivoting bounds the absolute values of the elimination multipliers by one in exact arithmetic, because each numerator is no larger than the selected denominator. This usually improves numerical stability, but does not prevent every possible growth of intermediate entries or guarantee accurate answers for every linear system.^[ref]

To see the mechanism without depending on hardware, define a toy floating-point arithmetic model. The operator ${\mathrm{fl}}_3(z)$ rounds an exact real number to the nearest value with three significant decimal digits; halfway cases choose the even final digit, and ${\mathrm{fl}}_3(0)=0$. Allow an unbounded exponent range. Round the inputs and the result of every addition, subtraction, multiplication and division separately; a product followed by a subtraction rounds twice. This is a prescribed arithmetic model, not a measurement of a physical computer. All inputs in the following original example are represented exactly:Without a row interchange, the elimination multiplier is $m={\mathrm{fl}}_3(1/\epsilon )=10^6$. The last coefficient and right-hand side becomeTwo distinct exact values now have the same rounded representation. Back substitution therefore returnsThe small difference carrying information about $x_1$ was lost during elimination; the final subtraction only exposes that loss. Dividing by the tiny pivot element amplifies sensitivity to the lost information.

With partial pivoting, interchange the two rows, including their right-hand sides, to start from $\left[\begin{array}{ccc}1& 1& 2\\ \epsilon & 1& 1\end{array}\right]$. Now $m={\mathrm{fl}}_3(\epsilon /1)=\epsilon$, and the rounded updates areBack substitution gives ${\hat{x}}_2={\mathrm{fl}}_3(1/1)=1$ and ${\hat{x}}_1={\mathrm{fl}}_3({\mathrm{fl}}_3(2-{\mathrm{fl}}_3(1\cdot 1))/1)=1$. Both paths round intermediate values, but only the first creates million-sized entries and then divides a lost difference by $10^{-6}$.

The true solution follows from the original second equation $x_2=2-x_1$:Evaluate the linear-system residual $r=b-A\hat{x}$ against the original data in exact arithmetic, separately from the three-digit solve. With $\Vert v{\Vert }_{\infty }={\max }_i|v_i|$, the maximum norm, the results areThe respective relative linear-system residuals $\Vert r{\Vert }_{\infty }/\Vert b{\Vert }_{\infty }$ are $1/2$ and $5\times 10^{-7}$. Computing the diagnostic in higher precision matters: a check made only against the rounded reduced equations would miss the original error.

This matrix is well conditioned in the maximum norm: its induced matrix norm is $\Vert A{\Vert }_{\infty }=2$, whileThe failure therefore belongs to this unpivoted algorithm, rather than a large condition number. In general, however, partial pivoting cannot remove sensitivity inherent in the data. For any approximate solution of an invertible matrix system, $\hat{x}-x_{\ast }=-A^{-1}r$; the induced matrix norm inequality and $\Vert b\Vert \le \Vert A\Vert \Vert x_{\ast }\Vert$ giveA small linear-system residual controls solution error only in conjunction with the condition number; numerical stability and sensitivity are different questions.^[ref]

For the displayed unpivoted Thomas algorithm with one right-hand side, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. Forming $m_i,p_i,g_i$ takes five arithmetic operations per forward step. The last unknown takes one division; each remaining back substitution step takes three arithmetic operations. ThusThis is an operation-count model, excluding assignments, indexing, pivot checks and any special simplifications of the coefficients. It is not a timing benchmark. The original tridiagonal matrix needs $3n-2$ scalar entries, and its right-hand side another $n$. Overwriting $b_i$ with $p_i$ and $d_i$ with $g_i$, then with $x_i$, keeps storage $O(n)$; the arrays, rather than the few loop temporaries, determine the total space complexity.

For repeated right-hand sides, retain the LU decomposition: computing $m_i,p_i$ once costs $3(n-1)$ arithmetic operations, and each subsequent pair of forward substitution and back substitution sweeps costs $5n-4$. Hence $r$ right-hand sides cost $3(n-1)+r(5n-4)$ arithmetic operations. This is the banded counterpart of Reusing LU factors for multiple right-hand sides.

For floating-point arithmetic with precision $p$ in radix $\beta$ and rounding to nearest, unit roundoff is the half-gap scale $u={\beta }^{1-p}/2$. If a nonzero exact real number $z$ lies in the normal finite range, its nearest rounded value satisfiesIndeed, the absolute distance to the nearest value is at most ${\Delta }_e/2$, and $|z|\ge {\beta }^e$ gives the bound. For a correctly rounded addition, subtraction, multiplication or division, apply this estimate to the exact result of that one operation on the stored operands. The bound does not include earlier roundoff error or automatically bound a whole algorithm. Results outside the finite range and tiny subnormal numbers require separate treatment. Rounding in a directed mode also changes the bound.^[ref]