Chinese Mathematics: Counting Rods, Nine Chapters, Fangcheng, Horner

Chinese mathematics was decimal place value arithmetic done with bamboo counting rods (算筹 suanchou) on a board. Its central classic, the Nine Chapters on the Mathematical Art (九章算術 Jiuzhang Suanshu), solved linear systems by column elimination, used red and black rods for positive and negative numbers, and extracted roots digit by digit, the procedure Europe later called Horner's method.

This post works through that tradition the way it was done, on a text version of the counting board, with every number checked in Python. It uses the same problem set as the other posts in our mathematics traditions series, so you can compare methods: 98 × 97, 47 × 53, 386 × 524, 85², √7,744, 7,429 ÷ 37, 1/19 as a decimal, and a three by three linear system.

Dates for early Chinese texts are often disputed; where they are, we give the range. The main sources are Joseph Needham's Science and Civilisation in China, volume 3 (Cambridge, 1959), the Shen Kangshen, John N. Crossley and Anthony W.-C. Lun translation and commentary The Nine Chapters on the Mathematical Art (Oxford University Press and Science Press, 1999), the MacTutor History of Mathematics archive at the University of St Andrews, and the papers each of those cites.

Key takeaways

• Counting rods gave China decimal place value from at least the Warring States period, with units upright, tens crosswise and an empty space for zero.
• The Nine Chapters is a problem book, not a proof book. Its 246 problems come with answers and procedures; Liu Hui's commentary of 263 CE added justifications.
• Fangcheng (方程) is Gaussian elimination in substance, worked on columns rather than rows and kept in whole numbers by cross multiplication. The same chapter states rules for adding and subtracting negative numbers.
• Sunzi's remainder problem has the answer 23, and Qin Jiushao's dayan method of 1247 gives a general algorithm for the inverses it needs.
• Root extraction on the counting board is the Ruffini and Horner method, centuries earlier. It turns √7,744 into two quick digit steps: 80, then 8.
• Zu Chongzhi's 355/113 is within 0.000000267 of π, and no fraction with a smaller denominator than 16,604 does better.
• The modern link is real but narrow. The Chinese remainder theorem is how RSA private key operations are sped up in practice, as written into the PKCS #1 standard (RFC 8017).

A dated timeline, with the disputes marked

How did counting rods work?

Counting rods were short sticks of bamboo, bone or wood. The Book of Han (completed in the early second century CE) describes a set of 271 rods, each one fen across and six cun long, carried as a hexagonal bundle. A calculator laid them out on a table or board, moved them as the work went on, and swept them away at the end, so what survives are instructions for moving rods, not the boards themselves.

Two forms for every digit

Each digit from 1 to 9 had two forms. In the upright form (縱 zong), one to five rods stood side by side, and six to nine used one crosswise rod on top worth five plus upright rods for the rest. In the crosswise form (橫 heng), the roles swapped: one to five rods lay flat, and six to nine used an upright rod worth five above flat rods.

digit   upright form (units, hundreds)      crosswise form (tens, thousands)
  1     1 upright rod                       1 flat rod
  2     2 upright rods                      2 flat rods
  3     3 upright rods                      3 flat rods
  4     4 upright rods                      4 flat rods
  5     5 upright rods                      5 flat rods
  6     flat rod (=5) over 1 upright        upright rod (=5) over 1 flat
  7     flat rod (=5) over 2 upright        upright rod (=5) over 2 flat
  8     flat rod (=5) over 3 upright        upright rod (=5) over 3 flat
  9     flat rod (=5) over 4 upright        upright rod (=5) over 4 flat

The Sunzi Suanjing gives the rule: units upright, tens crosswise (一從十橫), alternating from there. The alternation is the clever part. Two upright rods for 2 next to three upright rods for 3 would blur into five rods; alternate the forms and every column stands apart, which also makes an empty column, a zero, easy to see.

Here is 7,744 in rods, drawn approximately in plain text:

  thousands     hundreds      tens        units
  crosswise     upright       crosswise   upright
     |           _____         ____
   _____         |   |         ____       | | | |
   _____         |   |         ____       | | | |
                               ____
     7              7             4          4

The thousands 7 is an upright five rod over two flat rods. The hundreds 7 is a flat five rod over two upright rods. The tens 4 is four flat rods, and the units 4 is four upright rods.

Zero was a gap, and later a circle

For most of its history, rod numeration had no symbol for zero. The board left the column empty. MacTutor's article on Chinese numerals shows 60,390 with blank columns, readable because the alternating forms show that a gap is a real gap. In written texts a small circle for zero appears in the thirteenth century; MacTutor notes that Qin Jiushao's 1247 treatise uses one. Whether the circle came from Indian numerals or arose in China is debated.

Red, black and negative numbers

Chapter 8 of the Nine Chapters needs negative numbers, and the text gives the rules for them (正負術 zhengfu shu, the positive and negative method). Liu Hui's commentary explains that positive quantities were shown with red rods and negative ones with black rods. In later written texts a negative number was often marked with a slanting stroke across its last digit. The addition and subtraction rules read, in modern words:

• To subtract, take away numbers of the same sign and add numbers of opposite sign.
• Taking a positive number from nothing gives a negative; taking a negative from nothing gives a positive.
• To add, the reverse: add numbers of the same sign and take away numbers of opposite sign.

We use these rules below when we solve the problem set system, which has two negative entries.

The oldest decimal times table

In January 2014 Nature reported that Warring States bamboo slips held by Tsinghua University contain a decimal multiplication matrix about 2,300 years old, the oldest decimal times table known. It fits the picture from the rod texts: by the late first millennium BCE, Chinese calculators worked in base ten with place value.

Working the problem set on a counting board

The Sunzi Suanjing describes multiplication with three rows on the board. The multiplier goes in the upper row. The multiplicand goes in the lower row, shifted left so that its units digit sits under the leading digit of the upper row. The product builds up in the middle row. You multiply the leading upper digit by each lower digit from left to right, adding each product into the middle row at the right place. Then you remove that upper digit, slide the lower row one place to the right, and carry on with the next upper digit.

