Computer programming - Lab 2

Review and preparation

Fibonacci numbers 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.

Proposed problems

If any questions remain about these problems, please ask during office hours. Numbers as sequence of digits (for Problems 1 - 3). A nonnegative decimal number (i.e., in base 10) can be viewed recursively as either a single digit, or a number followed by a digit (we single out the last digit rather than the first since the two parts are computable as quotient and remainder modulo 10).

1. Most significant digit
Write a recursive function that returns the first (most significant) digit of a number when written in base 10.

2. Selecting digits Write a function that takes an unsigned number n and returns a number formed by some of the digits of n, e.g.: all digits on even positions / odd positions, all digits with a given property (odd/even/greater than 5, etc.)
Hint: Review the reversal of digits, done in class. Here, you won't use all digits. If you don't reverse, you don't need an accumulator and can directly construct the number using the result of the recursive call.

3. Changing the base Write a function that given a natural number computes the value resulting from the digits of its decimal representation when interpreted as a hexadecimal number. Example: f(312) = 3 * 256 + 1 * 16 + 2 = 786
Hint: use the same recursive decomposition, but when reconstructing the number, use the new base (16).

Limits and approximations

4. Function root. Write a recursive function that computes a root of a given continuous function f in an interval [a, b] with a given precision using the bisection method, assuming f(a) and f(b) have opposite signs.
How to do it:
If the interval length does not exceed the required precision for the root (say, 10-6, which can be written 1e-6), we can return as answer any point from the interval (a, b, the midpoint, etc.).
Otherwise, compute f in the midpoint of the interval, (a+b)/2. If f(a) * f((a+b)/2) ≤ 0 (the function changes sign), find the root by calling the function recursively on the left half-interval. Otherwise, there must be a root in the right half [(a+b)/2, b], so recursively find the root in that interval.
Why this works
Denote m = (a+b).2. We prove by contradiction that f(a) * f(m) ≤ 0 or f(m) * f(b) ≤ 0 (or both).
If both were > 0, by multiplication we'd get f(a) * f(m)2 * f(b) > 0. We divide by f(m)2 which must be strictly positive, since the entire product is, and we get f(a) * f(b) > 0 contrary to the problem statement that they have opposite signs.
Note that we do not need a zero check for the endpoints nor the midpoint, the reasoning above shows that the chosen checks suffice.

5. Series Write functions that compute the value of a given series.
a) Compute the value of 1/12 + 1/22 + ... + 1/n2 for some large n. Write versions that start to add from each of the ends. What is the difference in writing the recursion? Is there a difference in the result?
b) Write functions that compute the Taylor series for ex, cos, and sin (for a given value of x). Stop when the current term becomes smaller than a given value (e.g. 1e-6).
Hint: pass the sum computed so far as one of the arguments. To avoid wasteful computation, you may also pass the current term as one of the arguments, and compute the next term starting from the current term.

6. Limit Write a function that computes with a given precision (say, 1e-6) the limit of the sequence xn+1 = f(xn) (assuming it exists), with x0 and f given.
Your program should define a suitable f as a separate C function, for example f(x) = √x+2, with x0 some nonnegative number of your choice ≥ -2.
(Later we will learn how a pointer to f could be passed to the limit function.)
A value for which f(x) = x (which you are asked to compute) is called a fixpoint of the function (applying f results in the same value).
Use this approach to compute values of infinite terms, such as 1/(a+1/(a+1/(... + 1/a))) or √a+√a+ ...√a (for given values of a).
Hint: find the function f that transforms the term with n occurrences of a into the term with n+1 occurrences.

7. Fractals Write a program, similar to the one done in class, that draws the Koch curve, as described here.
The curve can be drawn without lifting pen from paper, so there is no need to issue commands to move the cursor, each segment starts from where the other left off. Segments have different orientation: the two central of four subfigures are tilted clockwise and counterclockwise with π/3 with respect to the orientation of the enclosing larger figure. Thus, a figure will have size and orientation (angle) as parameters.

8. Modular exponentiation If p is a prime number, and a is not divisible by p, the sequence a, a2, a3, ... eventually reaches 1 when computed modulo p (i.e., we take the remainders when dividing by p).
For example, let p = 7, and a = 4. Then a2 = 16 ≡ 2 (mod 7), and a3 = a2 * a ≡ 2 * 4 ≡ 1 (mod 7).
Write a function that takes as parameters an unsigned number p (assumed to be prime, no check needed) and an unsigned number a and returns 0 if p divides a, or else the smallest number n such that an ≡ 1 (mod p).
Hint: accumulate and pass as arguments the current exponent k and ak, until you reach 1 (mod p).

9*. Counting change Write a recursive function that returns the number of ways in which a natural number can be written as a sum of ones, twos and threes, irrespective of order.
Example: 5 can be written in 5 ways: 1 + 1 + 1 + 1 + 1 , 1 + 1 + 1 + 2 , 1 + 2 + 2 , 1 + 1 + 3 , and 2 + 3.
Hint: We can either use a value of 3 in the sum or not. The number of combinations will be the sum for both cases. If we use a value of 3, we are left with n - 3, and have to count all ways to write it (same problem, smaller n). If we do not use 3, we must write n using only ones and twos (we can write another function for this simpler problem, reasoning the same way about the value 2).
Does the function perform wasteful computation ? Generalize for three arbitrary values instead of 1, 2, and 3.

Marius Minea
Last modified: Fri Oct 6 7:50:00 EEST 2017