2 (numerical algorithm) 2. = ratio of the circumference to its diameter, number, Ludolph s number... sin, cos =3.45926535... 0 e x2 dx = /2 etc. : 999 : 99 : 974 P.: 973, J.-P.: 200 J. Arndt, Ch. Haenel: Unleashed, Springer, Berlin Heidelberg, 200 2.2 mathematics a, b. b = Pythagoras (572-492 B.C.) b =2/ 3 3 <<3 2 =2 3=3.464 3 2 5
a b 2.. half hexagon 2.2. n 2n O, /n LMN; LON : n /n n = LN =2a; LOT : n /(2n) n /2 = LT = b; LOM : 2n /(2n); 2n = LM =2a ; POQ : 2n /(2n) 2n = PQ =2b ; n OT LON LT LT H OTL LH : LT = OL : OT. OT 2 =+b 2 a = b +b 2 (2.) 2n a = b +b 2 (2.2) n 2n TPM TLH bb = a(b b ) (2.3) 6
T P b M Q L 2a a H N O 2.2. n-polygons 7
(2.) (2.3) a b = b + +b 2 (2.4) n =2A, n =2B, 2n =2A, 2n =2B A = na = nb +b 2, B = nb, A = 2na = 2nb +b 2, B =2nb = C = +b 2,C = +b 2 A = B/C, B = 2B +C, 2nb + +b 2 ( = ( B 2 B + )), A (2.5) (2.6) A = B /C n =4 2 m+ (m =, 2,...) 2l m, 2L m 2l m 2A 2L m 2B L =4, (2.7) { l n = L n / +(L n /2 n+ ) 2, (n =, 2,...) (2.8) L n+ = 2/ (/l n +/L n ), (recurrence formula) L,l, }{{} L 2,l 2, }{{} 8 L 3,l 3,... }{{} 6 8
2.2.2 () 0 <l n <<L n (2) l n <l n+ <L n+ <L n {l n } {L n } (3) 2 2=l <l 2 < <l n <l n+ < <L n+ <L n < <L 2 <L =4 (4) l = lim n l n, L = lim n L n (5) l = L = 2.2.3 (2.8) L n L n+ = 2 + + L n = ( ) Ln + L n+ 2 l n ( Ln 2 n+ ) 2 + 2 6 2 + 2n O(2 4n ) (n ) L n = O(2 2n )=O(4 n ) (n ) (2.9) log 0 4=0.6020... n L n 0 0.6 Ludolph van Ceulen(540-60, ). 2.2.4 2 m+ (m =, 2,...) 2 n+ n ln Ln 2.82842724746898 4.0000000000000000 2 3.06467458920783 3.337084989847607 3 3.2445522580524 3.82597878074528 9
4 3.365484905459398 3.57249074292564 5 3.4033569547534 3.4483852459047 6 3.42772509327738 3.422236299424577 7 3.4538044308 3.4750369689670 8 3.45729403670922 3.4632080703823 9 3.4587725277605 3.4602502568095 0 3.4594252006 3.459577495898 3.459234557089 3.45932696293085 2 3.45925765848738 3.45928075996455 3 3.4592634338564 3.45926920922557 4 3.45926487769870 3.4592663254094 5 3.45926523865925 3.4592655996980 6 3.45926532889937 3.459265493954 7 3.4592653545942 3.4592653740946 8 3.45926535709939 3.4592653627394 9 3.45926535850938 3.4592653599940 20 3.4592653588694 3.459265359244 2 3.45926535895009 3.45926535903820 22 3.4592653589722 3.4592653589944 23 3.45926535897762 3.4592653589833 24 3.45926535897900 3.45926535898033 25 3.4592653589793 3.45926535897967 26 3.45926535897940 3.45926535897949 27 3.45926535897949 3.45926535897949 28 3.45926535897949 3.45926535897949 29 3.45926535897949 3.45926535897949 30 3.45926535897949 3.45926535897949 2.2.5 real numbers R integers Z rational numbers Q algebraic numbers transcendental numbers 0
J.H. Lambert (728-77, ): (76) C.L.F. Lindemann (852-939, ): (882) 2.3 tan x tan 6 =, tan 4 = etc. Taylor (Maclaurin ) f(x) =f(0) + f (0)x + f (0) x 2 + 2 2.3. Gregory Leibniz J. Gregory (638-675, ) G.W.F. Leibniz (646-76, ) tan x arctan x 4 = arctan d (arctan x) = dx +x 2 0 dx +x 2 = 4 +x 2 = x 2 + x 4 x 6 + +( ) n x 2n +, ( x < ) dx +x 2 = x 3 x3 + 5 x5 7 x7 + + ( )n 2n + x2n+ + arctan x Maclaurin x = 4 = 3 + 5 ( )n + + + (2.0) 7 2n + ( ) n = 4 2n + = (4m + )(4m +2), 4 n=0 M m=0 m=0 (4m + )(4m +2) = O ( ) (4M + 3)(4M +4) ( ) = O 6M 2
M =0 (6M 2 ) 6.2 0 4 /( + x 2 ) Maclaurin 2.3.2 Sharp / 3 0 dx +x 2 = arctan 3 = 6 6 = ( 3 9 + ( )n + + 5 32 (2n +)3 + n / 3 3 Gregory Leibniz Sharp 699 ) 2.3.3 2.2. n 2n LON = 2 n, LOH = n, LH =sin n, LT =tan n 2 n+ 2l n 2 n+ 2L n sin, tan Maclaurin l n =2 n+ sin 2, L n+ n =2 n+ tan (2.) 2 n+ sin x = x 3! x3 + 5! x5 7! x7 +, ( x < ) tan x = x + 3 x3 + 2 5 x5 + 7 35 x7 + ( x < 2 ) (2.) N =2 n+ ( l n = ( ) 2 ( ) ( 4 + ), L n = + ( ) 2 2 ( ) 4 + + ) 6 N 20 N 3 N 5 N ( 3 (2l n + L n )= + ( ) 4 + ) 20 N (/N) 2 {l n }, {L n } { 3 (2l n + L n )} ( l n+ = 4 2 6 2 2(n+) + 60 ) 4 20 24(n+) 2
l () n 3 (4l n+ l n )= ( 3 (l n+ l n )+l n+ = 3 ) 4 4 + 20 24(n+) L () n 3 (4L n+ L n )= ( 3 (L n+ L n )+L n+ = 3 ) 4 2 4 + 5 24(n+) 2 4 6 extrapolation 664 739, 2 0 (n =9) 4 2 n+ n ln Ln accelerated 2.82842724746898 4.0000000000000000 3.2895464974597 2 3.06467458920783 3.337084989847607 3.455478056087323 3 3.2445522580524 3.82597878074528 3.4829394968778 4 3.365484905459398 3.57249074292564 3.46072967378 5 3.4033569547534 3.4483852459047 3.4593566385369 6 3.42772509327738 3.422236299424577 3.4592706026680 7 3.4538044308 3.4750369689670 3.4592657525237 8 3.45729403670922 3.4632080703823 3.4592653824559 9 3.4587725277605 3.4602502568095 3.4592653603704 0 3.4594252006 3.459577495898 3.45926535906635 3.459234557089 3.45932696293085 3.45926535898486 2 3.45925765848738 3.45928075996455 3.45926535897980 3 3.4592634338564 3.45926920922557 3.45926535897944 4 3.45926487769870 3.4592663254094 3.45926535897944 5 3.45926523865925 3.4592655996980 3.45926535897944 6 3.45926532889937 3.459265493954 3.45926535897944 7 3.4592653545942 3.4592653740946 3.45926535897944 8 3.45926535709939 3.4592653627394 3.45926535897944 9 3.45926535850938 3.4592653599940 3.45926535897936 3
20 3.4592653588694 3.459265359244 3.45926535897944 2 3.45926535895009 3.45926535903820 3.45926535897944 22 3.4592653589722 3.4592653589944 3.45926535897944 23 3.45926535897762 3.4592653589833 3.45926535897944 24 3.45926535897900 3.45926535898033 3.45926535897944 25 3.4592653589793 3.45926535897967 3.45926535897944 26 3.45926535897940 3.45926535897949 3.45926535897944 27 3.45926535897949 3.45926535897949 3.45926535897949 28 3.45926535897949 3.45926535897949 3.45926535897949 29 3.45926535897949 3.45926535897949 3.45926535897949 30 3.45926535897949 3.45926535897949 3.45926535897949 2.3.4 Euler Machin L. Euler (707 783, ) key idea tan(a B) = a =tana, b =tanb ( ) a b A B = arctan +ab tan A tan B +tana tan B (2.2) Euler (748) 4 = arctan = arctan ( ) ( ) + arctan 2 3 (2.3) John Machin (706) 4 = arctan = 4 arctan ( ) 5 ( ) arctan 239 (2.4) 4 arctan 20 = A tan A = 5 9 (2.4) Machin arctan ( 4 =4 5 3 5 + 3 5 5 ) ( ) 5 7 5 + 7 239 3 239 + 3 5 239 + 5 O(5 2n ) 4
n Gregory-Leibniz Sharp Machin 0 4.0000000000000000 3.464065377548 3.832635983263602 2.6666666666666670 3.079204356780042 3.405970293260603 2 3.4666666666666668 3.568475699543 3.4620293250346 3 2.8952380952380956 3.37852895956805 3.45977282773 4 3.3396825396825403 3.426047456630850 3.45926824043994 5 2.97604676046765 3.43087854628836 3.4592652653086 6 3.2837384837384844 3.4674326988380 3.45926536235550 7 3.07078707878 3.456875947844 3.45926535886025 8 3.252365934788767 3.459977385062 3.45926535898362 9 3.04839689294032 3.4590509380806 3.45926535897922 0 3.232358094055939 3.45933045030822 3.45926535897940 3.0584027659273332 3.45924542876468 3.45926535897940 2 3.284027659273333 3.4592750203804 3.45926535897940 3 3.07025467779854 3.4592634547344 3.45926535897940 4 3.20885652269439 3.459265952743 3.45926535897940 5 3.07953394974278 3.4592657339980 3.45926535897940 6 3.200365554095489 3.4592654725758 3.45926535897940 7 3.08607980238346 3.4592653406658 3.45926535897940 8 3.9487909239425 3.45926536478267 3.45926535897940 9 3.096238066678399 3.4592653574038 3.45926535897940 20 3.8984782277596 3.45926535956356 3.45926535897940 2 3.09665264636424 3.45926535879342 3.45926535897940 22 3.8505045352534 3.45926535903873 3.45926535897940 23 3.0999440323738079 3.45926535896044 3.45926535897940 24 3.85766854350325 3.45926535898548 3.45926535897940 25 3.034532886027 3.45926535897745 3.45926535897940 26 3.7867009992202 3.45926535898002 3.45926535897940 27 3.05889738279475 3.4592653589798 3.45926535897940 28 3.76065768684385 3.45926535897944 3.45926535897940 29 3.08268566698947 3.45926535897936 3.45926535897940 30 3.73842337907505 3.45926535897940 3.45926535897940 2.4 Gregory Leibniz O(n 2 ) n 5
Machin O(c an ) (c>) E. Salamin R.P. Brent (976). 2. Landen (Landen transformation) 3. Legendre (Legendre formulae) 206, 58, 430, 000 (999 0 ) ftp://pi.super-computing.org/readme.our latest record Pascal A 0 =,B 0 =,T 0 = 2 4,X 0 = n := 0 while abs(a n B n ) >εdo begin A n+ := (A n + B n )/2; B n+ := A n B n ; T n+ := T n X n (A n A n+ ) 2 ; X n+ := 2X n ; n := n +; end; := (A n+ + B n+ ) 2 /(4T n+ ) 2.4. agm arithmetic-geometric mean (agm) a 0,b 0,c 0 :, a 2 0 = b 2 0 + c 2 0 a n = 2 (a n + b n ), b n = a n b n (c 2 n = a2 n b2 n ) (2.5) lim a n = lim b n agm(a 0,b 0 ) 6
. a n >b n 2. b n <a n <a n 3. b n <b n 4. b n <b n <a n <a n 5. {a n }, {b n } 6. ā = lim a n, b = lim b n n n 7. 2a n = a n + b n ā = b agm c n = 2 (a n b n ) 0 < <c n+ <c n < <c 2 <c c 2 n =4a n+c n+ c n+ = c2 n = 4a n+ 4a n+ ( ) c 2 2 n = = 4a n c < 0 c 2(n+2) (2 2 2 4 2 8 2 2(n+) )(a n+ a n a ) 2.4.2 I(a, b) = /2 0 dt /2 a2 cos 2 t + b 2 sin 2 t, J(a, b) = 0 a 2 cos 2 t + b 2 sin 2 tdt agm Landen I(a n,b n )=I(a n+,b n+ ), J(a n,b n )=2J(a n+,b n+ ) a n b n I(a n+,b n+ ) ( agm(a 0,b 0 ) I(a 0,b 0 )= 2, J(a 0,b 0 )= a 2 0 2 ) 2 j c 2 j I(a 0,b 0 ) (2.6) j=0 Legendre (b/a) 2 +(b /a ) 2 = a 2 I(a, b)j(a,b )+a 2 I(a,b )J(a, b) a 2 a 2 I(a, b)i(a,b )= 2 aa (2.7) a 0 = a 0 =,b 0 = k, b 0 = k (k 2 + k 2 =) (2.6), (2.7) = 4agm(,k)agm(,k ) 2 j (c 2 j + c 2 j ) j= 7
k = k =/ 2 = 4 ( agm(, / 2) ) 2 2 j+ c 2 j j= k, k 2.4.3 0 <k,k <, k 2 + k 2 = a 0 =,b 0 = k {a n,b n,c n } agm = agm(,k) a 0 =,b 0 = k {a n,b n,c n} agm = agm(,k ) NN 4a N+ a N + N N 2 j c 2 j 2 j c 2 j j= j= NN < [ ( 8 2 2 N exp agm ) )] agm agm agm 2N+ +2 N exp ( agm agm 2N + (2.8) 2 NN = N N < 2 2 N+4 agm 2 exp( 2 N+ ) (2.9) 0 ( ) ( ) log 0 N > 2 N+ N log log 0 0 2 2log 0 agm N O(c an ); O(c an ) 8