1
\$\begingroup\$

I wrote code to calculate PI to a user specified number of decimal places. It works fine. I wanted to add a progress indication so that the user doesn't have to stare at a flashing cursor for hours on end with no indication of progress. I got something working but it makes the code much, much too slow. In the code below I have commented out the progress indicator section with a double line of ******'s before and after the "offending" piece of code. I suspect it is the log10 calculation that makes things too slow. Any suggestions:

# A program to calculate PI to a user specified number of decimal digits
# The program uses the Chudnovsky algorithm.  
# Further details on the algorithm are availabler here:
# https://en.wikipedia.org/wiki/Chudnovsky_algorithm

# A generator which divides the user requested number of decimal places into 10% increments

def ten_percent(places):

    for i in range(int(places/10),int(places+1),int(places/10)):
        yield i

def pi_calc(places):

    # places is user specified number of decimal places that should be calculated.

    import decimal
    import time
    import numpy as np
    start_time = time.time()

    decimal.getcontext().prec = places + 3

    # The function makes succesive calculations of PI using the algorithm.
    # The current calculated PI value is subtracted from the succesive PI value
    # If the difference is less than the 1 x 10**(-places) the result is returned

    # Initialise some variables

    current_pi = 3
    next_pi = 3
    precision = 1 * 10**(-places-3)
    counter = 1
    precision_step = ten_percent(places)
    precision_check = next(precision_step)

    # Initialise terms used in the itteration

    L = 13591409
    X = 1
    M = 1
    K = 6
    S = decimal.Decimal(M*L)/X

    next_pi = 426880*decimal.Decimal(10005).sqrt()/S

    # Perform the itterative calculation until the required precision is achieved

    while abs(next_pi - current_pi) > precision:
        current_pi = next_pi

        # Calculate the next set of components for the PI approximation

        L += 545140134
        X *= -262537412640768000
        M = M*(K**3-16*K)//(counter)**3
        S += decimal.Decimal(M*L)/X
        K += 12
        counter += 1

        # Calculate the next approximation of PI

        next_pi = 426880*decimal.Decimal(10005).sqrt()/S

#******************************************************************************************************************************
#******************************************************************************************************************************
# This progress indication slows the code down too much to be practical
#
#
#       # Give the user some feedback on progress of the calculation
#
#       # The try statement is required because the error between successive pi calculations can become
#       # "infintly" small and then a string is returned instead of a number.
#
#       try:
#           test_num = abs(round(np.log10(abs(decimal.Decimal(next_pi - current_pi)))))
#       except:
#           pass
#       
#       if test_num >= precision_check:
#           print('Calculation steps: ' + str(counter-1) + ' Approximate decimal places: ' + str(precision_check))
#           if precision_check < places:
#               precision_check = next(precision_step)
#*******************************************************************************************************************************
#*******************************************************************************************************************************

    return decimal.Decimal(str(next_pi)[:places+2])

# Get the required number of decimal places from the user and call the function to perform
# the calculation

while True:

    try:
        places = int(input('To how many decimal places would you like to calculate PI? '))
    except:
        print('Please provide a valid integer value.')
        continue
    else:
        break

calculated_pi = pi_calc(places) 
print('The value of PI to '+ str(places) + ' decimal places is:\n%s' % (calculated_pi))
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you done any profiling? Any timing numbers you could share? \$\endgroup\$ – User319 Oct 26 '18 at 20:31
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Feel free to post a follow-up question instead. \$\endgroup\$ – Mast Oct 29 '18 at 11:20
  • \$\begingroup\$ Sorry Mast. I was not aware. Thank you for pointing me in the right direction. I will correct accordingly. As far as I can tell you have deleted my update. I will proceed correctly now. \$\endgroup\$ – Adrian J G Oct 29 '18 at 14:24
  • \$\begingroup\$ I have decided to answer my own question because I don't really have a new question so posting a "new question" doesn't really make sense. On the other hand I think giving feedback could be of value to others. \$\endgroup\$ – Adrian J G Oct 29 '18 at 14:36
  • \$\begingroup\$ Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Toby Speight Oct 29 '18 at 15:26
1
\$\begingroup\$

This answers suggests various strategies for fixing performance. It does not consider other aspects of the code. It does not look at numerical analysis. (If there is a cheaper way to do the actual calculation to measure progress, that's not something I can tell you.)

First, this code goes through a lot of iterations. You know that most of the time you will not have hit the next progress marker. If you only check your progress every 100 times through the loop, you've reduced the time spent in this expensive operation to 1%. (You will lose accuracy for things that take fewer iterations, but for fast cases a progress bar is less important.)

Another option would be to compute the progress in a separate process. The main process could push the difference between next_pi and current_pi onto a stack, which the progress process could pop off whenever it finishes the last calculation.

Finally, you could estimate/lie. Graph running time (or number of iterations) vs number of digits. Is this a nice function? Then you can guess how long the computation like that will take up front, and base your progress on that. I am not a math person, so I have no idea if this is practical. If not, maybe it can get you thinking in a better direction.

\$\endgroup\$
  • \$\begingroup\$ Thank you User319. I have followed your advise and made some edits. I will put an update in a new response below. \$\endgroup\$ – Adrian J G Oct 29 '18 at 11:06
0
\$\begingroup\$

So based on feedback from User319 I modified the code to only do the progress calculation at selected intervals.

  • Firstly, no progress indication for less than 5000 decimal places on the basis that this calculation runs fast enough not to require update.
  • Calculation carried out at intervals based on observation of how many calculation cycles it took to calculate a certain number of decimal places.

With the changes I measured the following:

  • Calculating to 5000 decimal places with no user feedback took 7.63 seconds
  • Calculating to 5000 decimal places with new feedback method 41.76 seconds
  • Calculating to 5000 decimal places with old feedback method over 1400 seconds

So a dramatic improvement but still a slowdown to indicate progress. In the code below I have commented out the new method of calculating progress. I subsequently did some more work and eliminated the need to calculate the logarithm which I believe was the major reason for the code slow down. I have implemented a progress indicator using strings to determine how many decimal places have been calculated. This performs much better and actually had very little to no impact on the calculation time. The code below includes this method.

Finally I have subsequently realised that because I set the precision for Decimals equal to the number of decimal places I want to calculate from the beginning of the calculation; specifying more decimal places slows the calculation down form the very first step. I will now investigate changing the precision as the calculation progresses so that higher precision doesn't slow down early steps in the calculation.

Here is the code:

# A program to calculate PI to a user specified number of decimal digits
# The program uses the Chudnovsky algorithm.  
# Further details on the algorithm are availabler here:
# https://en.wikipedia.org/wiki/Chudnovsky_algorithm

# A generator which divides the user requested number of decimal places into 10% increments

def ten_percent(places):

    for i in range(int(places/10),int(places+1),int(places/10)):
        yield i

# A function which takes in a string representation of a decimal and finds the first non-zero
# digit in the string.

def first_non_zero(input_string):

    current_x = input_string.find('1')
    new_x = 0

    for i in range(2,10):
        new_x = input_string.find(str(i))
        if new_x != -1 and new_x < current_x:
            current_x = new_x

    return current_x

def pi_calc(places):

    # places is user specified number of decimal places that should be calculated.

    import decimal
    import time
    import numpy as np
    start_time = time.time()

    decimal.getcontext().prec = places + 3

    # The function makes succesive calculations of PI using the algorithm.
    # The current calculated PI value is subtracted from the succesive PI value
    # If the difference is less than the 1 x 10**(-places) the result is returned

    # Initialise some variables

    current_pi = 3
    next_pi = 3
    precision = 1 * 10**(-places-3)
    counter = 1
    precision_step = ten_percent(places)
    precision_check = next(precision_step)

    # Initialise terms used in the itteration

    L = 13591409
    X = 1
    M = 1
    K = 6
    S = decimal.Decimal(M*L)/X

    next_pi = 426880*decimal.Decimal(10005).sqrt()/S

    # Perform the itterative calculation until the required precision is achieved

    while abs(next_pi - current_pi) > precision:
        current_pi = next_pi

        # Calculate the next set of components for the PI approximation

        L += 545140134
        X *= -262537412640768000
        M = M*(K**3-16*K)//(counter)**3
        S += decimal.Decimal(M*L)/X
        K += 12
        counter += 1

        # Calculate the next approximation of PI

        next_pi = 426880*decimal.Decimal(10005).sqrt()/S

        # Give the user some feedback on progress of the calculation

        if places >= 5000 and counter%int(places/1000*7+1) == 0:

            # This section is the slow method that is replaced with the string method below.
            # try:
            #   test_num = abs(round(np.log10(abs(decimal.Decimal(next_pi - current_pi)))))
            # except:
            #   pass

            test_num = abs(decimal.Decimal(next_pi - current_pi))
            test_string = '{0:f}'.format(test_num)
            test_num = first_non_zero(test_string)

            if test_num >= precision_check:
                print('Calculation steps: ' + str(counter-1) + ' Approximate decimal places: ' + str(precision_check))
                if precision_check < places:
                    precision_check = next(precision_step)      

    end_time = time.time()
    print(str(end_time-start_time))
    return decimal.Decimal(str(next_pi)[:places+2])

# Get the required number of decimal places from the user and call the function to perform
# the calculation

while True:

    try:
        places = int(input('To how many decimal places would you like to calculate PI? '))
    except:
        print('Please provide a valid integer value.')
        continue
    else:
        break

calculated_pi = pi_calc(places) 
print('The value of PI to '+ str(places) + ' decimal places is:\n%s' % (calculated_pi))
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.