98 × 97

place:        1000   100    10     1
Start
  upper                      9      8
  middle
  lower               9      7            (97 shifted one place left)

Upper 9 (tens) times lower 9 (tens) = 81 hundreds
  middle         8    1      0      0     = 8,100
Upper 9 times lower 7 (units) = 63 tens
  middle         8    7      3      0     = 8,730
Remove the upper 9, slide the lower row one place right
  upper                             8
  lower                      9      7
Upper 8 (units) times lower 9 (tens) = 72 tens
  middle         9    4      5      0     = 9,450
Upper 8 times lower 7 (units) = 56
  middle         9    5      0      6     = 9,506

Four single digit products, four additions, answer 9,506. The rod method ignores the fact that 98 and 97 sit just below 100, which the Vedic Nikhilam shortcut exploits. It treats every multiplication the same way, which is its strength and its cost.

47 × 53

step  upper digit  lower digit  product  added at    middle row
 1    4 (tens)     5 (tens)       20     hundreds     2,000
 2    4 (tens)     3 (units)      12     tens         2,120
 3    7 (units)    5 (tens)       35     tens         2,470
 4    7 (units)    3 (units)      21     units        2,491

The answer is 2,491. Someone who noticed that 47 and 53 sit either side of 50 could use 50² minus 3², or 2,500 minus 9, but the board algorithm itself does not look for such patterns.

386 × 524, step by step

This is the full Sunzi layout for a three digit by three digit product. The lower row starts shifted two places left, so the 4 of 524 sits under the 3 of 386.

place:       10^5  10^4  10^3  10^2  10^1  10^0
Start
  upper                          3     8     6
  middle
  lower                5     2     4

step  upper  lower  product  place of product   middle row after
 1      3      5      15     ten thousands        150,000
 2      3      2       6     thousands            156,000
 3      3      4      12     hundreds             157,200
        remove 3, slide the lower row one place right
 4      8      5      40     thousands            197,200
 5      8      2      16     hundreds             198,800
 6      8      4      32     tens                 199,120
        remove 8, slide the lower row one place right
 7      6      5      30     hundreds             202,120
 8      6      2      12     tens                 202,240
 9      6      4      24     units                202,264

End
  upper                                       (empty)
  middle        2     0     2     2     6     4      = 202,264
  lower                            5     2     4

Nine products and nine additions give 202,264. Long multiplication does the same nine products but writes three partial rows (157,200, 41,920 and 3,144) and adds them at the end. The board folds the adding into each step: less writing, but an early slip hides inside the running total, so careful calculators checked by dividing back.

85²

Squaring on the board is just multiplication with the same number above and below.

step  upper      lower      product        middle row
 1    8 (tens)   8 (tens)   64 hundreds      6,400
 2    8 (tens)   5 (units)  40 tens          6,800
 3    5 (units)  8 (tens)   40 tens          7,200
 4    5 (units)  5 (units)  25               7,225

The answer is 7,225. Steps 2 and 3 are the same product, and that doubled middle term is exactly what the square root procedure undoes. We run it backwards for 7,744 further down.

7,429 ÷ 37

Division uses three rows too: the quotient (商 shang) on top, the dividend (實 shi, "the substance") in the middle, and the divisor (法 fa, "the method") at the bottom. The divisor is moved left until it sits under the part of the dividend it can go into, then the calculator finds the largest digit that fits, writes it in the quotient row, and subtracts.

Start
  shang (quotient)
  shi   (dividend)       7    4    2    9
  fa    (divisor)        3    7               (moved two places left: 3,700)

37 goes into 74 twice. Put 2 in the hundreds place of the quotient.
Subtract 2 x 3,700 = 7,400 from the dividend.
  shang                            2
  shi                                   2    9   = 29
  fa                          3    7             (moved right: 370)

370 does not go into 29. Put 0 in the tens place. Move fa right again.
  shang                            2    0
  shi                                   2    9
  fa                                    3    7   (37)

37 does not go into 29. Put 0 in the units place. Stop.
  shang                            2    0    0   = 200
  shi                                   2    9   = remainder 29
  fa                                    3    7

The quotient is 200 and the remainder is 29. The Nine Chapters would write the answer as 200 and 29 parts of 37 (三十七分之二十九), with the remainder left in the shi row as the numerator and the divisor in the fa row as the denominator. That is why classical texts call a numerator the shi and a denominator the fa.

1/19 as a decimal

Classical texts would normally leave this as a fraction, "one part of nineteen". Decimal parts did appear: Liu Hui says that when a square root is not exact you continue into "fine numbers" (微數), and Song dynasty authors named decimal places after small units of length and weight. So the board method below, the division procedure continued past the units place, is historically fair. Each step multiplies the remainder by 10, finds how many 19s fit, and keeps the new remainder.

step  remainder  x10   digit  new remainder
  1       1       10     0        10
  2      10      100     5         5
  3       5       50     2        12
  4      12      120     6         6
  5       6       60     3         3
  6       3       30     1        11
  7      11      110     5        15
  8      15      150     7        17
  9      17      170     8        18
 10      18      180     9         9
 11       9       90     4        14
 12      14      140     7         7
 13       7       70     3        13
 14      13      130     6        16
 15      16      160     8         8
 16       8       80     4         4
 17       4       40     2         2
 18       2       20     1         1   <- back to the start

At step 18 the remainder returns to 1, so the digits repeat from there:

1/19 = 0.052631578947368421, then the same 18 digits again forever.

The period cannot be longer than 18, because dividing by 19 leaves only 18 possible nonzero remainders. All 18 appear here, so the period is the full 18. Vedic methods produce the same digits from the other end, by repeated doubling.

What is in the Nine Chapters?

The Nine Chapters on the Mathematical Art is a collection of 246 problems, each with an answer and a procedure (術 shu). It is practical in tone: fields, grain, taxes, canals, walls and wages. MacTutor's summary of the chapters is a good starting point, and the Shen, Crossley and Lun translation gives the full text with Liu Hui's commentary.

When was it written?

