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

patrickas

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

tawfikkh

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

NuclearVision

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]

Ra8

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

NuclearVision

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

m-sabra

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.

Adnan

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.

Joe

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

Adnan

#!/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 !

NuclearVision

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.

Joe

Still working with Go:

package main

import (
	"fmt"
	"math/big"
)

func fibonacci(n int) *big.Int {
	if n < 2 {
		return big.NewInt(int64(n))
	}

	a, b := big.NewInt(0), big.NewInt(1)
	c := big.NewInt(0)

	for i := 1; i < n; i++ {
		c.Set(a)
		a.Set(b)
		b.Add(b, c)
	}

	return b

}

func main() {
	fmt.Printf("%s\n", fibonacci(100).String())
}

I confirm that the result is 354224848179261915075.

PS: The Go bigNum library is a mess and the lack of operator overloading is annoying.

« Previous Page