4
\$\begingroup\$

I found a simple series named the Lebniez series for finding Pi.

$$1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \dots = \frac{\pi}{4}$$

I made this in Python. I then realised that because it is an infinite series, and it will give an approximation. Additionally the convergence rate is very slow.

Here is the program I made after learning about series acceleration through the Shank Transform:

def lebniez(n):
    pi = 0
    n = n + 1
    for i in range(1,n):
        if(i % 2 == 1):
            pi -= 1 / (2*i - 1)
        else:
            pi += 1/(2*i - 1)
    pi = abs(4 * pi)
    return pi

def accelrate(n,depth):
    if depth == 1:
        a = lebniez(n + 1)
        b = lebniez(n)
        c = lebniez(n-1)
        return (a*c - b*b)/(a + c - 2*b) 
    a = accelrate(n + 1,depth - 1)
    b = accelrate(n,depth - 1)
    c = accelrate(n-1,depth - 1)
    return (a*c - b*b)/(a + c - 2*b)

I have applied the shank transformation and gotten a new series. After this I continuously apply it recursively. However using recursion has made it very slow. If I keep accelerating the function then after some depth the accuracy starts decreasing.

\$\endgroup\$
4
\$\begingroup\$

Repeated computations

Part of the reason it is slow is that a lot of the computations are repeated many times. For example, if you diagram the calls for accelrate(3,3) you get something like this (where A is a call to accelrate and L is a call to lebniez):

                                                                A(3,3)
                                                                   | 
                      +--------------------------------------------+--------------------------------------------+
                      |                                            |                                            |
                   A(4,2)                                       A(3,2)                                       A(2,2)
                      |                                            |                                            |
       +--------------+--------------+              +--------------+--------------+              +--------------+--------------+
       |              |              |              |              |              |              |              |              |
    A(5,1)         A(4,1)         A(3,1)         A(4,1)         A(3,1)         A(2,1)         A(3,1)         A(2,1)         A(1,1)
       |              |              |              |              |              |              |              |              |
  +----+----+    +----+----+    +----+----+    +----+----+    +----+----+    +----+----+    +----+----+    +----+----+    +----+----+
  |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
L(6) L(5) L(4) L(5) L(4) L(3) L(4) L(3) L(2) L(5) L(4) L(3) L(4) L(3) L(2) L(3) L(2) L(1) L(4) L(3) L(2) L(3) L(2) L(1) L(2) L(1) L(0)

Notice the repeated calls, like A(4,1) or L(3).

If you were to do this for accelrate(6,6) you would find that lebniez(6) is called 114351 times and there are 591,219 total calls to lebniez(). Also, there 41,361 calls to accelrate(6,1) and a total of 295,204 recursive calls to accelerate().

cache computations

One way to address repeated computations is to use a cache to save previous computations. For example, cache the computation of A(3,1) the first time it is called and reuse it in later computations. functools.lru_cache() can be used like so:

import functools as ft

@ft.lru_cache(maxsize=32)
def lebniez(n):
    pi = 0
    n = n + 1
    for i in range(1,n):
        if(i % 2 == 1):
            pi -= 1 / (2*i - 1)
        else:
            pi += 1/(2*i - 1)
    pi = abs(4 * pi)
    return pi

@ft.lru_cache(maxsize=128)
def accelrate(n,depth):
    if depth == 1:
        a = lebniez(n + 1)
        b = lebniez(n)
        c = lebniez(n-1)
    else:
        a = accelrate(n + 1,depth - 1)
        b = accelrate(n,depth - 1)
        c = accelrate(n-1,depth - 1)

    return (a*c - b*b)/(a + c - 2*b)

Numerical stability

Your second question has to do with the stability of numerical calculations (an entire field of its own). Basically, most calculations on a computer have limited precision (i.e., number of bits) which can cause problems. This article on Floating-point Arithmetic explains it better than I could. Check out the example of computing pi at the end.

Also, this article on the Shanks transformation says the expression you are using, (a*c - b*b)/(a + c - 2*b), is less numerically stable than another expression for the transform, a - (a-b)**2/((a-b)-(b-c)).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Don't know if you saw this message from Dhaval Bothra. "Hello I am brother of Coder B . I wanted to say thanks for this Answer to Root Two. Sorry I could not comment but a Big THANKS FOR ANSWERING" \$\endgroup\$ – Peilonrayz Aug 2 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy