LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#26 September 23 2010

Ayman
Member

Re: [Exercise] Fibonacci sequence

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

Last edited by Ayman (September 23 2010)

Offline

#27 September 23 2010

dino
Member

Re: [Exercise] Fibonacci sequence

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?

Offline

#28 September 23 2010

Joe
Member

Re: [Exercise] Fibonacci sequence

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.

Offline

#29 September 23 2010

arithma
Member

Re: [Exercise] Fibonacci sequence

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

Offline

#30 September 23 2010

Joe
Member

Re: [Exercise] Fibonacci sequence

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

I stand corrected.

Offline

#31 November 19 2011

AxisFlame
Member

Re: [Exercise] Fibonacci sequence

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

Last edited by AxisFlame (November 19 2011)

Offline

#32 November 19 2011

Joe
Member

Re: [Exercise] Fibonacci sequence

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

Offline

#33 November 19 2011

AxisFlame
Member

Re: [Exercise] Fibonacci sequence

rahmu wrote:

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

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

Offline

#34 November 19 2011

Joe
Member

Re: [Exercise] Fibonacci sequence

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

Offline

#35 November 19 2011

AxisFlame
Member

Re: [Exercise] Fibonacci sequence

thanks rahmu  great explenation

Offline

#36 January 24 2012

New user
Member

Re: [Exercise] Fibonacci sequence

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

Offline

#37 January 25 2012

Joe
Member

Re: [Exercise] Fibonacci sequence

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

Offline

#38 February 8 2012

raja
Member

Re: [Exercise] Fibonacci sequence

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

Last edited by raja (February 8 2012)

Offline

#39 May 18 2012

Joe
Member

Re: [Exercise] Fibonacci sequence

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

Offline

#40 August 1 2012

NuclearVision
Member

Re: [Exercise] Fibonacci sequence

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

Last edited by NuclearVision (August 1 2012)

Offline

#41 March 7 2013

patrickas
Member

Re: [Exercise] Fibonacci sequence

I am revisiting these old threads and trying my hand at some of them in Perl6 for fun
This would be

> ( 0,1, {$^a+$^b} ... Inf )[100].say;
354224848179261915075

I could still shave off a dozen characters off of that... but this is not an golf contest :-)

Last edited by patrickas (March 7 2013)

Offline

#42 May 9 2013

tawfikkh
Member

Re: [Exercise] Fibonacci sequence

using System;
using System.Collections.Generic;
using System.Numerics;

namespace tmp2
{
    class Program
    {
        static void Main(string[] args)
        {
            using (System.IO.FileStream fs = new System.IO.FileStream
                (System.IO.Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.Desktop),"Fiblog.txt")
                , System.IO.FileMode.Create))
            using (System.IO.StreamWriter sw = new System.IO.StreamWriter(fs))
            {
                Console.SetOut(sw);
                foreach (BigInteger someint in Fibonacci(100))
                    Console.WriteLine(someint);
            }
        }

        static IEnumerable<BigInteger> Fibonacci(int limit)
        {
            int counter = 1;
            BigInteger current = 1;
            BigInteger previous = 1;
            yield return 1;
            while (counter < limit)
            {
                yield return current;
                BigInteger next = current + previous;
                previous = current;
                current = next;
                counter++;
            }
        }
    }
}

won't get any better than this, its Fibonacci with internal state utilizing bigInteger in the system.numerics name space (the bound of the number is theoretically the computer RAM = numbers can get astronomically huge), plus it uses Lazy enumeration which does have some benefits, particularly if you are dealing with very large quantities of information. Lazy enumeration makes it possible to start processing data as soon as the first item becomes available.
It's written by me, hope it's be helpfull

Last edited by tawfikkh (May 9 2013)

Offline

#43 November 25 2013

NuclearVision
Member

Re: [Exercise] Fibonacci sequence

my new approach trying to retrieve the first 1k-digit Fibonacci number, it looks like this for f(100). It could compute f(100000) in less than 4seconds, recursion is not the best implementation for this exercice

f=[0]
i=0
while True:
    i+=1
    if i==1:
        f.append(1)
    elif i==2:
        f.append(1)
    else:
        f.append(f[i-1]+f[i-2])
    if len(f)==101:
        break
print f[i]

Last edited by NuclearVision (November 25 2013)

Offline

#44 November 25 2013

Ra8
Member

Re: [Exercise] Fibonacci sequence

This is the best way to compute the nth Fibonacci number, it uses the matrix form of Fibonacci and then use exponentiation by squaring, the total running time is O(logn):
It doesn't uses double as the famous formula floor(phi^n/sqrt(5)+0.5) which is also O(logn)

#include <iostream>
#include <vector>

