[Exercise] Fibonacci sequence

Joe · 2010-09-22T14:27:06+00:00

Ok guys, new exercise. This one involves logic, mathematics but also some knowledge of computer architecture. And unlike my first exercise (WordCount) this...

Georges

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();
        }
    }
}

arithma

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.

Joe

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

Joe

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.

xterm

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

Ayman

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

dino

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?

Joe

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.

arithma

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

Joe

My bad, it was my definition of Fibonacci that is incorrect. I thought that F(0) = 1. Clearly I was wrong.

I stand corrected.

AxisFlame

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

Joe

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

AxisFlame

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

Joe

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

AxisFlame

thanks rahmu :D great explenation

new-user

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();
}

Joe

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

raja

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

Joe

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

NuclearVision

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

« Previous Page Next Page »