< Back

Lab 13: Accumulator

As usual, create a directory to hold today's files. All programs that you write today should be stored in this directory. 

$ cd ~/cs120/labs
$ mkdir lab13 
$ cd lab13

Practice Problem 1

Write a function rational_sum(n) which returns the sum of the rational numbers \(\frac{1}{n}\):

\[ rational\_sum(n) = \sum_{i = 1}^{n} \frac{1}{i} = \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n} \] 









  
Practice Problem 2




  Write a function factorial(number) which returns the
  factorial
  of the specified number.  The factorial of a number \(n\) can be
  computed
  using the equation:



$$n! = n \times (n - 1) \times \ldots \times 1$$



  NOTE: Do not use the math module in this practice
  activity.




  

    
  

  

    
  

  








Fibonacci



  The Fibonacci sequence is a sequence of numbers that looks like:


  $$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,
  1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,
  196418, 317811, 514229, 832040, \ldots$$




  Each number in the sequence, after the first two, is the sum of the
  previous two numbers in the sequence.




Details



  In Emacs create a Python program in a file
  called fibonacci.py that prints the Fibonacci sequence.  The
  program should prompt the user to enter the length of the series to
  print.




Example


$ python3 fibonacci.py
enter the sequence length: 8
1 1 2 3 5 8 13 21




Hint



  
  

    
    
      
  • 
        Because the program should work for any length sequence, you
        will need a loop to compute each of the numbers in the
        sequence.
      
    • 
      
  • 
        What is different between this and other uses of an
        accumulator is that it needs the previous two iterations to
        compute the next iteration.  To do this, keep two variables,
        one for the previous value and one for the one before the
        previous.
      
    • 
      
  • 
        Pay attention to how the program will work for small numbers.
        If the user enters 1, the loop should run 0 times and print 1.
        If the user enters 2, the loop should run 1 time.  But what
        are the two previous values when computing the second number
        in the sequence?  Hint: 0 and 1.
      
    • 
    

  






  
Challenge

  

    The values of the Fibonacci sequence can be used to draw an
    approximation of a golden spiral.  The values of the sequence are
    the area of squares arranged in a spiral pattern with each square
    containing a quarter circle.  Use turtle graphics to draw a
    Fibonacci spiral.
  

  Fibonacci Spiral





Leibniz Approximation



  The mathematical constant π is an irrational number that represents the
  ratio between a circle's diameter and its circumference.  The first algorithm
  designed to approximate π was developed by Archimedes in 250 BC, and was
  able to approximate its value within 3 significant figures.  Today we know
  that there are an infinite number of digits in π, so lets use a little
  more sophisticated approach to estimate its value.



Details



  Create the function estimate_pi(duration) in a file
  called leibniz.py. This function takes an integer as a
  parameter, which is the number of terms to compute in the infinite series.  It should
  use this parameter to compute the Leibniz approximation, discussed below.





  The Leibniz approximation relies on the fact that:





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





  Which can be rewritten to approximate the true value of π:





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






  Make sure to test your function by calling the function multiple
  times with different parameters.  Make sure your code follows the
  course's code conventions.



Test Cases



  
    

      Function Parameters
      Expected Output
    

  
  
    

      0
      0
    

    

      1
      4
    

    

      10
      3.0418396189294032
    

    

      100
      3.1315929035585537
    

    

      1000
      3.140592653839794
    

  



Hint



  
  

    
    
      
  • 
	You will need a for loop that uses the accumulator pattern to
	accomplish this goal.  Create a variable (defaulted value to 0) before
	the for loop.  Then you just need to update the value of the variable inside the for loop.
      
    • 

      
  • 
	As you progress through your for loop, the denominator of your
	fraction increases by a factor of two.  Some simple algebra will
	reveal that during loop iteration i, the denominator is:
	$$(2 \times i) + 1$$
      
    • 

      
  • 
	You need to alternate adding and subtracting.  However, subtracting is
	the same as adding a negative number.  So we can accomplish this by
	multiplying every other fraction by -1.  The easy way to do
	this is to compute:
	$$-1^{i}$$
	Where \(i\) is your loop variable.
      
    • 

      
  • 
	The accumulator be the sum of all of the terms in the sequence, so you
	only need to add one term to the accumulator during each loop iteration.
      
    • 
    

  






  
Challenge

  

    The value you get from the Leibniz formula will be incredibly
    close.  However, it will never meet the true definition of π.
    To see how close it does get, compute the approximations
    for all equations from length 1 to length
    1000.  For each approximation, subtract the value
    of math.pi from it to compute the error.  Sum up all
    of these errors, and print the average error.