Liu Hui's π algorithm

From Wikipedia, the free encyclopedia

Liu Hui on area of circle
Liu Hui on area of circle

Liu Hui's π algorithm is a mathematical algorithm. invented by Liu Hui (fl. 3rd century), a mathematician of Wei Kingdom.Before his time, the ratio of circumference of circle to diameter was often taken experimentally as 3 in China, while Zhang Heng (78–139) rendered it as 3.1724 (from the proportion of the celestial circle to the diameter of the earth, \tfrac{736}{232}) or as \pi=\sqrt10=3.162. But Liu Hui was not satisfied with \pi=\sqrt10, he commented that it was too large and overshot the mark. Another mathematician Wan Fan(219-257) provided \pi=\frac{142}{45}=3.156. All these empirical π values were accurate to 3 digits. Liu Hui was the first Chinese mathematician to provide a rigorous algorithm for calculation of π to any accuracy. Liu Hui's own calculation with 96-gon provided an accuracy of 5 digits π = 3.1416.

Liu Hui remarked in his commentary to the The Nine Chapters on the Mathematical Art, that π= 3 was only the ratio of the circumference of an inscribed hexagon to the diameter of the circle, hence π must be greater than 3. He went on to provided a detailed step by step discription of an iterative algorithm to calculate π to any required accuracy based on disecting polygons; he calculated π to between 3.141024 and 3.142708 with a 96-gon; he suggested that 3.14 was a good enough approximation, and expressed π as 157/50, he admitted that this number was a bit small. Later he invented an ingenious quick method to improve on it, and got π = 3.1416 with only a 96-gon, with an accuracy comparable to that from a 1526-gon. His most important contribution in this area was his simple iterative π algorithm.

Contents

[edit] Area of circle

area of circle=radius x half circumference
area of circle=radius x half circumference

Liu Hui argued:

"Multiply one side of a hexagon by radius, then multiply by 3, yields the area of dodecagon; if we cut a hexagon into dodecagon, mulitply it's side with radius, then again multiply by 6, yields the area of 24-gon; the finer we cut the smaller the loss with respect to the area of circle, thus with further cut after cut, the area of the resulting polygon will coincide and become one with the circle, there will be no loss".

Apparently Liu Hui had already mastered the concept of limit[1].

\lim_{N \to \infty} area of N-gon \longrightarrow area of circle.

Further, Liu Hui proved the area of circle = half of circumference multiplied by radius, He said

"Between a polygon and a circle, there are excess radius. Multiply the excess radius with a side of polygon. The resulting area exceeds the boundary of circle".

In the diagram d = excess radius. Multipying d with one side results in oblong ABCD which exceeds the boundary of circle. If a side of polygon is so small (i.e. there is very large number of sides) then there will be no more excess radius, hence no nore excess area."

As in the diagram, when N \longrightarrowinfinity, d \longrightarrow 0, and ABCD \longrightarrow 0.

"Multiply a side of polygon with radius, the area doubles, hence muliply half circumference with radius, yields the area of circle".

When N \longrightarrow infinity, half the circumference of N-gon approaches a semicircle, thus half a circumference of circle muliply by radius \longrightarrow area of circle. Liu Hui did not explain in detail this deduction. However this is self evident by using Liu Hui's In-out complement principle he provided elsewhere in The Nine Chapters on the Mathematical Art: Cut up a geometric diagram into parts, move the parts like jigsaw puzzle around to form another diagram, the area of the two diagrams will be identical.

Thus move around the 6 green triangles 3 blue triangles and 3 red triangles into an oblong, with width = 3L, and height R,

hence the area of dodecagon = 3 \times R \times L;

In general, multiplying half of the circumference of N-gon with radius yields area of 2N-gon. He used this result repetively in his π algorithm.

[edit] Iterative algorithm

Liu Hui's π algorithm
Liu Hui's π algorithm

Lui Hui began with a inscribed hexagon. Let M be the length of one side AB of hexagon, r is the radius of circle.

Bisect AB with line OPC, AC becomes one side of dodecagon, let its length be m.

AOP, APC are two right angle triangles. Liu Hui used Gou Gu theorem repetitively:

{} G^2 = r^2 - \left(\frac{M}{2}\right)^2
{}G= \sqrt{r^2- \frac{M^2}{4}}
{} j= r - G = r - \sqrt{r^2- \frac{M^2}{4}}
{}m^2= \left(\frac{M}{2}\right)^2 + j^2
{}m=\sqrt{m^2}

With R = 10 units, he obtained

area of 96-gon {}A_{96} = 313 {584 \over 625}
area of 192-gon {}A_{192}= 314 {64 \over 625}

and π = 3.141024.

Liu Hui carried out his calculation with rod calculus, and expressed his results with fractions. However, the iterative nature of Liu Hui's π algorthm is quite clear:

2-m^2 =\sqrt{2+(2-M^2)}

In which m is the length of one side of next order polygon disected from M, then repeat the same calculation, each step required only one addition, one square root extraction.

Begin with m6 = M = 1 for hexagon:

Length of one side of successive polygons:

{} m_{12} = \sqrt{2- \sqrt{2+1}}
{} m_{24} = \sqrt{2-\sqrt{2+ \sqrt{2+1}}}
{} m_{48} = \sqrt{2-\sqrt{2+\sqrt{2+ \sqrt{2+1}}}}
{} m_{96} = \sqrt{2-\sqrt{2+\sqrt{2+\sqrt{2+ \sqrt{2+1}}}}}

Area of successive polygons inscribed in a circle with radius=1.