Nobody knows exactly. Liu Hui, writing in 263 CE, says that after the burning of books under the first Qin emperor, Zhang Cang (around 170 BCE) and later Geng Shouchang reconstructed the text from damaged originals. Most historians see a text compiled over centuries, reaching its final form between the first century BCE and the first century CE. One dating tool, MacTutor notes, is the units of measure in the problems, which changed with each dynasty. The 1980s discovery of the Suan shu shu, an older bamboo strip text with problems of the same kinds, supports the view that the Nine Chapters drew on material that was already in circulation in the early Han.

The commentators

Liu Hui's commentary of 263 CE justifies the procedures, often by dissection, and adds his own results: the polygon method for π, the volume of a pyramid, and a critique of the text's sphere rule. Li Chunfeng's team added notes in the seventh century. When people quote "the Nine Chapters", they usually quote this layered text.

How does fangcheng work?

Fangcheng (方程), usually read as "rectangular arrays", is the name of chapter 8 and its method. The coefficients of a linear system go on the board in a grid, one column per equation, the first equation on the right, with the total (the shi) at the bottom.

Elimination multiplies a whole column by a number and then subtracts another column from it repeatedly, a step called direct subtraction (直除 zhichu), until the top entry is empty. Instead of dividing to make a leading 1, which creates fractions, the method multiplies the target column by the leading entry of the other column, so everything stays in whole numbers until the last step.

Problem 8.1: three grades of grain

The first problem of chapter 8 reads, in paraphrase: three bundles of top grade grain, two of medium and one of low grade yield 39 dou. Two of top, three of medium and one of low yield 34 dou. One of top, two of medium and three of low yield 26 dou. How much does one bundle of each grade yield?

In modern notation, with x, y and z for the three grades:

3x + 2y +  z = 39
2x + 3y +  z = 34
 x + 2y + 3z = 26

The board at the start. The first equation goes in the right column.

Step 1. Multiply the whole middle column by 3, the top entry of the right column. The middle becomes 6, 9, 3, 102. Subtract the right column from it twice. The top entry falls from 6 to 3 to empty.

Check the middle column: 9 minus 2 × 2 is 5; 3 minus 2 × 1 is 1; 102 minus 2 × 39 is 24.

Step 2. Multiply the whole left column by 3. It becomes 3, 6, 9, 78. Subtract the right column once.

Step 3. Now clear the y entry of the left column using the middle column. Multiply the left column by 5, the y entry of the middle column. It becomes 20, 40, 195. Subtract the middle column four times: 20 minus 4 × 5 is 0; 40 minus 4 × 1 is 36; 195 minus 4 × 24 is 99.

The board is now triangular. The left column says 36 bundles of low grade grain yield 99 dou.

Back substitution, the Nine Chapters way

A modern student would now divide: z equals 99/36. The Nine Chapters avoids fractions for one more round. It keeps 36 as a common divisor, the fa, and works out each unknown's shi as a multiple of it.

The middle unknown. Multiply the middle column's shi by the fa, then take away the z term using the left column's shi: 24 × 36 is 864; 864 minus 1 × 99 is 765. Divide by the middle column's y entry, 5. That gives 153, the shi for y.

The right unknown. Multiply the right column's shi by the fa and take away the other two terms: 39 × 36 is 1,404; minus 2 × 153 (306); minus 1 × 99. That leaves 999. Divide by the x entry, 3, to get 333.

Divide everything by the fa.

These are the answers the text gives. Substituting back checks them: 3 × 9.25 + 2 × 4.25 + 2.75 is 39; 2 × 9.25 + 3 × 4.25 + 2.75 is 34; 9.25 + 2 × 4.25 + 3 × 2.75 is 26.

The problem set system, with red and black rods

The series problem set uses this system:

x + y + z  =  6
    2y + 5z = -4
2x + 5y - z = 27

It has two negative entries, so on the board they would be black rods. In the tables below a minus sign marks a black rod value; everything else is red.

The board at the start.

The middle column already has an empty top, so it needs no work in the first round.

Step 1: clear x from the left column. Multiply the left column by the right column's top entry, 1, which changes nothing. Subtract the right column twice.

left column            x     y     z    shi
at start               2     5    -1     27
minus right once       1     4    -2     21
minus right twice      .     3    -3     15

In the z row, taking a red 1 from a black 1 subtracts numbers of opposite sign, so the sizes add and the result stays black: black 2, then black 3.

Step 2: clear y from the left column. Multiply the left column by 2, the y entry of the middle column. It becomes 6, -6, 30. Subtract the middle column three times.

left column                  y      z    shi
after multiplying by 2       6     -6     30
minus middle once            4    -11     34
minus middle twice           2    -16     38
minus middle three times     .    -21     42

The same rule gives black 6 minus red 5 as black 11, and red 30 minus black 4 as red 34.

The triangular board.

The left column says black 21 times z gives red 42, so the fa is -21 and z is 42 ÷ -21, which is -2.

Back substitution with the common divisor -21.

• Middle: -4 × -21 is 84; take away 5 × 42 (210) to get -126; divide by 2 to get -63.
• Right: 6 × -21 is -126; take away 1 × -63 and 1 × 42, which gives -126 plus 63 minus 42, or -105; divide by 1 to get -105.

So x is 5, y is 3 and z is -2. Check: 5 + 3 minus 2 is 6; 2 × 3 + 5 × -2 is -4; 2 × 5 + 5 × 3 + 2 is 27.

One caution: the Nine Chapters states sign rules for addition and subtraction only. Dividing by a negative fa is our modern reading; explicit rules for multiplying signed numbers are usually credited to later texts such as Zhu Shijie's 1299 Introduction to Mathematical Studies (算學啟蒙). A Han calculator would more likely have arranged the work so the fa came out positive.

Is fangcheng really Gaussian elimination?

In substance, yes. MacTutor says the method uses "elementary column operations as is done today in the method of Gaussian elimination". The differences are bookkeeping: columns for rows, cross multiplication for division, a common divisor kept to the end. Gauss used elimination for least squares work in astronomy in the early nineteenth century, and his name was attached to it much later. Roger Hart's The Chinese Roots of Linear Algebra (2011) argues the board practice went further, toward determinant like patterns; treat that as one scholar's argument rather than consensus.

