Qin Jiushao's dayan method: the general remainder algorithm of 1247, in Python
Qin Jiushao's dayan method from the Shushu jiuzhang (1247): the Chinese text and a translation, his rice and dike problems, the qiuyi step and tested Python.
In 1247 Qin Jiushao (秦九韶, Ch'in Chiu-shao) dated the preface of his Shushu jiuzhang (數書九章, Mathematical Treatise in Nine Sections). The book opens with the dayan method (大衍總數術, dàyǎn zǒngshù shù), a general procedure for finding a number from its remainders by several divisors, including divisors that share factors. He worked it through 9 problems on divination, the calendar, money, grain, building works and couriers.
The Sunzi Suanjing, 8 to 10 centuries earlier, gave the multipliers 70, 21 and 15 for the divisors 3, 5 and 7 and said nothing about how to find them. Qin's method finds them for any divisors. I read the rule and 4 of his problems in Chinese, translated the core procedure, and coded it in Python. The code reproduces every number from the definite numbers to the answer in his worked solutions to the rice, dike and couriers problems (dayan.py on GitHub). The series is Ancient algorithms, implemented.
The problem: Qin's rice thieves
This is Qin's rice problem (餘米推數), in my paraphrase:
A rice shop reports a theft. It had 3 baskets, each filled to the brim with the same amount, which nobody recorded. The left basket now has 1 ge of rice left, the middle 1 sheng 4 ge, the right 1 ge. 3 thieves are caught. The first says he scooped from the left basket with a ladle, the second from the middle basket with a wooden shoe, the third from the remaining basket with a lacquer bowl. They ate the rice over many days and do not know how much they took. The ladle holds 1 sheng 9 ge, the shoe 1 sheng 7 ge, the bowl 1 sheng 2 ge. How much rice was lost, and how much did each thief take?
1 sheng is 10 ge, so the measures are 19, 17 and 12 ge, and the leftovers are 1, 14 and 1 ge. Each basket held a number N with
Qin's answer (答曰): the thieves took 3,192, 3,179 and 3,192 ge, 9,563 ge in all, which he writes as 9 shi 5 dou 6 sheng 3 ge. His worked solution (草) finds on the way that each basket held 3,193 ge.1
The Sunzi recipe would solve this if someone handed you the 3 multipliers. Here they are 3,060, 1,140 and 3,553, and nothing in the Sunzi text tells you how to get them. Qin's method does.
Who was Qin Jiushao?
- Qin Jiushao lived from about 1202 to 1261; both dates are uncertain. He was an official of the Southern Song. In his preface he signs himself as from Lu commandery, says he studied with the astronomical bureau in the capital as a young man and with a recluse scholar, and says he wrote in years of war.
- The book has 81 problems in 9 categories, by Qin's own count in the preface. The first category, dayan, is the remainder problem. His preface is dated the 9th month of the 7th year of Chunyou, which is 1247.
- Why he wrote it down. The preface says the dayan method is the one method missing from the Nine Chapters, the classic of Chinese mathematics, that nobody had been able to work it out, and that calendar makers used it a good deal while mistaking it for fangcheng, the array method for linear equations.
The text I read is the Siku Quanshu copy of 1784, titled 數學九章 (Shuxue jiuzhang), which its editors rebuilt from the Yongle dadian. They added notes after many paragraphs, corrected numbers, and moved the general rule from after the first problem to the head of the chapter.
The source text
The qiuyi procedure
The core is the procedure for the multiplier, the dayan qiuyi shu (大衍求一術), "the great extension method of finding 1". The Siku copy writes the variant 竒 for 奇, and 數 for 術 in this heading. I give the standard forms, with my punctuation.
大衍求一術云:置奇右上,定居右下,立天元一於左上。先以右上除右下,所得商數與左上一相生,入左下。然後乃以右行上下,以少除多,遞互除之,所得商數隨即遞互累乘,歸左行上下。須使右上末後奇一而止,乃驗左上所得,以為乘率。
Dàyǎn qiú yī shù yún: zhì jī yòu shàng, dìng jū yòu xià, lì tiānyuán yī yú zuǒ shàng. Xiān yǐ yòu shàng chú yòu xià, suǒ dé shāng shù yǔ zuǒ shàng yī xiāng shēng, rù zuǒ xià. Ránhòu nǎi yǐ yòu háng shàng xià, yǐ shǎo chú duō, dìhù chú zhī, suǒ dé shāng shù suíjí dìhù lěi chéng, guī zuǒ háng shàng xià. Xū shǐ yòu shàng mò hòu jī yī ér zhǐ, nǎi yàn zuǒ shàng suǒ dé, yǐ wéi chénglǜ.
| Chinese | Pinyin | Meaning |
|---|---|---|
| 奇 | jī | the remainder, the odd amount left over |
| 定 | dìng | the definite number, the divisor after reduction |
| 右上, 右下 | yòu shàng, yòu xià | upper right, lower right, places on the counting board |
| 天元一 | tiānyuán yī | the "celestial element" 1, a unit set on the board |
| 商數 | shāng shù | the quotient |
| 相生 | xiāng shēng | to generate together, here to multiply |
| 以少除多 | yǐ shǎo chú duō | divide the larger by the smaller |
| 遞互 | dìhù | in turn, alternately |
| 累乘 | lěi chéng | multiply and accumulate |
| 右上末後奇一 | yòu shàng mò hòu jī yī | the upper right finally has remainder 1 |
| 乘率 | chénglǜ | the multiplier |
My translation:
The great extension method of finding 1 says: put the remainder upper right and the definite number lower right, and set up the celestial element 1 upper left. First divide the lower right by the upper right; multiply the quotient by the 1 upper left and enter it lower left. Then divide the upper and lower numbers of the right column by each other, the smaller into the larger, in turn. Multiply each quotient as it comes by the left-hand number of the other row and add it into the left-hand number of the row that was divided. You must make the upper right end at 1, and then stop. Read the number upper left: that is the multiplier.
The text says 累乘, "multiply and accumulate", and leaves the addition implicit. Qin's worked solutions show it. In his first problem the last step multiplies the quotient 2 by the 1 lower left to get 2, and adds that into the 1 upper left, making 3. Wylie's 1852 summary, in his own words, calls the procedure "Finding Unity" and describes it as the alternate division of the 2 numbers by each other "till the remainder is reduced to 1".
The reduction
Before the multipliers come the definite numbers (定數). Qin's rule for divisors given as plain whole numbers begins:
元數者,先以兩連環求等,約奇弗約偶。
Yuán shù zhě, xiān yǐ liǎng liánhuán qiú děng, yuē jī fú yuē ǒu.
For original numbers: first take them 2 at a time, round the chain, and find their common measure; divide it out of the odd, and not out of the even.
Qin's paragraph on divisors ending in tens or hundreds (復數) adds the continued common measure (續等) for numbers that still share a factor: divide 1 number by it and multiply the other by it. A Siku editors' note applies the same move to plain whole numbers and adds that the text does not explain it in detail. Further paragraphs cover divisors with fractions.
What the text leaves open, and what is debated
- What "the odd" means. In Qin's first problem, the pair 2 and 4 has common measure 2, both numbers are even, and Qin reduces the 2. Wylie reads the rule as: divide the common measure out of the number that gives an odd quotient. The Siku editors read it as applying when the common measure is even, with the reverse when it is odd. The code follows Wylie. In the 4 problems of Qin's that I tested, each prime's highest power sits in only 1 of the original numbers, so the definite numbers are the same whichever number of a pair the common measure is divided out of.
- When the reduction is finished. The rule gives no test for completion. The code repeats the continued common measure until the pair shares no factor.
- The extra steps. Qin also takes a common divisor out of all the numbers at once (總等) and adjusts the use numbers afterward (泛用 to 正用). In the divination problem the adjustment adds the extension mother 12 to the 2nd use number, turning 12, 12, 4, 9 into 12, 24, 4, 9, which add to 49, the number of yarrow stalks in the Book of Changes. The Siku editors call this fit forced. The code leaves both steps out and returns 12, 12, 4, 9; the answers do not change.
- Errors. The Siku editors flag numbers in the text that do not work. In the pursuit problem (程行相及), Qin's definite numbers for 300, 250 and 200 are 3, 125 and 16, but 16 does not divide 200; the editors correct them to 3, 125 and 8, whose product 3,000 is the least common multiple. They also say the answers to the calendar problem (古曆會積) do not agree with the data, and that Qin's procedure for divisors ending in tens and hundreds cannot be fixed into a single rule; they offer a revised one.
- Transmission between India and China. The sources I read document no route by which the method passed in either direction, and I treat the kuttaka and qiuyi as separate developments.
Working the rice problem
The 3 measures, 19, 17 and 12, share no factor, so they are already the definite numbers. Then Qin's steps, with his names:
- Extension mother (衍母): 19 × 17 × 12 = 3,876.
- Extension numbers (衍數): 3,876 divided by each definite number: 204, 228 and 323.
- Remainders (奇): each extension number reduced by its own definite number. 204 leaves 14 with 19, 228 leaves 7 with 17, and 323 leaves 11 with 12.
- Multipliers (乘率), by qiuyi: 15, 5 and 11. Check: 14 × 15 = 210 = 11 × 19 + 1.
- Use numbers (用數): extension number times multiplier: 3,060, 1,140 and 3,553.
- Total (總數): each leftover times its use number, added: 1 × 3,060 + 14 × 1,140 + 1 × 3,553 = 22,573.
- Take away the extension mother as often as it goes: 22,573 - 5 × 3,876 = 3,193.
Every number above is in Qin's worked solution.
Here is the qiuyi board for the first multiplier, remainder 14 and definite number 19:
Working the reduction: the dike problem
In the dike problem (推計土功), 4 counties build equal lengths of an embankment. From their labor quotas, the 4 crews build 54, 57, 75 and 72 zhang a day. The first 2 counties finish on a full day; the 3rd has 51 zhang left over and the 4th 18 zhang, less than a day's work. How long is each county's share?
The divisors share factors, so the Sunzi recipe cannot start. The code reduces them in pairs:
- 54 and 57 share 3. 57 ÷ 3 = 19 is odd, so 57 becomes 19.
- 54 and 75 share 3. 75 ÷ 3 = 25 is odd, so 75 becomes 25.
- 54 and 72 share 18. 54 ÷ 18 = 3 is odd, so 54 becomes 3. But 3 still shares 3 with 72, so the continued common measure moves it across: 3 and 72 become 9 and 24, then 27 and 8.
- The other pairs already share no factor.
The definite numbers are 27, 19, 25 and 8, the same as in Qin's solution.2 In terms of prime factors, each prime goes in full to the divisor where it appears to the highest power: 23 from 72, 33 from 54, 52 from 75, 19 from 57. Their product, 102,600, is the least common multiple of 54, 57, 75 and 72.
Then the steps run as for the rice: extension numbers 3,800, 5,400, 4,104 and 12,825; remainders 20, 4, 4 and 1; multipliers 23, 5, 19 and 1; use numbers 87,400, 27,000, 77,976 and 12,825. The total is 51 × 77,976 + 18 × 12,825 = 4,207,626, and taking away 102,600 as often as it goes leaves 1,026 zhang for each county. Qin gets the same. Check: 1,026 = 19 × 54 = 18 × 57 = 13 × 75 + 51 = 14 × 72 + 18.
Why it works
The board. At every step the 4 numbers keep 2 relations, modulo the definite number m, with remainder a:
At the set-up, 1 × a ≡ a and 0 × a ≡ -m ≡ 0. A division of the lower right by the upper right subtracts q times the upper row from the lower row on the right, and adds q times the upper left to the lower left, and the minus sign makes both relations survive. The same holds for a division in the other direction. When the upper right is 1, the first relation reads upper left × a ≡ 1, so the upper left is the multiplier.
Why the 1 has to be upper right. In the board for 14 and 19, step 3 already reaches a 1, in the lower right, where the lower left is 4. By the second relation, 14 × 4 = 56 leaves -1 with 19, which is 57 - 1. That 4 is the extended Euclidean algorithm's coefficient -4, without its sign. Qin's rule that the 1 must end upper right, with the last quotient made 1 smaller, flips it to +1: 15 = 19 - 4. All the numbers on the board stay positive, and the sign never needs tracking.
The use numbers. Qin checks his use numbers by adding them: the sum must be 1 more than a multiple of the extension mother (併泛課衍母多一者為正用). For the rice, 3,060 + 1,140 + 3,553 = 7,753 = 2 × 3,876 + 1.
The reduction. Each pair step gives a prime's full power to 1 of the 2 numbers, so each prime ends in exactly 1 definite number, at its highest power. An answer for the definite numbers is then an answer for the originals, provided the original remainders agree on their shared factors.3
The Python
This is the method in a short form. It reproduces the rice and dike answers.
from math import gcd, prod
def qiuyi(qi: int, m: int) -> int:
"""Qin's multiplier: k with qi * k leaving 1 when divided by m."""
upper_left, upper_right, lower_left, lower_right = 1, qi, 0, m
while upper_right > 1:
if lower_right > upper_right:
q = lower_right // upper_right
lower_right -= q * upper_right
lower_left += q * upper_left
else:
q = (upper_right - 1) // lower_right # leave 1 in the upper right
upper_right -= q * lower_right
upper_left += q * lower_left
return upper_left
def definite_numbers(original: list[int]) -> list[int]:
"""Coprime divisors of the originals whose product is their lcm."""
nums = list(original)
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
g = gcd(nums[i], nums[j])
if g > 1:
nums[i] //= g
while (k := gcd(nums[i], nums[j])) > 1: # the continued common measure
nums[i], nums[j] = nums[i] * k, nums[j] // k
return nums
def dayan(pairs: list[tuple[int, int]]) -> int:
"""Smallest N >= 0 leaving each remainder r with its divisor m."""
definite = definite_numbers([m for _, m in pairs])
mother = prod(definite)
total = 0
for (r, _), d in zip(pairs, definite):
extension = mother // d
qi = extension % d or d # a definite number 1 gives remainder 1, as in Qin
total += r * extension * qiuyi(qi, d)
return total % mother
print(qiuyi(14, 19)) # 15
print(definite_numbers([54, 57, 75, 72])) # [27, 19, 25, 8]
print(dayan([(1, 19), (14, 17), (1, 12)])) # 3193
print(dayan([(0, 54), (0, 57), (51, 75), (18, 72)])) # 1026
This short version always divides the common measure out of the first number of the pair. The repo version follows Wylie's reading of "divide the odd", returns a record of every intermediate number, and raises an error when the remainders contradict each other. The tests check:
- Qin's own numbers: every number from the definite numbers to the answer in his rice, dike and couriers solutions, his qiuyi board for 3 and 4, the divination use numbers before his adjustment, and the Siku editors' correction in the pursuit problem;
- property tests with Hypothesis: qiuyi equals Python's
pow(a, -1, m), the kuttaka's inverse and the extended Euclidean coefficient up to 1012, and the dayan answer matchescrtfor up to 6 divisors that share factors.
Against the kuttaka and the extended Euclidean algorithm
All 3 run the same chain of divisions. They differ in what they carry:
- The extended Euclidean algorithm carries 2 coefficients forward,
sandt, with signs, and throws the quotients away. - Aryabhata's kuttaka (499 CE) keeps every quotient in a column and folds the column from the bottom once the divisions stop. It then adds or subtracts depending on whether the count of quotients is even or odd.
- Qin's qiuyi carries 1 coefficient forward, the one for the remainder, split over 2 cells so that every number stays positive. Forcing the final 1 into the upper right takes the place of the sign.
The repo's benchmark counts divisions on 1,000 random coprime pairs at each of 4 sizes, from 16 to 1,024 bits. Qiuyi used the same number of divisions as Euclid's algorithm in 506 to 521 pairs of each 1,000, and 1 fewer in the rest. It saves the last division whenever the 1 first appears in the upper right, because Euclid's algorithm goes on to divide by 1 to reach 0.
Parallels and lineage
These are the connections I can support from sources:
- Chinese calendar computation. Wylie names the Tang monk Yi Xing, author of the Dayan calendar, as the reputed first to apply the dayan method in astronomy, and Qin's own problem 2 asks for the cycle in which the solar year, the lunar month and the 60-day cycle start together.
- Aryabhata (499) and Bhaskara I (629). The kuttaka solves the same problem with the same divisions in Sanskrit, about 750 years earlier.
- Libbrecht (1973). Ulrich Libbrecht's Chinese Mathematics in the Thirteenth Century studies the Shushu jiuzhang, including the dayan problems.
Key takeaways
- Qin Jiushao's dayan method, from the Shushu jiuzhang (preface dated 1247), is a complete algorithm for the remainder problem, including divisors that share factors.
- It reduces the divisors to coprime definite numbers, finds each multiplier with the qiuyi procedure, and combines them the way Sunzi's 70, 21, 15 recipe does.
- Qiuyi runs the extended Euclidean chain of divisions and carries only the multiplier, with every number positive. It uses the same number of divisions as Euclid or 1 fewer.
- The Python reproduces every number from the definite numbers to the answer in Qin's rice, dike and couriers solutions and agrees with the incremental construction,
crt, on random inputs. - The code and tests are in ancient-algorithms. The earlier posts cover the Sunzi problem and the kuttaka.
Sources
- Qin Jiushao, Shushu jiuzhang (數書九章), preface dated 1247. Siku Quanshu copy, titled 數學九章, 18 juan, 1784. E-text: Chinese Wikisource. The dayan rule and problems are in juan 1, parts 1 and 2.
- A. Wylie, "Jottings on the science of the Chinese arithmetic", first published in 1852. Reprinted in Chinese Researches, Shanghai, 1897, pp. 159 to 194. The dayan rule is on pp. 175 to 179.
- U. Libbrecht, Chinese Mathematics in the Thirteenth Century: The Shu-shu chiu-chang of Ch'in Chiu-shao. MIT Press, 1973.
- Sunzi Suanjing (孫子算經), Siku Quanshu copy. E-text: Chinese Wikisource.
Footnotes
-
10 ge make 1 sheng, 10 sheng 1 dou, and 10 dou 1 shi. So 3,193 ge is 3 shi 1 dou 9 sheng 3 ge, as in Qin's worked solution. ↩
-
Qin's own route differs in order: he first takes 3 out of 57, 75 and 72 together, then reduces 54 by 6 to 9, then moves a 3 from 24 to 9. ↩
-
Qin does not check this. With divisors 4 and 6, remainders 0 and 1 have no solution, because the first makes the number even and the second odd. The repo version raises an error in that case. ↩
Common questions
What is the dayan method?↓
The dayan method (dayan zongshu shu) is Qin Jiushao's general procedure, from the Shushu jiuzhang of 1247, for finding a number that leaves given remainders with given divisors. It reduces the divisors to ones that share no factor, finds a multiplier for each with the qiuyi procedure, and combines the remainders the way the Sunzi Suanjing's 70, 21, 15 recipe does.
Who was Qin Jiushao?↓
Qin Jiushao (Ch'in Chiu-shao, c. 1202 to 1261) was a Southern Song official and mathematician. His Shushu jiuzhang, or Mathematical Treatise in Nine Sections, has a preface dated the 9th month of 1247. In it he says he studied with the astronomical bureau in the capital and with a recluse scholar.
What does dayan qiuyi mean?↓
Dayan qiuyi shu means the great extension method of finding 1. Given a remainder and a divisor that share no factor, it finds the multiplier that makes the remainder leave 1 with the divisor. Today this number is called a modular inverse.
Is the dayan method the same as the Chinese remainder theorem?↓
The dayan method is a complete algorithm for the problem the Chinese remainder theorem describes. It goes further than the Sunzi Suanjing's recipe in 2 ways: it says how to find the multipliers for any divisors, and it handles divisors that share factors.
How does Qin Jiushao handle divisors that share a factor?↓
He takes the divisors 2 at a time, divides their common factor out of one of them, and moves any factor still shared from one to the other. The result is a set of divisors with no common factor whose product is the least common multiple of the originals. In his dike problem, 54, 57, 75 and 72 become 27, 19, 25 and 8.