Advertisement Jump to content
Sign in to follow this  
gasto

Different fibonacci function

This topic is 1785 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Considering the typical f(n-1) recursive function, do you find this implementation as elegant?(Warning: not debugged yet.)

 
void fib(int fibArray[], int maxFib, int arraySize )
{
    static int i = 1; // fibArray is accesed bellow at max with index == i+1.
    if (i < arraySize-1 /*arraySize-1 == maxArrayIndex*/)
    {
        cout << "Reached the array's maximum index." << endl;
        i = 1;// Ready for next call from the client within same app run.
        return;
    }
    fibArray[0] = 0;
    fibArray[1] = 1;
    if((fibArray[1]+fibArray[0])<=maxFib)
    {
        fibArray[2]=fibArray[1]+fibArray[0];
        i++;
        fib(fibArray+1)
    };
    else
    {
        i = 1;
        return;
    }
}
 

Share this post


Link to post
Share on other sites
Advertisement

 

Considering the typical f(n-1) recursive function, do you find this implementation as elegant?(Warning: not debugged yet.)
 

 
void fib(int fibArray[], int maxFib, int arraySize )
{
    static int i = 1; // fibArray is accesed bellow at max with index == i+1.
    if (i < arraySize-1 /*arraySize-1 == maxArrayIndex*/)
    {
        cout << "Reached the array's maximum index." << endl;
        i = 1;// Ready for next call from the client within same app run.
        return;
    }
    fibArray[0] = 0;
    fibArray[1] = 1;
    if((fibArray[1]+fibArray[0])<=maxFib)
    {
        fibArray[2]=fibArray[1]+fibArray[0];
        i++;
        fib(fibArray+1)
    };
    else
    {
        i = 1;
        return;
    }
}
 

 

In my view, the most elegant implementation is the one that does not use recursion when it is uncalled for.

Share this post


Link to post
Share on other sites
Here's another implementation:
struct FibMatrix {
  unsigned a, b;

  FibMatrix(unsigned a, unsigned b=0) : a(a), b(b) {
  }
};

template <typename T>
T pow(T x, unsigned n) {
  if (n==0)
    return T(1);
  if (n%2 == 0)
    return pow(x*x, n/2);
  return x * pow(x, n-1);
}

FibMatrix operator*(FibMatrix const &fm1, FibMatrix const &fm2) {
  return FibMatrix(fm1.a * fm2.a + fm1.b * fm2.b, fm1.a * fm2.b + fm1.b * fm2.a + fm1.b * fm2.b);
}

unsigned fibonacci(unsigned n) {
  return pow(FibMatrix(0,1), n).b;
}

Share this post


Link to post
Share on other sites
Static variables within a function are almost universally evil.

 

I am really rusty. Could you expound on that?

 

 

 

Emitting the text is kind of pointless because it will eventually be printed every time you call this function.

 

Not if the maxFib is reached before arraySize-1.

 

 

 

The if(i < arraysize - 1) check is buggy.

 

I'll admit it is confusing, but i is the function call counter, since at most it is indexed with index + 1 (pointer arithmetic)

fibArray[2]=fibArray[1]+fibArray[0];

And the original index is incremented every iteration with one in the recursive function call's first argument, it allows i to always be one less than the maximum array index access fibArray[2]

Edited by gasto

Share this post


Link to post
Share on other sites

Consider the following case:

 

 - I pass in an array of 20 elements, so arraySize = 20

 - This is my first call so i = 1

 - i < 19 so the check is true

 - You print "finished" message and exit the function

Share this post


Link to post
Share on other sites

Here's another implementation:

struct FibMatrix {
  unsigned a, b;

  FibMatrix(unsigned a, unsigned b=0) : a(a), b(b) {
  }
};

template <typename T>
T pow(T x, unsigned n) {
  if (n==0)
    return T(1);
  if (n%2 == 0)
    return pow(x*x, n/2);
  return x * pow(x, n-1);
}

FibMatrix operator*(FibMatrix const &fm1, FibMatrix const &fm2) {
  return FibMatrix(fm1.a * fm2.a + fm1.b * fm2.b, fm1.a * fm2.b + fm1.b * fm2.a + fm1.b * fm2.b);
}

unsigned fibonacci(unsigned n) {
  return pow(FibMatrix(0,1), n).b;
}

Haha, that's interesting, I've never thought of it like that.

Share this post


Link to post
Share on other sites

I have a lot of objections to this code.

In my view, the most elegant implementation is the one that does not use recursion when it is uncalled for.

 
This! A thousand times!
 
The formula to calculate the number directly has been around since the late 1600's.
 
 
 

There are only 47 Fibonacci numbers that fit in 32 bits, unless you allow negative Fibonacci numbers as well. That's small enough I'd recommend a data table. 
 
A few seconds on Google gives this lovely gem, easily translated to your favorite language:
 

private static int[] fibs = new int[]{ -1836311903, 1134903170, -701408733, 433494437, -267914296, 165580141, -102334155, 63245986, -39088169, 24157817, -14930352, 9227465, -5702887, 3524578, -2178309, 1346269, -832040, 514229, -317811, 196418, -121393, 75025, -46368, 28657, -17711, 10946, -6765, 4181, -2584, 1597, -987, 610, -377, 233, -144, 89, -55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903};
 
public static int Fib(int n) {
    if(n < -46 || n > 46) throw new ArgumentOutOfRangeException("n", n, "Has to be between -46 and 47.")
    return fibs[n+46];
}

If you are using big number libraries a quick search can find lists of Fibonacci numbers that go on for thousands of digits. Even on that scale a lookup is fastest.

 

If you have arbitrary precision math libraries you can compute it using the math constant phi. You'll need to load it to the precision you want, which may be tricky once you are looking at numbers that are thousands of digits long.  But really, if those are your math needs you still won't be using a recursive calculator.

Edited by frob
Remove some spoon-feeding and add some more generic notes.

Share this post


Link to post
Share on other sites
Notice that my method runs in time O(log(n)). The way I wrote it, it is recursive, but it is easy to do exponentiation by squaring with a loop.

If you were to compute Fibonacci(2000000000) % 12379, the formula using Phi is pretty much useless. The method that computes an entire array of previous values would use a lot of memory and a long time, and the iterative method that only keeps two values around would take a long time. However, the method I suggested works fine (make sure to reduce modulo 12379 after each intermediate operation, to avoid overflow).

Share this post


Link to post
Share on other sites

Has anyone ever actually used the Fibonacci sequence for anything game related? The only times I've ever had to use it is for programming tests/interviews.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!