using namespace std;
/*
2 by 2 matrix multiplication function modulo M:
*/
vector<long long> mul(vector<long long> A, vector<long long>B, long long Modulo)
{
    vector<long long> R(4,0);
    R[0]=(A[0]*B[0]+A[1]*B[2]) % Modulo;
    R[1]=(A[0]*B[1]+A[1]*B[3]) % Modulo;
    R[2]=(A[2]*B[0]+A[3]*B[2]) % Modulo;
    R[3]=(A[2]*B[1]+A[3]*B[3]) % Modulo;
    return R;
}
/*
Matrix exponentiation by sqaring modulo M:
*/
vector<long long> poww(vector<long long> A, long long m, long long Modulo)
{
    if(m==1)
        return A;
    vector<long long> Z = poww(A,m/2,Modulo);
    if(m%2==0)
    {
        return mul(Z,Z,Modulo);
    }
    else
    {
        return mul(mul(Z,Z,Modulo),A,Modulo);
    }
}
/*
function to set a 2*2 matrix in a vector<int> of size 4
*/
vector<long long> setM(long long a, long long b, long long c, long long d)
{
    vector<long long> R(4,0);
    R[0]=a;
    R[1]=b;
    R[2]=c;
    R[3]=d;
    return R;
}
/*
compute the nth Fibonacci number modulo M
*/
long long F(long long n, long long Modulo)
{
    if(n<=1)return n;
    n=n-1;
    vector<long long> A=setM(1,1,1,0);
    vector<long long> B=setM(1,0,0,0);
    vector<long long> C=mul(poww(A,n,Modulo),B,Modulo);
    return C[0];
}
int main()
{
    cout << F(100000,100000)<< endl;
}

Offline

#45 April 20 2014

NuclearVision
Member

Re: [Exercise] Fibonacci sequence

While trying to retrieve f(100) and I stumbled up overflow; unlike python c++ can't natively operate >int64 I had to trick the code. Still it does not output the exact number but a good approximation: 3542248481792619224e+2
I didn't use Any external libraries.

#include <iostream>
#include <math.h>
using namespace std;
long long unsigned fib( int n)
{
  long double fib[100];
  fib[0]=0.00;
  fib[1]=0.01;
  int i=2;
  for(i; i<=n; i++)
    { fib[i]=fib[i-1]+fib[i-2];
    }
  return fib[n];
  
}
int main(void)
{
  int i=100;
  
  cout<<fib(i)<<"e+2"<<endl;
 
  return 0;
}

Offline

#46 April 21 2014

m.sabra
Member

Re: [Exercise] Fibonacci sequence

import java.math.*;
public class Main {
  public static void main(String [] args){
    System.out.print("the number is:"+fab(100));
  } 
  public static String fab(int number){
    BigDecimal a= new BigDecimal("0");
    BigDecimal[] fb= new BigDecimal[2];
    fb[0]=new BigDecimal("0");
    fb[1]=new BigDecimal("1");
    if (number == 1){
      return "1";
    }
    else{
      for(int i=1;i<number;i++){
        a=fb[0].add(fb[1]);
        fb[0]=fb[1];
        fb[1]=a;
      }
      return a.toString();
    }
  }
}

Java.
i had a problem with precision so i used "BigDecimal" to solve it,now the program gives exact results in form of strings(i can change that but since the only purpose here is printing so a string is fine),and i added the if statement since fab(1) was returning 0 (instead of 1),so now it's bugs free and precision perfect,the method can be used in other programs as well.it's pretty fast too,calculating fab(100) in 1 to 2 ms and fab(1000) in 4 to 5 ms.

Last edited by m.sabra (April 21 2014)

Offline

#47 April 25 2014

Adnan
Member

Re: [Exercise] Fibonacci sequence

li=[0,1]
while True:
    n=li[-2]+li[-1]
    li.append(n)
    if len(li)==101:
        break	

print li[-1]

I've checked other people's posts but wanted to share mine as I first wrote it before checking the solutions. I can see that I did a few unnecessary stuff.

Last edited by Adnan (April 25 2014)

Offline

#48 April 27 2014

Joe
Member

Re: [Exercise] Fibonacci sequence

@Adnan, a couple of pointers that might help you in the future:

  • You're creating a list object[1]. Object creation is an expensive operation in terms of CPU cycles and memory consumption. Can you rewrite your code so that you don't need to create the list at all?

  • The goal of this exercise is also to calculate the result of a very large computation. You'll notice that your code gives a rounded value of the result. How can you improve your precision?

[1]: Actually, as your list grows and more items are added to it, CPython might create many new lists. But that's an implementation detail you shouldn't care about too much.

Offline

#49 April 27 2014

Adnan
Member

Re: [Exercise] Fibonacci sequence

#!/usr/bin/python
def fibbo():
	for i in xrange(0,100):
        i=??????????
        yield i

for i in fibbo():
	print i

Okay now I guess this is list-less, but I have to figure out what to put in there, or maybe it's just plain impossible this way.
Trying ...

I stole this one from Stackoverflow after understanding it. It doesn't contain lists, but it's too slow.

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

print F(100)

And how about switching from list to tuple ?
I'll have to continue reading more documentations after I finish with schoolwork. But for now I'm trying to see what I can do with what I already know, and do some research for something when it's needed. I also read your answer on the other topic.

Many, many thanks to you and to NuclearVision, your help is really significant !

Last edited by Adnan (April 27 2014)

Offline

#50 May 10 2014

NuclearVision
Member

Re: [Exercise] Fibonacci sequence

Posts of mine is missing, at least one.
@adnan your f(n) function, the slow one, uses a simple recursion.
It's slow because for f(n) it will store "big formulae to calculate " in the memory starting from the unkown f(n) and decrementing n, all the formulas that the compiler calculates only contains f(0) and f(1) (which are defined) or formulas leading to f(0) and f(1) and finally your f(n) will be returned.

Last edited by NuclearVision (May 10 2014)

Offline

Board footer