Excess and deficit: double false position

Chapter 7, 盈不足 yingbuzu, solves problems by making two guesses and using the two errors. The first problem is a group purchase. If each person pays 8, there are 3 too many; if each pays 7, there are 4 too few. How many people are there, and what does the item cost?

The board lays the two rates and two errors crosswise:

           guess A    guess B
rate          8          7
error     excess 3   deficit 4

The procedure is to multiply crosswise and add (because one error is an excess and the other a deficit), then divide by the difference of the rates.

Check: 7 people at 8 each is 56, which is 3 more than 53. At 7 each it is 49, which is 4 less than 53.

The method is exact when the error grows in a straight line with the guess, and an approximation otherwise. Chapter 7 has a case that looks nonlinear. Two rats burrow through a wall 5 chi thick from opposite sides. The big rat digs 1 chi on the first day and doubles each day; the small rat digs 1 chi on the first day and halves each day. When do they meet?

• Guess 2 days: the big rat has dug 1 + 2 = 3 chi, the small rat 1 + 1/2 = 1.5 chi. Total 4.5, a deficit of 0.5.
• Guess 3 days: the big rat has dug 1 + 2 + 4 = 7, the small rat 1 + 1/2 + 1/4 = 1.75. Total 8.75, an excess of 3.75.
• Excess and deficit rule: (2 × 3.75 + 3 × 0.5) ÷ (3.75 + 0.5) = 9 ÷ 4.25 = 36/17, which is 2 and 2/17 days.

That is the text's answer, and it is exact: during the third day both rats dig at a steady rate (4 chi and 1/4 chi a day), so the error is linear between the guesses. The big rat has dug 3 and 8/17 chi and the small rat 1 and 9/17, which add to 5.

Gougu: the right triangle chapter

In Chinese terms the short leg of a right triangle is the gou (勾), the long leg the gu (股) and the hypotenuse the xian (弦). Chapter 9 opens with the 3, 4, 5 triangle and then moves to problems that need some algebra.

The reed in the pond. A square pond is 10 chi on a side. A reed grows at its centre and sticks 1 chi above the water. Pulled to the middle of one edge, its tip just reaches the surface. How deep is the water, and how long is the reed?

Let the depth be d. The reed, d + 1 long, leans over half the width, 5 chi, so d² + 5² = (d + 1)². That gives 25 = 2d + 1: the water is 12 chi deep and the reed 13 chi. The text's rule is the same: square the half width, take away the square of the height above water, divide by twice that height, (25 minus 1) ÷ 2 = 12.

The broken bamboo. A bamboo 10 chi tall breaks, and its top touches the ground 3 chi from the base. How high is the break? If the break is at height h, the fallen part is 10 minus h long and is the hypotenuse of a right triangle with legs h and 3. So h² + 9 = (10 minus h)², which gives 20h = 91 and h = 91/20, or 4 and 11/20 chi.

How Liu Hui justified it. The Nine Chapters states the gougu rule without proof. Liu Hui's commentary justifies it with the out and in complementary principle (出入相補 churu xiangbu): cut the squares on the two legs into pieces, move the pieces, and they fill the square on the hypotenuse exactly. Donald Wagner's 1985 paper in Historia Mathematica reconstructs Liu Hui's dissection.

Liu Hui's polygons and the value of π

The Nine Chapters uses π = 3 in its circle rules. Liu Hui knew this was too small, because the perimeter of a hexagon inscribed in a circle is exactly three diameters and the circle is longer than the hexagon. So he set out to do better by doubling the number of sides.

His key fact is simple. If you know the side of an inscribed polygon with n sides, the area of the polygon with 2n sides is n × (radius) × (side) ÷ 2. You get the area of the doubled polygon from the side of the one you already have. He took a circle of radius 1 chi, which is 10 cun, and worked in cun.

polygon      area for radius 10    area / 100
 12 sides         300.000            3.00000
 24 sides         310.583            3.10583
 48 sides         313.263            3.13263
 96 sides         313.935            3.13935
192 sides         314.103            3.14103

These are the exact values from Python. Liu Hui truncated his square roots as he went, so his own figures are slightly smaller: 313 and 584/625 square cun for the 96 sided polygon (313.9344) and 314 and 64/625 for the 192 sided one (314.1024).

He then bounded the circle from both sides. Its area is more than the 192 sided polygon, and less than that polygon plus the difference between the 192 and 96 sided ones, because the circle fits inside the rectangles built on the small triangles added at the last doubling. With his numbers:

• Lower bound: 314 and 64/625, or 314.1024.
• Upper bound: 314.1024 + (314.1024 minus 313.9344) = 314.2704.

Dividing by 100 gives π between 3.141024 and 3.142704. Liu Hui then recommended the practical value 157/50, which is 3.14, and said himself that it was slightly small.

A further passage in the commentary, using polygons with many more sides, gives 3,927/1,250, exactly 3.1416. Who wrote it is disputed: some historians credit Liu Hui, others think it was added later, possibly from Zu Chongzhi's work. Treat 3.1416 as belonging to the commentary tradition rather than certainly to Liu Hui.

Zu Chongzhi and 355/113

Zu Chongzhi (429 to 500 CE) was an astronomer and engineer of the Southern dynasties. His mathematical book, the Zhui shu (綴術), was included in the Ten Mathematical Classics in 656 and was later lost. What we know of his π work comes from the official history of the Sui dynasty, which reports that he showed π to lie between 3.1415926 and 3.1415927, and gave two fractions: an approximate ratio (約率 yuelü) of 22/7 and a close ratio (密率 milü) of 355/113.

How good is 355/113?

355/113 is correct to six decimal places. The continued fraction of π begins 3, 7, 15, 1, 292, and 355/113 is the convergent just before that large 292, which is why it is so good for its size. A brute force check in Python confirms that no fraction with a denominator below 16,604 is closer; the next better one is 52,163/16,604.

