• Coding
  • [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();
        }
    }
}
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.
#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 wroteyh 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
Having the same issues with double. Tomorrow I'll try using unsigned characters.
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.
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
Nice method xterm I really like it.

A standard recursive implementation would be doing lots of unnecessary and repetitive work so I was thinking if we could cache answers into an array or list, also using BigInteger in java.

And here is what I got:
import java.math.BigInteger; 
import java.util.Map; 
import java.util.HashMap; 

public class Fibo
{

	public static BigInteger fibo(int a)
	{
		return new Object()
		{
			Map cache = new HashMap();
			BigInteger compute(int b)
			{
				for(int i = 0; i <= b; i++)
					cache.put(i,fibo(i));
					
					return (BigInteger)cache.get(b); 
			} 
				
			BigInteger fibo(int b)	
			{
				if(b == 0)
					return new BigInteger("0"); 
				
				else if(b <= 2)		
					return new BigInteger("1"); 
				else 
				{
					return ((BigInteger)cache.get(b-1)).add((BigInteger)cache.get(b-2));
				}		
			}
		}.compute(a); 		

      public static void main(String[] args)
      {
		// 354224848179261915075
		System.out.println("fibonacci for 100: " + fibo(100)); 
		
		// 280571172992510140037611932413038677189525	
		System.out.println("for 200: " + fibo(200));
		
		// 222232244629420445529739893461909967206666939096499764990979600 	
		System.out.println("for 300: " + fibo(300));	
			
		                                       //176023680645013966468226945392411250770384383304492191886725992896575345044216019675
		System.out.println("for 400: " + fibo(400));	
	}
	
	}
}
EDIT: Each of these results took around 16 milliseconds to compute, time not 100% precise though :)
tried the first code and as expected this is it.. using javascript and firebug
function fib(a)
{
if (a < 2) return 1;
return fib(a-1) + fib(a-2);
}


Any other challenges.. tougher stuff?
arithma wrote
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(){
       // Rahmu correction: changed first argument to 1.
	cout << fibonacci_rec(1, 1, 49) << endl;
}
Corrected a small error in main function. Output was giving fib of n-1. Anyway, I think this is the most clever recursion implementation. I will test it on very large numbers.
@rahmu: F(0) = 0, F(1) = 1. This is the definition of the series. By my definition, the above function calculates F(2) = 1, F(3) = 2, F(4) = 3 correctly. It also agrees with the other functions I have written.
My bad, it was my definition of Fibonacci that is incorrect. I thought that F(0) = 1. Clearly I was wrong.

I stand corrected.
a year later
I just started programming, and i thought i would try this so here is mine in python
fib = (0, 1)
fib = list(fib)
n = 0
for i in range (99):
    n = fib [i] + fib [i + 1]
    fib.append(n)
print (fib[100])
the one-hundredth fibonacci number is...

354224848179261915075
AxisFlame, congrats!

A few remarks:

fib = (0, 1)

Why start with a tuple? Wouldn't it be easier to start with a list directly? It will save you the trouble of converting later. You also don't need to initialize n to 0.

Here's a simplified version of your code, it does the exact same thing but with fewer lines:
s = [0, 1]

for i in range(2, 200):
    s.append (s[i-1] + s[i-2])

print s
rahmu wroteAxisFlame, congrats!

A few remarks:

fib = (0, 1)

Why start with a tuple? Wouldn't it be easier to start with a list directly? It will save you the trouble of converting later. You also don't need to initialize n to 0.

Here's a simplified version of your code, it does the exact same thing but with fewer lines:
s = [0, 1]

for i in range(2, 200):
    s.append (s[i-1] + s[i-2])

print s
thanks!! appreciate your help, i still do not get what the difference between list and tuple is...

and for the n, i am just used to initializing to 0
tuples are immutable, which means you cannot change them once they are created. You should definitely use a tuple instead of a list, every time you can. Simply because tuples are lighter objects than lists.

