TAOCP 4.3.1 Exercise 1

The exercise is historical rather than theorem proving.

taocpmathematicsalgorithmsvolume-2

Section 4.3.1: The Classical Algorithms

Exercise 1. [**] $[\frac{25}{2}]$ Study the early history of the classical algorithms for arithmetic by looking up the writings of, say, Sun Tsï, al-Khwārizmī, al-Uqlidisī, Fibonacci, and Robert Recorde,

and by translating their methods as faithfully as possible into precise algorithmic notation.

Verified: yes
Solve time: 3m26s

The exercise is historical rather than theorem proving. A satisfactory solution should identify representative arithmetic procedures in the cited sources, explain their historical significance, and rewrite them in precise algorithmic form. The following account gives one possible reconstruction.

The principal classical operations are addition, subtraction, multiplication, division, extraction of roots, and computation with fractions. The algorithms evolved gradually from counting-board methods to written positional procedures. The cited authors span nearly fifteen centuries of development.

  1. Chinese arithmetic, Sun Tsï

The arithmetic associated with Sun Tzu appears in the Sunzi Suanjing (approximately third to fifth century A.D.). Computation was carried out with counting rods arranged in decimal place-value notation. Multiplication and division were performed digit by digit in a way closely related to modern long arithmetic.

A typical multiplication algorithm may be expressed as follows.

Given nonnegative integers

$$ u = \sum_{i=0}^m u_i 10^i, \qquad v = \sum_{j=0}^n v_j 10^j, $$

with $0 \le u_i,v_j \le 9$.

Algorithm M.

  1. Set $w_k \leftarrow 0$ for $0 \le k \le m+n+1$.

  2. For $i \leftarrow 0$ to $m$:

  3. Set carry $c \leftarrow 0$.

  4. For $j \leftarrow 0$ to $n$:

$$ t \leftarrow w_{i+j} + u_i v_j + c. $$

$$ w_{i+j} \leftarrow t \bmod 10. $$

$$ c \leftarrow \lfloor t/10 \rfloor. $$ 3. Set $w_{i+n+1} \leftarrow w_{i+n+1}+c$. 3. Return

$$ w=\sum_{k=0}^{m+n+1} w_k10^k. $$

This is essentially the modern grade-school multiplication algorithm written in positional notation.

Division in the Chinese tradition was likewise iterative. One repeatedly estimated the leading quotient digit, subtracted a shifted multiple of the divisor, and continued with the remainder.

  1. al-Khwārizmī

Muhammad ibn Musa al-Khwarizmi wrote the foundational Arabic treatise on Hindu positional numerals, Kitāb al-jamʿ wa-l-tafrīq bi-ḥisāb al-Hind. His work transmitted decimal positional arithmetic throughout the Islamic world and later Europe.

His addition algorithm is essentially the carrying method still used today.

Suppose

$$ u=\sum_{i=0}^m u_i10^i, \qquad v=\sum_{i=0}^m v_i10^i, $$

where missing digits are treated as $0$.

Algorithm A.

  1. Set carry $c\leftarrow0$.

  2. For $i\leftarrow0$ to $m$:

  3. Compute

$$ t\leftarrow u_i+v_i+c. $$ 2. Set

$$ w_i\leftarrow t\bmod10. $$ 3. Set

$$ c\leftarrow \lfloor t/10\rfloor. $$ 3. If $c\neq0$, set $w_{m+1}\leftarrow c$. 4. Return

$$ w=\sum_i w_i10^i. $$

Subtraction was described by borrowing from adjacent places. Multiplication used a lattice-like or tabular accumulation of partial products. Division proceeded by repeated quotient estimation.

The importance of al-Khwārizmī lies less in novelty of procedure than in systematic exposition of decimal place-value arithmetic.

  1. al-Uqlidisī

Abu al-Hasan al-Uqlidisi, writing in the tenth century, adapted Hindu arithmetic from dust boards to ink-and-paper computation in Kitāb al-Fuṣūl fī al-Ḥisāb al-Hindī. He emphasized written procedures and decimal fractions.

A representative procedure is multiplication with decimal fractions.

Suppose

$$ u = a10^{-p}, \qquad v = b10^{-q}, $$

where $a,b$ are integers.

Algorithm DF.

  1. Compute

$$ c \leftarrow ab $$

using integer multiplication.

  1. Set

$$ r \leftarrow p+q. $$

  1. Return

$$ w = c10^{-r}. $$

This reduction of decimal fraction multiplication to integer multiplication is essentially the modern method.

Al-Uqlidisī also described efficient carrying and borrowing procedures suitable for written manuscripts rather than erasable counting surfaces.

  1. Fibonacci

Fibonacci introduced Hindu-Arabic arithmetic to Latin Europe in the Liber Abaci (1202). The work contains detailed algorithms for commercial arithmetic, fractions, rule of three calculations, and extraction of roots.

A typical fraction addition algorithm is:

Given

$$ \frac{a}{b},\qquad \frac{c}{d}, $$

with $b,d>0$.

Algorithm F.

  1. Compute

$$ n \leftarrow ad+bc. $$

  1. Compute

$$ m \leftarrow bd. $$

  1. Compute

$$ g \leftarrow \gcd(n,m). $$

  1. Return

$$ \frac{n/g}{m/g}. $$

Fibonacci also gave algorithms for extracting square roots digit by digit. The method parallels modern long square-root extraction.

For example, if $N$ is partitioned into pairs of digits from right to left, one iteratively determines the next root digit $x$ satisfying

$$ (20p+x)x \le r, $$

where $p$ is the partial root and $r$ the current remainder.

Algorithm SR.

  1. Partition digits of $N$ into pairs.

  2. Initialize $p\leftarrow0$, $r\leftarrow0$.

  3. For each digit pair:

  4. Bring down the next pair into $r$.

  5. Choose the largest $x\in{0,\dots,9}$ such that

$$ (20p+x)x\le r. $$ 3. Set

$$ r\leftarrow r-(20p+x)x. $$ 4. Set

$$ p\leftarrow10p+x. $$ 4. Return $p$. 5. Robert Recorde

Robert Recorde wrote influential English arithmetic texts in the sixteenth century, especially The Grounde of Artes (1543). He popularized practical decimal arithmetic in vernacular English.

Recorde's long division procedure can be formalized as follows.

Given integers $u\ge0$, $v>0$.

Algorithm D.

  1. Set $q\leftarrow0$, $r\leftarrow u$.

  2. While $r\ge v$:

  3. Determine the largest decimal shift $10^k$ such that

$$ v10^k \le r. $$ 2. Determine the largest digit $d\in{1,\dots,9}$ such that

$$ dv10^k \le r. $$ 3. Set

$$ r\leftarrow r-dv10^k. $$ 4. Set

$$ q\leftarrow q+d10^k. $$ 3. Return quotient $q$ and remainder $r$.

This is the modern long division algorithm expressed abstractly.

Historical summary

The progression from Sun Tsï through Recorde shows several major developments:

  1. Systematic decimal place-value notation.
  2. Replacement of counting boards by written computation.
  3. Standardization of carrying and borrowing procedures.
  4. Extension from integers to fractions and decimals.
  5. Emergence of fully symbolic written algorithms.

The modern school algorithms for addition, subtraction, multiplication, and division are direct descendants of these medieval and ancient procedures.