Check Machin-like formulas: Difference between revisions

From Rosetta Code
Content added Content deleted
m (use <math> for formatting in task)
(TeX: might as well use more conventional formating, then)
Line 3: Line 3:
Verify the following Machin-like formulas are correct by calculating the value of '''tan'''(''right hand side)'' for each equation using exact arithmetic and showing they equal 1:
Verify the following Machin-like formulas are correct by calculating the value of '''tan'''(''right hand side)'' for each equation using exact arithmetic and showing they equal 1:


: <math>\pi/4 = \arctan(1/2) + \arctan(1/3)</math>
: <math>{\pi\over4} = \arctan{1\over2} + \arctan{1\over3}</math>
: <math>\pi/4 = 2\times\arctan(1/3) + \arctan(1/7)</math>
: <math>{\pi\over4} = 2 \arctan{1\over3} + \arctan{1\over7}</math>
: <math>\pi/4 = 4\times\arctan(1/5) - \arctan(1/239)</math>
: <math>{\pi\over4} = 4 \arctan{1\over5} - \arctan{1\over239}</math>
: <math>\pi/4 = 5\times\arctan(1/7) + 2\times\arctan(3/79)</math>
: <math>{\pi\over4} = 5 \arctan{1\over7} + 2 \arctan{3\over79}</math>
: <math>\pi/4 = 5\times\arctan(29/278) + 7\times\arctan(3/79)</math>
: <math>{\pi\over4} = 5 \arctan{29\over278} + 7 \arctan{3\over79}</math>
: <math>\pi/4 = \arctan(1/2) + \arctan(1/5) + \arctan(1/8)</math>
: <math>{\pi\over4} = \arctan{1\over2} + \arctan{1\over5} + \arctan{1\over8}</math>
: <math>\pi/4 = 4\times\arctan(1/5) - \arctan(1/70) + \arctan(1/99)</math>
: <math>{\pi\over4} = 4 \arctan{1\over5} - \arctan{1\over70} + \arctan{1\over99}</math>
: <math>\pi/4 = 5\times\arctan(1/7) + 4\times\arctan(1/53) + 2\times\arctan(1/4443)</math>
: <math>{\pi\over4} = 5 \arctan{1\over7} + 4 \arctan{1\over53} + 2 \arctan{1\over4443}</math>
: <math>\pi/4 = 6\times\arctan(1/8) + 2\times\arctan(1/57) + \arctan(1/239)</math>
: <math>{\pi\over4} = 6 \arctan{1\over8} + 2 \arctan{1\over57} + \arctan{1\over239}</math>
: <math>\pi/4 = 8\times\arctan(1/10) - \arctan(1/239) - 4\times\arctan(1/515)</math>
: <math>{\pi\over4} = 8 \arctan{1\over10} - \arctan{1\over239} - 4 \arctan{1\over515}</math>
: <math>\pi/4 = 12\times\arctan(1/18) + 8\times\arctan(1/57) - 5\times\arctan(1/239)</math>
: <math>{\pi\over4} = 12 \arctan{1\over18} + 8 \arctan{1\over57} - 5 \arctan{1\over239}</math>
: <math>\pi/4 = 16\times\arctan(1/21) + 3\times\arctan(1/239) + 4\times\arctan(3/1042)</math>
: <math>{\pi\over4} = 16 \arctan{1\over21} + 3 \arctan{1\over239} + 4 \arctan{3\over1042}</math>
: <math>\pi/4 = 22\times\arctan(1/28) + 2\times\arctan(1/443) - 5\times\arctan(1/1393) - 10\times\arctan(1/11018)</math>
: <math>{\pi\over4} = 22 \arctan{1\over28} + 2 \arctan{1\over443} - 5 \arctan{1\over1393} - 10 \arctan{1\over11018}</math>
: <math>\pi/4 = 22\times\arctan(1/38) + 17\times\arctan(7/601) + 10\times\arctan(7/8149)</math>
: <math>{\pi\over4} = 22 \arctan{1\over38} + 17 \arctan{7\over601} + 10 \arctan{7\over8149}</math>
: <math>\pi/4 = 44\times\arctan(1/57) + 7\times\arctan(1/239) - 12\times\arctan(1/682) + 24\times\arctan(1/12943)</math>
: <math>{\pi\over4} = 44 \arctan{1\over57} + 7 \arctan{1\over239} - 12 \arctan{1\over682} + 24 \arctan{1\over12943}</math>
: <math>\pi/4 = 88\times\arctan(1/172) + 51\times\arctan(1/239) + 32\times\arctan(1/682) + 44\times\arctan(1/5357) + 68\times\arctan(1/12943)</math>
: <math>{\pi\over4} = 88 \arctan{1\over172} + 51 \arctan{1\over239} + 32 \arctan{1\over682} + 44 \arctan{1\over5357} + 68 \arctan{1\over12943}</math>