{}\pi\approxeq A_{24} =m_{12}\cdot 6 =\sqrt{2- \sqrt{2+1}}\cdot 6
{}\pi\approxeq A_{48} =m_{24}\cdot 12 =\sqrt{2-\sqrt{2+ \sqrt{2+1}}}\cdot 12
{}\pi\approxeq A_{96} =m_{48}\cdot 24 =\sqrt{2-\sqrt{2+\sqrt{2+\sqrt{2+1}}}}\cdot24
{}\pi\approxeq A_{192} =m_{96}\cdot 48 =\sqrt{2-\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+1}}}}}\cdot 48

Liu Hui's π algorithm can be carried through to higher order polygons to any accuracy. For example:

\begin{align} \pi \approxeq A_{3072} & {} \approxeq 768 \sqrt{2 - \sqrt{2 + \sqrt{2 + \sqrt{2 + \sqrt{2 + \sqrt{2 + \sqrt{2 + \sqrt{2 + \sqrt{2+1}}}}}}}}} \\ & {} \approxeq 3.141590463236763. \end{align}
\pi \approxeq A_{12288} \approxeq 3.141592516588156
\pi \approxeq A_{49152} \approxeq 3.141592645321216

[edit] Quick method

Calculation of square roots of irrational numbers was not an easy task in the third century with counting rods.Liu Hui discovered a short cut by studied the area differentials of polygons, and found that the proportion of the difference in area of sucessive order polyons was approximately 1/4.[2]

Let DN denotes the difference in areas of N-gon and (N/2)-gon

D_N = A_N - A_{N/2}\,

He found:

D_{96} \approxeq \frac{1}{4} D_{48}


D_{192} \approxeq \frac{1}{4} D_{96} 1

Hence:

\begin{align} D_{384} & {} \approxeq \frac{1}{4} D_{192} \\ D_{768} & {} \approxeq \left(\frac{1}{4}\right)^2 D_{192} \\ D_{1536} & {} \approxeq \left(\frac{1}{4}\right)^3 D_{192} \\ D_{3072} & {} \approxeq \left(\frac{1}{4}\right)^4 D_{192} \\ & {} \ \ \vdots \end{align}

Area of unit circle= {}\pi = A_{192} + D_{384} + D_{768}+D_{1536}+D_{3072} + \cdots \approxeq A_{192} + F \cdot D_{192}.

In which

F = \frac{1}{4} + \left(\frac{1}{4}\right)^2 + \left(\frac{1}{4}\right)^3 + \left(\frac{1}{4}\right)^4 + \cdots = \frac{1}{3}.

That is all the subsequent excess areas add up amount to one third of the D192

area of unit circle {}=\pi = A_{192} + \left(\frac{1}{3}\right)D_{192} \sim {3927 \over 1250} = 3.1416.\,2

Liu Hui was quite happy with this result, he said, he got the same result by calculation to 1536gon and obtained the area of 3072-gon.

This explained four questions:

1) Why he stop short at A192 in his presentation of his algorithm. Because he discovered a quick method of improving the accuracy of π, achieving same result of 1536-gon with only 96-gon. After all calculation of square roots was not a simple task with rod calculus. With the quick method, he only needed to perform one more subtraction, one more division (by 3) and one more addition, instead of four more square root extractions.

2)Why he prefered to calculate π through calculation of areas instead of circumferences of successive polygons, because the quick method required information about the difference in areas of sucessive polygons.

3) Who was the true author of the paragraph containing calculation of

\pi = {3927 \over 1250}.

That famous paragraph began with "A Han dynasty bronze container in the military warehouse of Jin dynasty....".

Many scholars, among them Yoshio Mikami and Joseph Needham, believed that the "Han dynasty bronze container" paragraph was the work of Liu Hui and not Zu Chongzhi as other believed, because of the strong correlation of the two methods through area calculation, and because there was not a single word mentioning Zu's 3.1415926 < π < 3.1415927 result obtained through 12288-gon.

4) On what ground Lui Hui critcized Zhang Heng's \pi=\sqrt10 as "too large and overshoot the mark", or remarked on his own \pi= {157 \over 50} as "a bit small"?Of course with his more accurate result \pi= {3927 \over 1250}.

[edit] Later developments

Liu Hui established a solid algorithm for calculation of π to any accuracy.

  • Zu Chongzhi was familiar with Liu Hui's work, obtained 3.1415926 <π< 3.1415927 based on Liu Hui's π algorithm to 12288-gon. Zu Chongzhi's result was the world record for most accurate value of π for the next one thousand years. Zu Chongzhi also used He Chengtian's interplolation formula and obtained an approximate fraction \pi= {355 \over 113}.
  • Yuan dynasty mathematician Zhao Yu Xin worked on a variation of Liu Hui's π algorithm,by disecting an inscribed square instead of a hexagon.

[edit] Notes

Note 1: Check with spreedsheet:
D192 = 0.0016817478
D96 = 0.0067215898
D_{192} / D_{96}=0.2502009052 \approxeq 0.25
Note 2: double check with spreedsheet:
A192 = 3.1410319509
D192 = 0.0016817478
\pi \approxeq A_{192}+ \frac{1}{3} D_{192}\approxeq 3.1410319509 +0.0016817478/3
\pi \approxeq 3.1410319509 +0.0005605826
\pi \approxeq 3.1415925335.

Off only 0.0000001201 with Π. Liu Hui's quick method was indeed excellent, potentially able to deliver almost the same result of 12288-gon(3.141492516588) with only 96-gon.

[edit] References

  1. ^ First noted by Japanese mathematician Yoshio Mikami
  2. ^ Yoshio Mikami: Development of Mathematics in China and Japan
Languages