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

## 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 on other sites

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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 9
• 11
• 9
• 9
• ### Forum Statistics

• Total Topics
634135
• Total Posts
3015752
×