and confirm that the following formula is incorrect by showing '''tan'''(''right hand side)'' is ''not'' 1:
and confirm that the following formula is incorrect by showing '''tan'''(''right hand side)'' is ''not'' 1:


: <math>\pi/4 = 88\times\arctan(1/172) + 51\times\arctan(1/239) + 32\times\arctan(1/682) + 44\times\arctan(1/5357) + 68\times\arctan(1/12944)</math>
: <math>{\pi\over4} = 88 \arctan{1\over172} + 51 \arctan{1\over239} + 32 \arctan{1\over682} + 44 \arctan{1\over5357} + 68 \arctan{1\over12944}</math>


These identities are useful in calculating the values:
These identities are useful in calculating the values:
: <math>\tan(a + b) = (\tan(a) + \tan(b))/(1 - \tan(a)*\tan(b))</math>
: <math>\tan(a + b) = {\tan(a) + \tan(b) \over 1 - \tan(a) \tan(b)}</math>
: <math>\tan(\arctan(a/b)) = a/b</math>
: <math>\tan\left(\arctan{a\over b}\right) = {a\over b}</math>
: <math>\tan(-a) = -\tan(a)</math>
: <math>\tan(-a) = -\tan(a)</math>



Revision as of 21:05, 8 November 2012

Check Machin-like formulas is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Machin-like formulas are useful for efficiently computing numerical approximations to Pi. Verify the following Machin-like formulas are correct by calculating the value of tan(right hand side) for each equation using exact arithmetic and showing they equal 1:

and confirm that the following formula is incorrect by showing tan(right hand side) is not 1:

These identities are useful in calculating the values:

Note

It can be assumed that the equations are pre-parsed into a tree-like structure such as that used in the Haskel and OCaml examples below.

Haskell

<lang haskell>import Data.Ratio

tanEval (1,f) = f tanEval (coef,f) | coef < 0 = -tanEval (-coef, f) | otherwise = (a + b) / (1 - a * b) where a = tanEval (ca, f) b = tanEval (cb, f) ca = coef `div` 2 cb = coef - ca

tans [x] = tanEval x tans xs = (a + b) / (1 - a * b) where a = tans aa b = tans bb (aa, bb) = splitAt ((length xs)`div`2) xs

machins = [ [(1, 1%2), (1, 1%3)], [(2, 1%3), (1, 1%7)], [(12, 1%18), (8, 1%57), (-5, 1%239)], [(88, 1%172), (51, 1%239), (32 , 1%682), (44, 1%5357), (68, 1%12943)]]

not_machin = [(88, 1%172), (51, 1%239), (32 , 1%682), (44, 1%5357), (68, 1%12944)]

main = do putStrLn "Machins:" mapM_ (\x->putStrLn $ show(tans x) ++ " <-- " ++ show(x)) machins

putStr "\nnot Machin: "; print not_machin print (tans not_machin)</lang>

OCaml

<lang ocaml>open Num;; (* use exact rationals for results *)

let tadd p q = (p +/ q) // ((Int 1) -/ (p */ q)) in

(* tan(n*arctan(a/b)) *) let rec tan_expr (n,a,b) =

 if n = 1 then (Int a)//(Int b) else
 if n = -1 then (Int (-a))//(Int b) else
   let m = n/2 in
   let tm = tan_expr (m,a,b) in
   let m2 = tadd tm tm and k = n-m-m in
   if k = 0 then m2 else tadd (tan_expr (k,a,b)) m2 in

let verify (k, tlist) =

 Printf.printf "Testing: pi/%d = " k;
 let t_str = List.map (fun (x,y,z) -> Printf.sprintf "%d*atan(%d/%d)" x y z) tlist in
 print_endline (String.concat " + " t_str);
 let ans_terms = List.map tan_expr tlist in
 let answer = List.fold_left tadd (Int 0) ans_terms in
 Printf.printf "  tan(RHS) = %s\n" (string_of_num answer) in

(* example: prog 4 5 29 278 7 3 79 represents pi/4 = 5*atan(29/278) + 7*atan(3/79) *) let args = Sys.argv in let nargs = Array.length args in let v k = int_of_string args.(k) in let rec triples n =

 if n+2 > nargs-1 then []
 else (v n, v (n+1), v (n+2)) :: triples (n+3) in

