[Exercise] Fibonacci sequence

Joe

Ok guys, new exercise.

This one involves logic, mathematics but also some knowledge of computer architecture. And unlike my first exercise (WordCount) this one is not tied to a single language.

Ok here goes the problem:

What is the result of F(100), where F is the Fibonacci sequence?

For those of you who aren't familiar with Fibonacci sequences, here's its definition:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

The goal of the exercise is to obtain the numerical result (of course), but also to show us the code that let you do it. You are free to choose any language you like.

Padre

good ol recursion !

int fib(int a)
{
    if (a < 2 ) return 1;
    return fib(a-1) + fib(a-2);
}

int main()
{
printf("Fib of 100 is: %i",fib(100));
}

didn't try the code, but that should be it.

arithma

Padre wrotegood ol recursion !

int fib(int a)
{
    if (a < 2 ) return 1;
    return fib(a-1) + fib(a-2);
}

int main()
{
printf("Fib of 100 is: %i",fib(100));
}

didn't try the code, but that should be it.

Shouldn't this explode?

Ayman

public static int fibo(int a)
{
   if((a==1) || (a==2))
     return 1; 
   else 
    return fibo(a-2) + fibo(a-1); 
}

public static void main(String[] args)
{
  System.out.println("Fibonacci of 100 is: " + fibo(100)); 
}

@rahmu, these problems are classics we all know from school, please give something more fun/challenging. Thanks :)

Joe

Ok guys, none of you has given me the final answer.

Padre's solution is taking ages to execute on my machine, I'm wondering if it's even computing anything at all. I don't even dare trying Java.

Ayman: F(2) = 2, and your solution goes crazy for F(0).

Finally there's no way F(100) is going to hold on an int.

Georges

This is what happens when you miss checking LebGeeks for LESS than 3 hours.
@Rahmu: Please, do not post the answer in less than (let's say) 8 hours!

Edit: I have another question: What is the largest value "n" for which Fib(n) is still computable :)

Joe

@Yorgi: I agree, apologize, and took my answer down.

However you should not think about it as THE only right answer. Padre and Ayman's solution (using recursive functions) is as correct, though incomplete.

The goal of these exercises is for each one of us to post his own code and get feedback for it. I simply happened to have worked on Fibonacci all afternoon, this is why I had this piece of code ready so fast.

Anyway, give it a try, we'll comment on your results :)

Ayman

You are right rahmu, the problem seemed classic to me on first sight. I will look into it more then and a different solution, also I will test before posting :)

arithma

*** SPOILER ALERT ***

#include <iostream>
#include <map>

using namespace std;

long long fibonacci(int input){
	if(input < 1) return 0;
	long long n1 = 0, n2 = 1;
	for(int i = 1; i < input; i++){
		long long next = n2 + n1;
		n1 = n2;
		n2 = next;
	}

	return n2;
}

void main(){
	cout << fibonacci(100) << endl;
}

The line "#include <map>" is a remnant of a failed attempt. Totally useless. I used a dynamic programming technique, but even that failed in front of the hideous combinatorial nature of the recursive definition.

eurybaric

OFF TOPIC: it would be good to have an option to hide/unhide a peice of code on lebgeeks. think it would make pages w a lot of code much clearer and would be very useful for hiding spoilers and the like.

Ayman

@arithma, I think your way being iterative is much better than being recursive, I was just writing something similar to yours right now. The recursive one would be expensive in time and would do lots of redundant work over and over again.

And I understand the inclusion of map in your code, you were trying to do it recursively and try to cache already found answers so that it wont do the work over and over again right? :)

arithma

*** SPOILER ALERT ***
Modified first example for memory congested systems (they have more ROM space than RAM).
Corrected my first attempt that was using dynamic programming.

using namespace std;

long long fibonacci(int input){
	if(input < 1) return 0;
	long long n1 = 0, n2 = 1;
	for(int i = 1; i < input; i++){
		if(i&0x1)
			n1 += n2;
		else
			n2 += n1;
	}

	if(input&0x1)
		return n2;
	else
		return n1;
}

long long fibonacci_dyn(long input){
	cout << "computing for " << input << endl;
	static map<long, long long> cache;
	if(input < 1) return 0;
	if(input == 1) return 1;
	if(cache.find(input) != cache.end())
		return cache[input];
	long long val = fibonacci_dyn(input - 2) + fibonacci_dyn(input - 1);
	cache[input] = val;
	return val;
}

void main(){
	cout << fibonacci(49) << endl;
	cout << fibonacci_dyn(49) << endl;
}

arithma

*** SPOILER ALERT ***

Keyword: Tail recursion.
Why not let the compiler optimize things for you! Tested on VS2010, should work on a recent gcc version as well:

long long fibonacci_rec(long long n1, long long n2, long input){ // input must be greater than 0
	if (input == 1) return n2;
	return fibonacci_rec(n2, n1+n2, --input);
}

void main(){
	cout << fibonacci_rec(0, 1, 49) << endl;
}

Padre

lol man it works :/ just tried it on small values (like 20 or 30).
true, should be int64 instead of int. for non recursive u could do smth like:

__int64 fib(int a)
{

	long i;
	__int64 b=1;
	__int64 c=1;
	__int64 k=1;
	for (i=2;i<=a;i++)
	{
		k=b+c;
		c=b;
		b=k;
	}
	return k;

}

if im correct, fib of 100 should be 1298777728820984005

arithma

There's one more solution I tried to crack down but the math is escaping me. The idea is to transform the problem into matrix exponentiation.
Given an initial vector (1 1), and the matrix M = (0 1; 1 1). We can compute fibonacci using M ^ n * v. Since matrix exponentiation is computationally expensive, (about as expensive as the above functions times a constant factor), we could diagonalize matrix M into L * D * L_inverse. M ^ n = L * D ^ n * L_inverse. Diagonal matrix exponentiation is logarithmic in cost (just the same as a scalar exponentiation).

Anyone has recently been doing university linear algebra and wants to help with this solution?

edit: This solution is already detailed on wiki, so forget it.. reading up.

Ayman

@Padre, Fibonacci 100 should give 354224848179261915075.

Padre

yh my code was overflowing, replaced with unsigned __int64 ... but all is correct till fib(93).

lol yeah, unsigned __int64 wont hold it. neither will long long )same thing :P

saeidw

For Fibonacci, tree recursion is a bad idea since you end up repeating the work for values you already calculated. A regular iteration is better.

In Common Lisp:

(defun fib (n)
 (defun fib-loop (a b m)
  (if (= m 0) b
      (fib-loop (+ a b) a (- m 1))))
 (fib-loop 1 0 n))

(fib 100)

@arithma: your cache method is probably the best solution when combined with tree recursion, it's clever!

arithma

I prefer best my tail recursion solution. I should have used some biginteger data type. The cache method is still algorithmically less efficient than the tail recursion or the iterative method. The tail recursion and the iterative method should ideally compile to the same machine/byte code.

Show your bigint data type! Should it be arbitrarily expandable? How tight is it? How performant is it? What benchmark should we use?

arithma

How about computing Fib(200)?