Tryst with a variation of Fibonacci !!

[nthrgeek]

Consider the following code snippet:

int find_fib(int N)
{
assert(N>0);

int f1 = 1;
int f2 = 1;

if(N<2) return 1;

return (find_fib(N-1) + find_fib(N-2));
}

Given that find_fib is called from main with N as 25,how many total
calls
are made to find_fib ? (We can't modify the find_fib)

Manually we can derive this:

Let f(n) be the number of calls made to calculate fib(n).

* If n < 2 then f(n) = 1.
* Otherwise, f(n) = 1 + f(n - 1) + f(n - 2).

So, f is at least O(fib(n)). In fact, f(n) is 2 * fib(n) - 1. We show
this by induction:

* Base cases (n < 2, that is, n = 0 or n = 1):
o f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1.
* Induction step (n >= 2):
o f(n + 1) = f(n) + f(n - 1) + 1
o f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1
o f(n + 1) = 2 * fib(n + 1) - 1


Modifying the find_fib by including a counter variable,I computed:

fib(25) =121393
Number of times called : 242785

 

[nthrgeek]

Consider the following code snippet:

int find_fib(int N)
{
  assert(N>0);

  int f1 = 1;
  int f2 = 1;

  if(N<2) return 1;

  return (find_fib(N-1) + find_fib(N-2));

}

Given that find_fib is called from main with N as 25,how many total
calls
are made to find_fib ? (We can't modify the find_fib)

Manually we can derive this:

Let f(n) be the number of calls made to calculate fib(n).

    * If n < 2 then f(n) = 1.
    * Otherwise, f(n) = 1 + f(n - 1) + f(n - 2).

So, f is at least O(fib(n)). In fact, f(n) is 2 * fib(n) - 1. We show
this by induction:

    * Base cases (n < 2, that is, n = 0 or n = 1):
          o f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1.
    * Induction step (n >= 2):
          o f(n + 1) = f(n) + f(n - 1) + 1
          o f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1
          o f(n + 1) = 2 * fib(n + 1) - 1

Modifying the find_fib by including a counter variable,I computed:

fib(25) =121393
Number of times called : 242785

Problem Solved.I just now recalled that we are free to write your own
assert() macro.

So I solved this with:

int Count = 0;

#define assert(x) Count + = 1;

If anybody can suggest some better solution he/she is welcome

 

[Paul N]

Consider the following code snippet:

int find_fib(int N)
{
  assert(N>0);

  int f1 = 1;
  int f2 = 1;

  if(N<2) return 1;

  return (find_fib(N-1) + find_fib(N-2));

}

This doesn't look right. For instance, suppose we want to find find_fib
(2). The first time through, N is 2, so:

assert(N>0);

No problem

int f1 = 1;
int f2 = 1;

if(N<2) return 1;

N is 2, so we don't return here

return (find_fib(N-1) + find_fib(N-2));

So we've got to calculate find_fib(1) and find_fib(0). Finding find_fib
(0) goes as follows:

assert(N>0);

But N is equal to zero here, so the assert fails and the program
stops!

Hope this helps.
Paul.

 

[Dann Corbit]

This doesn't look right. For instance, suppose we want to find find_fib
(2). The first time through, N is 2, so:


No problem


N is 2, so we don't return here


So we've got to calculate find_fib(1) and find_fib(0). Finding find_fib
(0) goes as follows:


But N is equal to zero here, so the assert fails and the program
stops!

Maybe:

#include <math.h>
/*
** Direct computation of Fibonacci numbers.
**
** Input: index of Fibonacci number to compute (n)
**
** Returns: nth Fibonacci number.
*/
double
Fibonacci (unsigned n)
{
/* isf is 1/sqrt(5) */
static const double isf =
0.44721359549995793928183473374625524708812367192231;
/* gr is golden ratio */
static const double gr =
1.6180339887498948482045868343656381177203091798057;
double x, xx;

x = pow (gr, n) * isf;
xx = floor (x);
if (x - xx > 0.5)
xx += 1;
return xx;
}
#ifdef UNIT_TEST
#include <stdio.h>
main ()
{

unsigned i;
double dfib;
for (i = 0; i <= 80; i++)
{
dfib = Fibonacci (i);
printf ("Fibonacci(%u) = %.0f\n", i, dfib);
}
return 0;

}
#endif

 

[Morris Keesan]

Thanks,but I was looking for an alternate solution for the problem.

I have no idea what the original poster was looking for, but an obvious
alternative to recursion, for computing Fibonacci numbers, would be to use
iteration.

 

[scattered]

Consider the following code snippet:

int find_fib(int N)
{
  assert(N>0);

  int f1 = 1;
  int f2 = 1;

  if(N<2) return 1;

  return (find_fib(N-1) + find_fib(N-2));

}

Given that find_fib is called from main with N as 25,how many total
calls
are made to find_fib ? (We can't modify the find_fib)

Manually we can derive this:

Let f(n) be the number of calls made to calculate fib(n).

    * If n < 2 then f(n) = 1.
    * Otherwise, f(n) = 1 + f(n - 1) + f(n - 2).

So, f is at least O(fib(n)). In fact, f(n) is 2 * fib(n) - 1. We show
this by induction:

    * Base cases (n < 2, that is, n = 0 or n = 1):
          o f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1.
    * Induction step (n >= 2):
          o f(n + 1) = f(n) + f(n - 1) + 1
          o f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1
          o f(n + 1) = 2 * fib(n + 1) - 1

Modifying the find_fib by including a counter variable,I computed:

fib(25) =121393
Number of times called : 242785

What is the point of the variables f1,f2?

 

[Dann Corbit]

I have no idea what the original poster was looking for, but an obvious
alternative to recursion, for computing Fibonacci numbers, would be to use
iteration.

Better yet, since they expand at an exponential rate (with g as the
exponent) why not just create a table?

Here is an interesting paper on recurrence relations of this sort:
http://www.math.binghamton.edu/chanusa/papers/2001/tilingchain.pdf

 

[Ike Naar]

Better yet, why not just calculate the result directly? There is a
simple formula.

Simple, but inaccurate. Elsethread, Dann Corbit posted code
that computes the Fibonacci numbers directly.
Here's a fragment from the program's output:

[...]
Fibonacci(69) = 117669030460994
Fibonacci(70) = 190392490709135
Fibonacci(71) = 308061521170130
[...]

It can easily be verified that Fibonacci(69) + Fibonacci(70) != Fibonacci(71).