We do not know Zu's method, because the book is gone. A Python check shows that Liu Hui's inequality applied to a 24,576 sided polygon is enough to pin π between 3.1415926 and 3.1415927, while 12,288 sides falls just short, so polygon doubling of that depth is a plausible reconstruction, not a documented one. In Europe the fraction appears only in the late sixteenth century, usually credited to Adriaan Anthonisz; Yoshio Mikami used that gap in 1913 to argue it should be called Zu's ratio.

Sunzi's remainder problem

The Sunzi Suanjing contains the most famous problem in Chinese mathematics. In translation: there are things whose number is unknown. Counted by threes, 2 are left over; counted by fives, 3 are left over; counted by sevens, 2 are left over. How many things are there? The answer given is 23.

The text's method uses three numbers to remember: 70, 21 and 15.

• 70 leaves 1 when divided by 3, and divides evenly by 5 and 7.
• 21 leaves 1 when divided by 5, and divides evenly by 3 and 7.
• 15 leaves 1 when divided by 7, and divides evenly by 3 and 5.

So 70 × 2 handles the threes, 21 × 3 the fives and 15 × 2 the sevens:

Check: 23 = 7 × 3 + 2, 23 = 4 × 5 + 3, 23 = 3 × 7 + 2. Any number that differs from 23 by a multiple of 105 (128, 233, 338 and so on) also fits; 23 is the smallest.

MacTutor calls this the earliest known problem of its type, and notes that the solution, though for a special case, is exactly the modern method. Gauss stated and proved the general theorem in his Disquisitiones Arithmeticae of 1801. Indian mathematics developed the related kuttaka method from Āryabhaṭa onwards; A. K. Bag and Shen Kangshen compared the two traditions in 1984.

The hard part is finding numbers like 70, 21 and 15 when the moduli are larger. That needs a procedure, and it arrived in 1247.

Qin Jiushao's dayan method, worked

Qin Jiushao (c. 1202 to 1261) opened his Mathematical Treatise in Nine Sections (數書九章 Shushu Jiuzhang, 1247) with indeterminate problems and a general algorithm, the dayan rule for finding one (大衍求一術 dayan qiuyi shu). Its job is to find, for a number a and a modulus m with no common factor, the multiplier k that makes a × k leave remainder 1 when divided by m. In modern terms, k is the inverse of a modulo m.

The board layout

Qin uses four positions:

upper left  = 1  (tianyuan, "the heavenly one")   upper right = a  (the leftover number)
lower left  = 0                                   lower right = m  (the modulus)

Then he alternates two moves until the upper right holds 1:

1. Divide the lower right by the upper right. Replace the lower right with the remainder. Add quotient × upper left into the lower left.
2. Divide the upper right by the lower right. Replace the upper right with the remainder. Add quotient × lower left into the upper left.

One special rule keeps the process ending on a 1 in the upper right: if a division would leave remainder 0 in the upper right, take one less as the quotient, so the remainder equals the divisor instead. When the upper right reaches 1, the upper left is the answer.

A worked example: the inverse of 18 modulo 25

move  upper left  upper right  lower left  lower right  working
start      1          18           0           25
  1        1          18           1            7       25 = 1 x 18 + 7;  lower left 0 + 1 x 1
  2        3           4           1            7       18 = 2 x 7 + 4;   upper left 1 + 2 x 1
  3        3           4           4            3        7 = 1 x 4 + 3;   lower left 1 + 1 x 3
  4        7           1           4            3        4 = 1 x 3 + 1;   upper left 3 + 1 x 4

The upper right is 1, so the answer is 7. Check: 18 × 7 is 126, which is 5 × 25 + 1.

The special rule in action: the inverse of 12 modulo 13

move  upper left  upper right  lower left  lower right  working
start      1          12           0           13
  1        1          12           1            1       13 = 1 x 12 + 1;  lower left 0 + 1 x 1
  2       12           1           1            1       12 / 1 would leave 0, so take 11, remainder 1;
                                                        upper left 1 + 11 x 1

The answer is 12. Check: 12 × 12 is 144, which is 11 × 13 + 1. Without the special rule the upper right would have become 0 and the procedure would have lost the answer.

The dayan rule is the extended Euclidean algorithm, arranged for a counting board and tracking only the coefficient that is needed.

Putting it together: a three modulus problem

Find the smallest positive number that leaves 2 when divided by 7, 3 when divided by 11 and 4 when divided by 13. The product of the moduli is 1,001.

modulus  1,001 / modulus  reduced by modulus      dayan inverse     basis number
   7          143         143 = 20 x 7 + 3   -> 3     5 (3 x 5 = 15)       143 x 5 = 715
  11           91          91 = 8 x 11 + 3   -> 3     4 (3 x 4 = 12)        91 x 4 = 364
  13           77          77 = 5 x 13 + 12  -> 12   12 (12 x 12 = 144)     77 x 12 = 924

These basis numbers play the role of Sunzi's 70, 21 and 15. Each leaves 1 for its own modulus and 0 for the others.

• 715 × 2 + 364 × 3 + 924 × 4 = 1,430 + 1,092 + 3,696 = 6,218.
• 6,218 minus 6 × 1,001 = 6,218 minus 6,006 = 212.

Check: 212 = 30 × 7 + 2 = 19 × 11 + 3 = 16 × 13 + 4. The answer is 212.

Qin also gave rules for moduli that share factors and applied the method to calendar cycles. Ulrich Libbrecht's Chinese Mathematics in the Thirteenth Century (MIT Press, 1973) is the standard study.

Root extraction: Horner before Horner

Chapter 4 of the Nine Chapters gives a procedure for square roots (開方術 kaifang shu) and cube roots. It is laid out in rows on the board, finds one digit at a time and after each digit updates the rows so that the next digit is a smaller version of the same problem. Jia Xian in the eleventh century turned the update into a simple chain of multiply and add steps (增乘開方法 zengcheng kaifang fa), and Qin Jiushao in 1247 used the same idea on equations of degree three and four. In Europe the method was published by Paolo Ruffini in 1804 and William George Horner in 1819, and it now carries Horner's name.

√7,744 on the board