The most common example I give is this one:
('Jan', 'Feb', 'Mar', 'April', 'May', 'Jun', 'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec')
If you ever need this, it would be a shame to use a list, because tuples are so much lighter and faster. This tuple is definitely no going to change any time soon ;)
thanks rahmu :D great explenation
2 months later
F(0)=1F(0)+0F(1)
F(1)=0F(0)+1F(1)
F(2)=1F(0)+1F(1)
F(3)=1F(0)+2F(1)
F(4)=2F(0)+3F(1)
and so on......
_________
Im new to programming and i work on c so here's what i ended up with
#include<stdio.h>
#include<conio.h>
void main()
{
  int a=1,b=0,c,f0,f1,fn,i,n;     /*n is the nth term the user wants*/
  scanf("%d%d&d" ,&n,&f0,&f1);    /*the user enters nth 0 term and 1 term respectively*/
  for(i=0 ; i<n ; i++)
  {
    c=a;
    a=b;
    b=c+b;
  }
  fn=(a*f0)+(b*f1);
  printf("%d" ,fn);
  getch();
}
Hello and welcome to Lebgeeks!

I have a few remarks concerning the style of your writing:

- Since the requirements already stated it's a Fibbonacci sequence, you can assume that 0term == 0 and 1term == 1. Filling them with a scanf seems weird.

- I tend to write separate functions that I call from the main. Not only is this general good practice, but it also helps others re-use the code your produce more easily. And it also provides a more straight up answer to the exercise (you should have a int fibbonacci (int x) somewhere).

- You should name your variables in a more expressive way; it's such a short program yet I'm already confused by the naming scheme. A good naming convention should completely replace the comments.

I really liked your early representation of F(x), so I wrote a small piece of recursive code based on it.
F(x) = A*F(0) + B*F(1)
class fibtuple:
    ''' fibtuple is a representation of F(x) following:
    F(x) = A * F(0) + B * F(1). It can be  represented as a tuple (A, B)'''

    def __init__(self, x):
        if x == 0:
            self.A, self.B = 1, 0
        elif x == 1:
            self.A, self.B = 0, 1
        else:
            self.A = fibtuple(x-1).B
            self.B = self.A + fibtuple(x-1).A

def Fib(x):
    ''' The real value should be F(0) * A + F(1) * B
    but F(0) == 0, allowing us to write the simple following'''
    return fibtuple(x).B
14 days later
This is how I usually do fibonacci:
def F(n):
    a = 0
    b = 1
    for i in range(n):
        a,b = b,a+b
    return a
This is the one-liner equivalent:
F = lambda n : reduce(lambda a,dummy: (a[1],sum(a)), [(0,1)] + range(n))[0]
Some output:
>>> map(F, [0, 1, 2, 3, 100, 200])
[0, 1, 1, 2, 354224848179261915075L, 280571172992510140037611932413038677189525L]
PS: I have some code lying around somewhere that uses gmp to compute really large values of the fibonacci sequence in C. At the time I wrote it, I tested 3 versions of the same code C/gmp python/int and Java/BigInteger. As far as speed goes, taking the C implementation as reference, they ran something like this(more is worse):
C/gmp: 1x
python/int: 2x
Java/BigInteger: ~4x

I don't know if the java bigint implementation has improved since, but apparently the default int class of python is pretty damn performant
3 months later
I'm learning Lua and I wanted to keep this somewhere.
function fibiter (n, count, total, last)
   if n == 0 or n == 1 then return n
   elseif count and count > n then return total
   else
      local count = count or 2
      local total = total or 1
      local last = last or 0
      return fibiter(n, count+1, total+last, total)
   end
end
Also the Lua interpreter had no problem computing (a rounded value of) the large number:
>= fibiter(100)
3.5422484817926e+20
>= fibiter(100) == fibiter(100) -1
true
print(fibiter(100))
3 months later
#Python

from math import sqrt
phi = (1+sqrt(5))/2
psi = (1-sqrt(5))/2
def F(n):
    return (phi**n-psi**n)/(phi-psi)
F(100)