1

I came across an interesting Python exercise and tried to code it. I need to write a code that does the following (without the help of any libs or modules):

  1. Create the infinite series
     1 - 1/3 + 1/5 - 1/7 + ... 
  2. Perform the calculation:
     4*(1 - 1/3 + 1/5 - 1/7 + ...) 
  3. Perform N iterations until the absolute value of the difference between iteration n and n-1 is less than or equal to 0.00000000005, then return the calculated value.

My code goes as following:

def pi(n):
    a = [0]*n
    calc = [0]*n
    dif = 1
    while abs(dif) > 0.00000000005:
        for k in range(0,n):
            if k==0:
                a[k] = -((-1)**(k+1))*(1/(2*k+1))
                calc[k] = 4*sum(a)
            else:
                a[k] = -((-1)**(k+1))*(1/(2*k+1))
                calc[k] = 4*sum(a)
                dif = calc[k] - calc[k-1]
    return calc[k]

I probably have to call the function with n being a really big number, as I don't know when the difference will be <= 0.00000000005. Is there a way to perform it without setting a range or should I always start with a huge value for n? I still couldn't get any results so I don't know if my n isn't high enough and I'll get no result at all or if it's just a problem with memory.

4
  • You already have a loop with the while, you don't need another one with for. Commented Aug 20, 2021 at 3:46
  • Can the loop exceed the number of n epochs? If yes, you can remove the for block. Commented Aug 20, 2021 at 4:06
  • You don't need to store all n partial sums, only the previous and the current one. Commented Aug 20, 2021 at 4:35
  • This series is pretty slow to converge, though: be prepared to wait for a while. Commented Aug 20, 2021 at 4:43

4 Answers 4

1

I think it's possible to calculate that infinite series to within your specified tolerance without using much memory at all, but based on how you wrote your code, I'm not sure if you have more requirements I'm just missing. Anyway, here's my attempt:

import numba as nb # optional speedup

@nb.njit # optional speedup
def pi(tol = 5e-11):
   sign = 1
   denom = 1
   diff = 4/denom
   calc = diff
   while diff > tol:
       sign *= -1
       denom += 2
       diff = 4/denom
       calc += sign*diff
   return calc

The numba lines are optional and are just for making it run faster during testing. I know you're not allowed to use libraries, and the code will work without the lines.

Sign up to request clarification or add additional context in comments.

Comments

0

As I understand the problem, you don't really need to store all of the previous values, just to sum them up until the current value. Besides, the difference between the values of consecutive iterations is always the last value itself (at iteration n you just add the last value to the sum), Therefore it is sufficient to check if the absolute value of the last iteration is smaller than the threshold. Finally, you don't really need to limit your self to any value of N, as this is an infinite series, and this is definitely not a production code. (This is why using While True is suitable, although it is not considered as best practice). All these conclusions are leading to the following modified code:

def pi():
    result = 0  # holds the sum until the current iteration
    k = 0
    while True:
        a = 4 * (-((-1)**(k+1))*(1/(2*k+1)))
        result += a
        if abs(a) < 0.00000000005:
            return result

        k += 1

Comments

0

You can try defining your own class instead of range. As per your question on how to implement with no modules or library.

class Range(object):
  def __init__(self, last, first=0):
    self.first = first
    self.last = last

  def advance(self):
    self.first +=1

  def __next__(self):
    if self.first == self.last:
      raise StopIteration
    else:
      answer = self.first
      self.advance()
      return answer

  def __iter__(self):
    return self

def pi(n):
  # when you use arrays they take up lot of space in ram, as the list increases
  sum_ = 0
  prev = 0
  present = 0
  diff = 0
  while abs(diff) <= 0.00000000005:
    try:
      range_obj = Range(n)
      k = next(range_obj) # getting the first value
      while k < n:
        if k==0:
          sum_ += -((-1)**(k+1))*(1/(2*k+1))
          prev = 4 * sum_
        else:
          sum_ += -((-1)**(k+1))*(1/(2*k+1))
          present = 4*sum_
          diff = present - prev
        print("k value", k)
        print(diff)
        k = next(range_obj)
    except StopIteration:
      pass
  if present:
    # where k>0
    return present
  else:
    # only one value k = 0 
    return prev


print("final", pi(10))

Comments

0

The itertools module provides a number of types and functions for working with infinite series.

from itertools import count, accumulate, cycle
from operator import truediv

def pi(tol):
    last = 0
    for current in accumulate(map(truediv, cycle([4, -4]), count(1, 2))):
        if abs(current - last) < tol:
            return last
        last = current

You start with a series of fractions whose numerators alternate between 1 and -1 (4 and -4 if you account for multiplication by 4 immediately) and whose denominators are the odd natural numbers.

4/1, -4/3, 4/5, -4/7, ...

The approximations of pi are the partial sums of series.

4/1 = 4
4/1 - 4/3 = 2.666666...
4/1 - 4/3 + 4/5 = 3.46666...
4/1 - 4/3 + 4/5 - 4/7 = 2.8952380...

This series is known to converge slowly. On my machine, I see the following increase in running times:

pi(0.0000005)  # ~2 seconds
pi(0.00000005)  # ~7 seconds
pi(0.000000005)  # ~60 seconds
pi(0.0000000005) # ~660 seconds
pi(0.00000000005)  # ???, estimated 100 minutes

At this rate, I wouldn't hold my breath waiting for pi(0.00000000005) to complete.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.