The rows are the quotient (shang, the root being built), the shi (the number, kept as a negative constant so that zero means done), the fa (the linear coefficient) and the bottom row (the square coefficient, 1 for a square root).

Find the first digit. The number has four digits, so the root has two. The largest tens digit whose square fits under 7,744 is 8, since 80² is 6,400 and 90² is 8,100. Put 8 in the tens place of the quotient.

Update the rows with 80. Each update is "multiply by 80 and add into the row above", run upward and then once more:

row      start     bottom x 80 into fa   fa x 80 into shi            bottom x 80 into fa again
shang                8 (tens)             8                          8
shi      -7,744     -7,744               -7,744 + 6,400 = -1,344    -1,344
fa            0         80                   80                        160
bottom        1          1                    1                          1

The board now holds the reduced problem: find y with y² + 160y = 1,344, where the full root is 80 + y.

Find the second digit. Divide 1,344 by the fa, 160, as a trial: it goes about 8 times. Try 8.

row      before    bottom x 8 into fa    fa x 8 into shi
shang       8          88                   88
shi      -1,344     -1,344               -1,344 + 168 x 8 = 0
fa         160        168                  168
bottom       1          1                    1

The shi is now exactly zero, so the root is exact: √7,744 is 88.

The structure follows the square from earlier. 88² is 80² + 2 × 80 × 8 + 8², or 6,400 + 1,280 + 64. The first update removed the 6,400. The fa of 160 is the 2 × 80. The final step removed 160 × 8 + 8 × 8, which is 1,280 + 64.

The same steps as synthetic division

Here is the same calculation in Python. The function shifts p(x) to p(x + r) using only multiply and add, the same updates the board rows perform.

def shift(coeffs, r):
    """Return the coefficients of p(x + r), highest degree first.
    Repeated synthetic division: only multiply and add."""
    c = list(coeffs)
    n = len(c) - 1
    for i in range(n):
        for j in range(1, n + 1 - i):
            c[j] += c[j - 1] * r
    return c

# x^2 - 7744 = 0
print(shift([1, 0, -7744], 80))   # [1, 160, -1344]  ->  y^2 + 160y - 1344
print(shift([1, 160, -1344], 8))  # [1, 176, 0]      ->  constant 0, so 88 is exact

The printed constant terms, -1,344 and then 0, are the shi row of the board after each digit.

Qin Jiushao's quartic

The method is not limited to square roots. A quartic equation from Qin Jiushao's treatise, often quoted in histories of the method, is:

-x^4 + 763200 x^2 - 40642560000 = 0

Its root is 840. On the board Qin finds it in three digits, 8 hundreds, 4 tens and 0 units, shifting the polynomial after each digit.

stage              coefficients (x^4, x^3, x^2, x, constant)                 reading
start              -1,      0,    763,200,            0, -40,642,560,000
shift by 800       -1, -3,200, -3,076,800,  -826,880,000,  38,205,440,000      constant positive: root above 800
trial digit        38,205,440,000 / 826,880,000 is about 46                   try 4 in the tens place
shift by 40 more   -1, -3,360, -3,470,400, -1,088,640,000,              0      constant zero: 840 is exact

Check by direct substitution: 840⁴ is 497,871,360,000; 763,200 × 840² is 538,513,920,000; and 538,513,920,000 minus 497,871,360,000 minus 40,642,560,000 is 0.

MacTutor's page on Qin gives two more of his equations: 4,608x³ = 3,000,000,000 × 30 × 800, with answer 2,500, and a quartic in the same family. The pattern is the same each time: guess a digit from the leading terms, shift, repeat.

So who gets the credit?

The fair statement is that the digit by digit root method with polynomial shifting was standard in Chinese mathematics from at least the eleventh century, was applied to cubic and quartic equations by 1247, and was published independently in Europe by Ruffini (1804) and Horner (1819). MacTutor's Horner biography says as much, and notes that the method had been considered by Zhu Shijie in China centuries earlier. "Horner's method" is a convenient name, not a claim of priority.

The Yang Hui triangle

Yang Hui's 1261 Detailed Analysis of the Mathematical Rules in the Nine Chapters prints a triangle of numbers and says it comes from Jia Xian, about two centuries earlier. Zhu Shijie's 1303 Jade Mirror of the Four Unknowns extends it to the eighth power. In Europe it is called Pascal's triangle, after Blaise Pascal's treatise of the 1650s; in China it is the Yang Hui triangle, and some writers say Jia Xian triangle.

row 0                 1
row 1               1   1
row 2             1   2   1
row 3           1   3   3   1
row 4         1   4   6   4   1
row 5       1   5  10  10   5   1
row 6     1   6  15  20  15   6   1
row 7   1   7  21  35  35  21   7   1
row 8 1   8  28  56  70  56  28   8   1

Each number is the sum of the two above it. Row n gives the coefficients of (a + b) to the nth power. Jia Xian's use for it was root extraction: row 2 (1, 2, 1) says (80 + 8)² is 1 × 80² + 2 × 80 × 8 + 1 × 8², which is exactly how the √7,744 board was organised. Row 3 drives cube roots and row 4 fourth roots. The Chinese name for the diagram, 開方作法本源 (the source of the method of root extraction), says what it was for.

The suanpan: the Chinese abacus

The suanpan (算盤) is a frame with rods, a crossbar, two beads above the bar and five below. Each upper bead is worth 5 and each lower bead 1. A digit is shown by pushing beads toward the bar.

Here is 7,429 on four rods, counting the beads pushed against the bar:

                         thousands  hundreds  tens  units
upper beads at the bar        1         0       0      1     (worth 5 each)
lower beads at the bar        2         4       2      4     (worth 1 each)
digit                         7         4       2      9

Seven is one upper bead and two lower beads; nine is one upper and four lower. The other beads rest away from the bar.

Why two and five?

A rod can show up to 2 × 5 + 5 × 1, which is 15. A common explanation is that this suited the jin, a weight divided into 16 liang. In decimal work the spare beads serve as temporary carries. The Japanese soroban later dropped to one bead above and four below, the minimum for decimal work.

When did it appear?

