Why do two codes that calculate pi using the same algorithm have different running times?

user_18239939 0
Viewed 73

The Wallis formula is also used to calculate PI. Why are the running times of the two methods so different？

The link to the formula is http://en.wikipedia.org/wiki/Wallis_product

Thank you so much! The following code:

from __future__ import division 
import time
# Method 1
T1 = time.perf_counter()
pi = 3.14159265358979312
my_pi = 1. 
for i in range(1, 100000):
    my_pi *= 4 * i * i / (4 * i * i - 1.)
my_pi *= 2
T2 = time.perf_counter()
print(pi)
print(my_pi)
print(abs(pi - my_pi))
print("Running time:", T2-T1)

# Method2
T3 = time.perf_counter()
num = 1
den = 1
pi = 3.14159265358979312
for i in range(1, 100000):
    tmp = 4 * i * i
    num *= tmp
    den *= tmp - 1

better_pi = 2 * (num / den)
T4 = time.perf_counter()
print(pi)
print(better_pi)
print(abs(pi - better_pi))
print("The error between the two results:", abs(my_pi - better_pi))
print("Running time:", T4-T3)

The following output

3.141592653589793

3.141584799578707

7.854011085939305e-06

Running time: 0.04233423100001232

3.141592653589793

3.1415847995787067

7.854011086383395e-06

The error between the two results: 4.440892098500626e-16

Running time: 23.963929412
time-complexity python
1 Answers

The second version only uses integers, which are implemented as BigNums, hence much much slower. This is total overkill, unless you hope for huge accuracy (but this is completely hopeless given the very slow convergence of Wallis).

By adding this in the loop

if i & 15 == 0:
    den= math.frexp(den)[0]
    num= math.frexp(num)[0]

here is the output:

3.141592653589793
3.141584799578707
7.854011085939305e-06
Running time: 0.033463999999999994
3.141592653589793
3.1415847995786645
7.85401112857187e-06
The error between the two results: 4.263256414560601e-14
Running time: 0.0331592
user_11965490
Related