CPSC 120 B

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

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.

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.