The dating is disputed. A late Han text attributed to Xu Yue (around 190 CE), the Shushu Jiyi, mentions calculation with beads (珠算 zhusuan), but whether that means the later framed abacus is debated. By the Ming dynasty the suanpan was in wide use, and Cheng Dawei's Suanfa Tongzong of 1592 became the standard manual, with verse rules for division that operators memorised. In 2013 UNESCO inscribed Chinese zhusuan, the knowledge and practice of calculation with the abacus, on its Representative List of the Intangible Cultural Heritage of Humanity.

From Sunzi to RSA: the remainder theorem today

The Chinese remainder theorem is how the most common RSA private key operation is made faster. The idea is Sunzi's: work modulo the factors separately, then recombine.

An RSA modulus n is the product of two large primes p and q. Decrypting or signing raises a number to a large private exponent d modulo n. The key holder can instead compute modulo p and modulo q, each with a smaller exponent, and stitch the two remainders together; with numbers half as long, the work drops to roughly a quarter. The PKCS #1 standard, RFC 8017, builds this into the private key format: a key can carry p, q, dP, dQ and a CRT coefficient qInv, defined by q * qInv == 1 (mod p). That qInv is a dayan inverse.

Here is a toy version with textbook sized numbers, for understanding only. Real keys use primes hundreds of digits long, padding and constant time code; always use a maintained cryptography library.

# Toy RSA with tiny primes, to show the CRT step only. Never use for real keys.
p, q, e = 61, 53, 17
n = p * q                      # 3233
phi = (p - 1) * (q - 1)        # 3120
d = pow(e, -1, phi)            # 2753

# CRT parameters, as in the RFC 8017 private key format
dP = d % (p - 1)               # 53
dQ = d % (q - 1)               # 49
qInv = pow(q, -1, p)           # 38, the "dayan" inverse of q modulo p

m = 65
c = pow(m, e, n)               # 2790

# Decrypt the slow way and the CRT way
slow = pow(c, d, n)
m1 = pow(c, dP, p)             # 4,  the remainder modulo p
m2 = pow(c, dQ, q)             # 12, the remainder modulo q
h = (qInv * (m1 - m2)) % p     # 1
fast = m2 + h * q              # 65

print(slow, fast)              # 65 65

The recombination is Garner's form of the theorem: start from the remainder modulo q and add the right multiple of q to fix the remainder modulo p. Sunzi's 70, 21 and 15 do the same job in a different arrangement.

One defensive point, at concept level: Boneh, DeMillo and Lipton showed in 1997 that a computing fault in one half of a CRT computation can leak information about the key. Maintained libraries guard against this, for example by checking the result before releasing it, which is one more reason never to hand roll RSA.

How the Chinese tradition compares

The series comparison post works all three traditions on the same problems; here is the Chinese summary.

Chinese board mathematics favoured general procedures that work the same way every time over shortcuts that need numbers of a special shape. That is why it reads like a set of algorithms.

What to practise

1. Lay numbers out in rods with matchsticks on squared paper until you can read 60,390, blanks and all, at a glance.
2. Multiply with three rows: 47 × 53, then 386 × 524. Check by dividing back.
3. Divide with shang, shi and fa: 7,429 ÷ 37 as 200 and 29/37, then 1/19 to its full 18 digit cycle.
4. Run fangcheng on problem 8.1 in whole numbers, then the problem set system with two colours of sticks.
5. Extract √7,744 with four rows, then √2 to three decimal places.
6. Work Sunzi's problem, then the dayan inverse of 18 modulo 25 by hand.
7. Read the Shen, Crossley and Lun translation to follow the procedures with Liu Hui's reasons beside them.

Common mistakes

• Giving the Nine Chapters one author and one date. It is a layered text; give a range and say whose words you quote.
• Saying the Chinese had no zero. The board had a working zero, the empty column. Only the written symbol came later.
• Swapping the rod colours. Red was positive and black negative, the reverse of modern accounting.
• Calling 3.1416 Liu Hui's value without qualification. That passage may be later. His own recommendation was 157/50.
• Describing Zu Chongzhi's method as documented. We know his results, not his method.
• Saying Sunzi proved the theorem. Sunzi solved one case; Qin gave the general algorithm; Gauss proved the theorem in 1801.
• Calling the root method "Horner's" without context. Chinese mathematicians used it centuries earlier.
• Building RSA from the toy code. It shows arithmetic only. Use a maintained library.

FAQ

What is Chinese mathematics best known for?

Decimal place value with counting rods, fangcheng elimination for linear systems, early negative numbers, the remainder problem behind the Chinese remainder theorem, root extraction later called Horner's method, and Zu Chongzhi's 355/113 for π.

What are Chinese counting rods?

Small rods of bamboo, bone or wood laid on a board as digits, upright for units and hundreds, crosswise for tens and thousands. An empty column meant zero; red and black rods marked positive and negative.

When was the Nine Chapters on the Mathematical Art written?

It was compiled over centuries and reached roughly its present form between the first century BCE and the first century CE; the exact date is disputed. Liu Hui's commentary is dated 263 CE.

Is fangcheng the same as Gaussian elimination?

In substance, yes: it reduces the array to triangular form by multiplying and subtracting whole columns, then back substitutes. It uses columns, not rows, and avoids fractions until the last step.

What is the answer to Sunzi's remainder problem?

23. It leaves 2 when divided by 3, 3 when divided by 5 and 2 when divided by 7. Sunzi's method adds 70 × 2, 21 × 3 and 15 × 2 to get 233, then subtracts 210.

Did China discover Horner's method first?

The method was in use in China by the eleventh century and applied to quartic equations by Qin Jiushao in 1247. Ruffini (1804) and Horner (1819) published it independently in Europe.

How accurate is Zu Chongzhi's value of π?

355/113 is 3.14159292, about 0.000000267 above π, correct to six decimal places. No fraction with a smaller denominator than 16,604 is closer. He also bounded π between 3.1415926 and 3.1415927.

How is the Chinese abacus different from the Japanese one?

The suanpan usually has two beads above the bar and five below, so a rod can hold up to 15. The Japanese soroban settled on one above and four below, the minimum for decimal work.

Where is the Chinese remainder theorem used today?

In RSA. Private key operations are computed modulo the two prime factors separately and recombined, roughly four times faster. RFC 8017 stores the needed values, including the inverse qInv, in the private key.

What is the best book to read on Chinese mathematics?

The Shen, Crossley and Lun translation of the Nine Chapters (1999) for the text; Needham's volume 3 (1959) for context; Libbrecht (1973) for the thirteenth century. MacTutor is a free starting point.

Where Safeguard fits

Safeguard does not do mathematics; the checks in this post were plain Python. The honest parallel is one of habit. A counting board answer was trusted because every step could be laid out again and checked, just as a fangcheng solution ends by substituting back. Software supply chains need the same property: you should be able to say which components went into a build, where each came from, and whether a known fix exists.

The RSA arithmetic above runs in your systems through open source cryptography and big number libraries, which are dependencies like any other and get security fixes. The section below describes how Safeguard helps teams close the gap between a fix existing and that fix running.

Fix it without waiting for upstream

Whatever the vulnerability, most of the risk sits in two gaps. The first is the time between a fix being published and that fix actually running in your production builds. The second, and worse, is the time before any fix exists at all, while a maintainer works out a patch and a release schedule. Waiting through both gaps is a habit, not a requirement. Safeguard gives teams three ways to close them.

1. Autonomous remediation: pull requests, not tickets

When a fixed version exists, Safeguard's Griffin models open a tested, policy gated pull request that moves the affected dependency to the safe version. You can run it on one repository or in bulk across every project that carries the vulnerable version. Remediation covers eight categories, including dependencies, licenses, security posture and findings. Reachability analysis ranks the vulnerable code paths your application actually calls first, so the first pull requests you merge are the ones that matter most. Autonomous remediation ships switched off, with every category set to Manual, so your team decides how much runs on its own and what still needs a human approval.

2. Gold Open Source: the safe version in seconds, free

gold.safeguard.sh is free and needs no login. Search any CVE or package to see affected and fixed versions, CVSS, EPSS, CISA KEV status and a recommended safe version, or use the "Am I affected?" checker. The same data is available through a free read API, README status badges and RSS threat feeds. The safeguard-sh/gold-scan-action GitHub Action can fail a build on a known exploited vulnerability, on any known vulnerability, or never, so a version you have just removed cannot quietly come back in next week's merge.

3. Gold Registry: start from components that are already fixed

registry.safeguard.sh provides hardened, drop in replacements for upstream packages and container images. Every Gold artifact is held continuously to zero exploitable critical or high CVEs, zero malware and a completed license check, with SLSA L3 or higher provenance, a Sigstore signature and a public evidence page you can hand to an auditor. An artifact loses its Gold badge if it regresses. Teams can point their own package directory at the registry so hardened equivalents resolve without changing how developers install anything.

When upstream has no fix yet, or will not ship one, Safeguard first works to get the fix accepted upstream. If the issue is severe or upstream will not move, Safeguard builds a fork, fixes the vulnerability there and publishes a hardened Gold build, so you are not stuck on a maintainer's release schedule. You can also request a hardened, compatibility tested build of a specific package. This fork and patch flow is in early access today, so ask which packages it covers before you plan around it.

One honest limit: when the vulnerable code lives in a vendor appliance, a hosted service or an operating system runtime you do not build yourself, the fix still has to come from that vendor or distribution. The steps above apply to the open source dependencies and container images you build and ship, which is where most teams carry the largest and least tracked share of their exposure.

See how Safeguard would help

These demos show Safeguard on ordinary software projects; none of them does mathematics.

The first is a real Safeguard CLI session. Asked to fix the lodash CVE in a repository, it reads the finding and advisory, asks before any command that changes something, edits package.json to lodash 4.17.21, runs npm install and npm test with approval, and pushes nothing. The same flow applies when the outdated dependency is a crypto library.

Click through it at your own pace, or open it full screen.

The second sets up the local runner on your own machine, approves it with its device code and scans from the terminal, for teams that want scanning next to the code.

Click through it at your own pace, or open it full screen.

The third connects Claude to the Safeguard MCP server with OAuth and chooses which tools Claude can use, so an assistant that explains code like the RSA example can also look up that code's dependencies.

Click through it at your own pace, or open it full screen.

To try it on your own projects, download Safeguard or read the CLI documentation.

Quick check

Sources

• MacTutor: Nine Chapters on the Mathematical Art
• MacTutor: Overview of Chinese mathematics
• MacTutor: Chinese numerals
• MacTutor: Liu Hui
• MacTutor: Zu Chongzhi
• MacTutor: Sun Zi
• MacTutor: Qin Jiushao
• MacTutor: Jia Xian
• MacTutor: Yang Hui
• MacTutor: Zhu Shijie
• MacTutor: William George Horner
• Nature news, 7 January 2014: Ancient times table hidden in Chinese bamboo strips
• RFC 8017, PKCS #1: RSA Cryptography Specifications Version 2.2
• UNESCO: Chinese Zhusuan, knowledge and practices of mathematical calculation through the abacus
• Shen Kangshen, John N. Crossley and Anthony W.-C. Lun, The Nine Chapters on the Mathematical Art: Companion and Commentary, Oxford University Press and Science Press, 1999.
• Joseph Needham with Wang Ling, Science and Civilisation in China, volume 3, Mathematics and the Sciences of the Heavens and the Earth, Cambridge University Press, 1959.
• Ulrich Libbrecht, Chinese Mathematics in the Thirteenth Century: The Shu-shu chiu-chang of Ch'in Chiu-shao, MIT Press, 1973.
• Roger Hart, The Chinese Roots of Linear Algebra, Johns Hopkins University Press, 2011.
• D. B. Wagner, "A proof of the Pythagorean theorem by Liu Hui (third century AD)", Historia Mathematica 12 (1985), 71 to 73.
• D. Boneh, R. A. DeMillo and R. J. Lipton, "On the importance of checking cryptographic protocols for faults", EUROCRYPT 1997.

Last reviewed: 25 October 2026.