Computer programming - Lab 4

2. Write a function that computes the root of a given continuous function f in an interval [a, b] using the bisection method, assuming f(a) and f(b) have opposite signs. Compute f in the midpoint of the interval, and continue the process for the subinterval for which f changes sign.

3. The closed formula for the n^th term of the Fibonacci sequence is F_n = 1/√5(((1+√5)/2)ⁿ - ((1-√5)/2)ⁿ). Thus, the ratio of two consecutive Fibonacci numbers F(n)/F(n-1) converges to the golden ratio φ = (1+√5)/2 = 1.6180339887.... Compute the first value of n for which this ratio is accurate to 6 decimal digits.

4. A real number 0 < x < 1 can be successively approximated in a continued fraction with 1/a1, 1/(a1+1/a2), 1/(a1+1/(a2+1/a3)), ... where a1, a2, a3, ... are natural numbers. In the initial approximation, a1 is ⌊1/x⌋, and one continues using the same rule for the fractional part of the denominator approximated with a1, etc. One obtains a sequence of rational numbers p0/q0, p1/q1, p2/q2, ... that approximate x increasingly well, alternating from above and below. The following recurrences hold:
p_n+1 = a_n+1 * p_n + p_n-1 for n >= 0, with p_-1 = 1, p_0 = 0
q_n+1 = a_n+1 * q_n + q_n-1 for n >= 0, with q_-1 = 0, q_0 = 1
a) Write a program that for a given real number x between 0 and 1 computes the best continued fraction approximation of x for which the denominator does not exceed a given value. Print the answer both as sequence a1, a2, ... a_n and as ratio p_n/q_n .
b) Optionally, check that no rational number with smaller denominator is a better approximation.

5. Write a program that finds and prints phone numbers in a text read from input. A phone number is a sequence of the form (prefix)number, where the prefix has 4 digits, starting with 0, and the number has 6 digits, e.g. (0723)123456 .

6. Write a function that receives an unsigned number and using bitwise operators returns the number of ones in the binary representation of that number.

7. Write a function that receives an unsigned number and using bitwise operators tells whether the number is a power of two or not.

8. Write a generic function getbits(x, n, p) to retrieve right-adjusted n-bit field of x that begins at position p. Example: getbits(110110, 4, 3) = 101, getbits(110110, 1, 2) = 10 [taken from K&R]