if nargs > 4 then let dat = (v 1, triples 2) in verify dat else List.iter verify [

 (4,[(1,1,2);(1,1,3)]);
 (4,[(2,1,3);(1,1,7)]);
 (4,[(4,1,5);(-1,1,239)]);
 (4,[(5,1,7);(2,3,79)]);
 (4,[(5,29,278);(7,3,79)]);
 (4,[(1,1,2);(1,1,5);(1,1,8)]);
 (4,[(4,1,5);(-1,1,70);(1,1,99)]);
 (4,[(5,1,7);(4,1,53);(2,1,4443)]);
 (4,[(6,1,8);(2,1,57);(1,1,239)]);
 (4,[(8,1,10);(-1,1,239);(-4,1,515)]);
 (4,[(12,1,18);(8,1,57);(-5,1,239)]);
 (4,[(16,1,21);(3,1,239);(4,3,1042)]);
 (4,[(22,1,28);(2,1,443);(-5,1,1393);(-10,1,11018)]);
 (4,[(22,1,38);(17,7,601);(10,7,8149)]);
 (4,[(44,1,57);(7,1,239);(-12,1,682);(24,1,12943)]);
 (4,[(88,1,172);(51,1,239);(32,1,682);(44,1,5357);(68,1,12943)]);
 (4,[(88,1,172);(51,1,239);(32,1,682);(44,1,5357);(68,1,12944)])

]</lang>

Compile with

ocamlopt -o verify_machin.opt nums.cmxa verify_machin.ml

or run with

ocaml nums.cma verify_machin.ml
Output:
Testing: pi/4 = 1*atan(1/2) + 1*atan(1/3)
  tan(RHS) = 1
Testing: pi/4 = 2*atan(1/3) + 1*atan(1/7)
  tan(RHS) = 1
Testing: pi/4 = 4*atan(1/5) + -1*atan(1/239)
  tan(RHS) = 1
Testing: pi/4 = 5*atan(1/7) + 2*atan(3/79)
  tan(RHS) = 1
Testing: pi/4 = 5*atan(29/278) + 7*atan(3/79)
  tan(RHS) = 1
Testing: pi/4 = 1*atan(1/2) + 1*atan(1/5) + 1*atan(1/8)
  tan(RHS) = 1
Testing: pi/4 = 4*atan(1/5) + -1*atan(1/70) + 1*atan(1/99)
  tan(RHS) = 1
Testing: pi/4 = 5*atan(1/7) + 4*atan(1/53) + 2*atan(1/4443)
  tan(RHS) = 1
Testing: pi/4 = 6*atan(1/8) + 2*atan(1/57) + 1*atan(1/239)
  tan(RHS) = 1
Testing: pi/4 = 8*atan(1/10) + -1*atan(1/239) + -4*atan(1/515)
  tan(RHS) = 1
Testing: pi/4 = 12*atan(1/18) + 8*atan(1/57) + -5*atan(1/239)
  tan(RHS) = 1
Testing: pi/4 = 16*atan(1/21) + 3*atan(1/239) + 4*atan(3/1042)
  tan(RHS) = 1
Testing: pi/4 = 22*atan(1/28) + 2*atan(1/443) + -5*atan(1/1393) + -10*atan(1/11018)
  tan(RHS) = 1
Testing: pi/4 = 22*atan(1/38) + 17*atan(7/601) + 10*atan(7/8149)
  tan(RHS) = 1
Testing: pi/4 = 44*atan(1/57) + 7*atan(1/239) + -12*atan(1/682) + 24*atan(1/12943)
  tan(RHS) = 1
Testing: pi/4 = 88*atan(1/172) + 51*atan(1/239) + 32*atan(1/682) + 44*atan(1/5357) + 68*atan(1/12943)
  tan(RHS) = 1
Testing: pi/4 = 88*atan(1/172) + 51*atan(1/239) + 32*atan(1/682) + 44*atan(1/5357) + 68*atan(1/12944)
  tan(RHS) = 1009288018000944050967896710431587186456256928584351786643498522649995492271475761189348270710224618853590682465929080006511691833816436374107451368838065354726517908250456341991684635768915704374493675498637876700129004484434187627909285979251682006538817341793224963346197503893270875008524149334251672855130857035205217929335932890740051319216343365800342290782260673215928499123722781078448297609548233999010983373327601187505623621602789012550584784738082074783523787011976757247516095289966708782862528690942242793667539020699840402353522108223/1009288837315638583415701528780402795721935641614456853534313491853293025565940011104051964874275710024625850092154664245109626053906509780125743180758231049920425664246286578958307532545458843067352531217230461290763258378749459637420702619029075083089762088232401888676895047947363883809724322868121990870409574061477638203859217672620508200713073485398199091153535700094640095900731630771349477187594074169815106104524371099618096164871416282464532355211521113449237814080332335526420331468258917484010722587072087349909684004660371264507984339711