Write a function or complete program that takes a positive number
n and performs
n steps of an iterative algorithm for calculating π that has quadratic convergence (i.e. it approximately doubles the number of accurate digits at every iteration) then returns or prints out 2n correct digits (including the beginning 3). One such algorithm is the Gauss–Legendre algorithm, but you are free to use a different algorithm if you prefer.
1 → output
2 → output
5 → output
- Each iteration of the algorithm must perform a constant number of basic operations such as addition, subtraction, multiplication, division, power and root (with integer exponent/degree) - each such operation on "big" integer/decimal numbers is counted as one even if it involves one or more loops internally. To be clear, trigonometric functions and powers involving complex numbers are not basic operations.
- The algorithm is expected to have an initialization step which must also have a constant number of operations.
- If the algorithm needs 1 or 2 more iterations to get to 2n correct digits, you can perform up to
n+2iterations instead of just
- If it wasn't clear enough, after the correct 2n digits, your program must not print anything else (such as more correct digits, wrong digits or the complete works of Shakespeare).
- Your program must support values of
nfrom 1 to at least 20.
- Your program should not take more than an hour for
n=20 on a modern computer (not a hard rule, but try to keep it reasonable).
- The program must not obtain more than 20 accurate digits after the initialization and first iteration of the algorithm.
- The program must be runnable in Linux using freely available software.
- The source code must use only ASCII characters.
Straightforward code golf, shortest code wins.
The winner is Digital Trauma, I finally finished running his code on n=20 (just kidding). Special prize goes to primo for his very fast python solution and different algorithm :)