Computer programming - Homework 2

Please submit on by Wednesday 10pm of week 3.

1. Fibonacci numbers (see lab 2) A really inefficient way of computing Fibonacci numbers is by using the recurrence directly as given: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2.
Find a formula for the number of calls needed to compute Fn. What is the relation to the actual Fibonacci numbers? Confirm by writing a program that also prints something in the function.

2. Golden ratio The ratio between two consecutive Fibonacci numbers rn = Fn+1/Fn converges to a number called the golden ratio.
Write a function that computes this limit, stopping when the difference between two successive approximations is lower than 1e-6. How many approximations of the ratio are computed for this precision? Avoid wasteful recomputations of Fibonacci numbers, and the same approach to write a recursive function that computes Fn efficiently.

3. Taylor series Write functions that compute the Taylor series of cos and sin for a given value of x. Stop when the current term becomes smaller than a given value (e.g. 1e-6).

4. Fractals (optional) Adapt the program written in class to draw another fractal of your choice (Koch snowflake, Sierpiński carpet, Sierpiński triangle, dragon curve, Pythagoras tree, etc.)

Marius Minea
Last modified: Fri Oct 6 17:00:00 EEST 2017