Fibonacci Numbers

Continuing reading the SICP book...

In every book about algorithms I have read there is always a chapter about the Fibonacci numbers. Mainly on the different algorithms of calculating the n-th Fibonacci number and comparing their order of growth. First comes the algorithm, based on definition:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

This function is good at explaining tree recursion, but is awful for calculating Fibonacci numbers, as it makes too many unnecessary calculations. The order of growth is Θ(Fib(n)), which means exponential. The next comes iterative funcion, which solves the task much better, using less resources and time. Its order of growth is Θ(n) - linear.

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
     b
     (fib-iter (+ a b) a (- count 1))))

But there is also an algorithm that calculates Fibonacci number with Θ(log n) complexity. There, in the book they give you the function with gaps and some pointers ( no C here :) ), how to fill them.

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   [??] calculate p'
                   [??] calculate q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

The authors remind us of the transformation of the state variables a and b in the previous (iterative) fib-iter procedure: a ← a + b and b ← a. Provided these state changes are labeled transformation T, applying T repeatedly for n iterations starting with a = 1 and b = 0 will produce the pair a = Fib(n + 1) and b = Fib(n). So the Fibonacci numbers are produced by the n^th power of the transformation T (Tⁿ), starting with the pair (1, 0).

Now consider the family of transformations T_pq which transforms the pair (a, b) according to the following rules:

a ← bq + aq + ap
b ← bp + aq

Where transformation T is just a special case of T_pq, where p = 0 and q = 1. Now it's up to you to find the transformation T_p'q' such so, if we apply T_pq twice, the effect is the same as using a single transformation T_p'q' of the same form. Compute p' and q' in terms of p and q and put into the function.

I will not provide the solution here, in case you want to handle it yourself. But if you are eager to see the result, visit some other blog that has the solution. :)

Structure and Interpretation of Computer Programs

Recently we decided to read the "Structure and Interpretation of Computer Programs" book through. And not just read it, but also to complete the exercises, given after each chapter. On Friday we had a first meeting, concerning the first chapters we read.

As a working environment the Racket was chosen. It turned out to be a very powerful instrument: not just the language and it's interpretor, but almost a complete IDE with autocomplete, unit tests and even debugging.

That is how errors are shown in Racket. Yes, these arrows are cute.

The meeting was nice and quite productive. We shared some solutions to exercises, and also some were solved just in place. We learned that

(A 2 6)

is a very big number :), where

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

P.S. Thanks Anton for the picture :)

C# Function That Mimics SQL IN-operator

A good question was asked on stackoverflow, and an even better answer received.

How can we rewrite the condition

if (a == x || a == y || a == z)

to make it more readable?

The answer is

public static bool IsIn<T>(this T obj, params T[] collection) {
   return collection.Contains(obj);
}

if (a.IsIn(x, y, z))

PS. Sorry for such a long period with no posting. You know, summer, Sun, beach, sea, +30 and vacation.