LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 September 22 2010

Joe
Member

[Exercise] Fibonacci sequence

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.

Offline

#2 September 22 2010

Padre
Member

Re: [Exercise] Fibonacci sequence

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.

Offline

#3 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

Padre wrote:

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.

Shouldn't this explode?

Offline

#4 September 22 2010

Ayman
Member

Re: [Exercise] Fibonacci sequence

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 :)

Last edited by Ayman (September 22 2010)

Offline

#5 September 22 2010

Joe
Member

Re: [Exercise] Fibonacci sequence

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.

Offline

#6 September 22 2010

Georges
Member

Re: [Exercise] Fibonacci sequence

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 :)

Last edited by Georges Raad (September 22 2010)

Offline

#7 September 22 2010

Joe
Member

Re: [Exercise] Fibonacci sequence

@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 :)

Offline

#8 September 22 2010

Ayman
Member

Re: [Exercise] Fibonacci sequence

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 :)

Offline

#9 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

*** 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.

Last edited by arithma (September 22 2010)

Offline

#10 September 22 2010

eurybaric
Member

Re: [Exercise] Fibonacci sequence

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.

Offline

#11 September 22 2010

Ayman
Member

Re: [Exercise] Fibonacci sequence

@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? :)

Offline

#12 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

*** 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;
}

Offline

#13 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

*** 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;
}

Offline

#14 September 22 2010

Padre
Member

Re: [Exercise] Fibonacci sequence

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

Last edited by Padre (September 22 2010)

Offline

#15 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

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.

Last edited by arithma (September 22 2010)

Offline

#16 September 22 2010

Ayman
Member

Re: [Exercise] Fibonacci sequence

@Padre, Fibonacci 100 should give 354224848179261915075.

Offline

#17 September 22 2010

Padre
Member

Re: [Exercise] Fibonacci sequence

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

Last edited by Padre (September 22 2010)

Offline

#18 September 22 2010

saeidw
Member

Re: [Exercise] Fibonacci sequence

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!

Last edited by saeidw (September 22 2010)

Offline

#19 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

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?

Offline

#20 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

How about computing Fib(200)?

Offline

#21 September 22 2010

Georges
Member

Re: [Exercise] Fibonacci sequence

You might find something weird about this code, but i got curious about the largest yet computable value of Fibonacci's series.

static void Main(string[] args)
{

    double i, a = 0, b = 1, sum = 0, numb;

    Console.Write("Please enter the value: ");
    numb = Double.Parse(Console.ReadLine());

    if (numb == 0) // Handles the Zero case.
    {
        Console.WriteLine("Fib {0} = 0", numb);
        Console.ReadKey();
    }
    else
    {
        for (i = 0; i < numb; i++)
        {
            sum = a + b;
            a = b;
            b = sum;

           // Get the maximum computable value of Fib. (which is 1475)
            if (sum.ToString().Equals("Infinity"))
            {
                Console.WriteLine("Maximum value of input is {0}", i);
                break;
            }
        }

        if (sum.ToString().Equals("Infinity"))
            Console.ReadKey();
        else
        {
            Console.WriteLine("Fib ({0}) = {1}", numb, sum);
            Console.ReadKey();
        }
    }
}

Offline

#22 September 22 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

double precission floating types have 52 bits of integral precision. That means that the number of integers a double can represent is significantly smaller than a 64 bit unsigned integer. You may be interested in reading up here: http://en.wikipedia.org/wiki/Double_precision_floating-point_format. Long story short, floating types are very bad when dealing with number theoretic problems. They have their uses for sure, but they're a huge liability in any solution they get into.

PS: Your solution will get out of precision long before it hits an overflow. This is precisely because floating types compromise precision for range.

Last edited by arithma (September 22 2010)

Offline

#23 September 22 2010

Joe
Member

Re: [Exercise] Fibonacci sequence

#include <stdio.h>
#include <stdlib.h>

long Fibonacci (long n);

long main (long argc, char* argv[])
{
    printf("%ld\n", Fibonacci(100));
    return 0;
}    

long Fibonacci (long n)
{
    /* Declaration */
    long i,a,b,sum;

    /* Initialization */
    a=0;
    b=1;
    sum=0;

    if (n == 0) /* Particular case of 0 */
    { 
        return 0;
    }
    else
    {
        /* Main loop */
        for (i=0;i<n;i++)  
        {
            sum = a + b;
            a = b;
            b = sum;
        }
        return sum;
    }
}

Here's my answer I had posted earlier. C code.

Padre wrote:

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

Having the same issues with double. Tomorrow I'll try using unsigned characters.

Offline

#24 September 22 2010

Joe
Member

Re: [Exercise] Fibonacci sequence

This code doesn't come from me, but is worth taking a look at:

#include <stdio.h>
#include <stdlib.h>

int fib(int i)
{
  int a = 1, b = 1, c = 1;
  switch(i%3)
    while(i > 3)
    {
       i-=3;
               b = a + c;  printf("%d\n", b);
       case 2: a = b + c;  printf("%d\n", a);
       case 1: c = a + b;  printf("%d\n", c);
       case 0: continue;
    }
  return c;
}

int main (int argc, char* argv[])
{
    printf("%d\n",fib(100));

    return 0;
}

doesn't solve the overflow issue. But is a worthwile implementation.

Offline

#25 September 22 2010

xterm
Moderator

Re: [Exercise] Fibonacci sequence

arithma has it spot on.

Here's my Haxed version with a twist.

Tools used: MonoDevelop, Mono Framework.
Execution time: Ridiculously fast, you can't even blink faster.

Cheats: BigInteger

using System;
using System.Linq;
using Mono.Math;

namespace FooBar
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			//354224848179261915075
			Console.WriteLine (Utils.Fib(100));
			
			//280571172992510140037611932413038677189525
			Console.WriteLine (Utils.Fib(200));
		}
	}
	
	class Utils {
		public static BigInteger Fib(int num){
			BigInteger a = 0;
			BigInteger b = 1;
			Enumerable.Range(1,num).ToList().ForEach( n => { a += b; BigInteger c = a; a = b; b = c; } );
			return a;
		}
	}	
}

Ruby, Python, Groovy and the lot could've done the same in one tenth the wording due to their MOP features and interpolation.

P.S.: For those of you that would like to test it, download Mono Develop, add the Mono.Security assembly to the project and run.[/i]

P.P.S.: For those of you with VS2010, .NET 4.0 comes with a BigInt i believe in System.CSharp.Math

Last edited by xterm (September 22 2010)

Offline

Board footer