[IngeniousHax]

See how small and compact, yet efficient you can make a Fibonacci function, or don't use a function. Use anything you choose, recursion, arrays, linked lists, whatever you fancy Let's see what we can come up with!


Here's my little piece treasure.

Spoiler

#include <iostream>
using std::cout;

int Fib(int i)
{
  int value = 0;
  if(i < 1) return 0;
  if(i == 1) return 1;
  return Fib(i-1) + Fib(i - 2);
}

int main()
{
  int i = 0;
  while(i < 45)
  {
     cout << Fib(i) << endl;
     i++;
   }        
  return 0;
}

This post has been edited by jimblumberg: 01 August 2012 - 03:58 PM
Reason for edit:: Added missing Code Tags, Please learn to use them.

[Aphex19]

Here's a slightly unconventional approach using a formula.

Spoiler

#include <iostream>
#include <math.h>

int fib(int n) {
	static const double phi = 1.618033;
	static const double sr5 = 2.236067;
	return ceil(((pow(phi,n) - pow(phi-sr5,n)) / sr5));
}

int main() {
	for (int i = 0; i < 10; i++)
		std::cout << fib(i) << std::endl;
	return 0;
}

It's only an approximation though, and in that code after the first 24 digits, the results seem to start showing errors. It's just a matter of fractional precision though. Theoretically, the formula could calculate fib to infinity given infinitely precise numerical values and arithmetic.

edit:
improved (slightly). Accurate up to fib(52).

Spoiler

#include <iostream>
#include <math.h>

unsigned long long fib(int n) {
	static const double phi = 1.618033988749;
	static const double sr5 = sqrt((double)5.0);
	return ceil(((pow(phi,n) - pow(phi-sr5,n)) / sr5));
}

int main() {
	for (int i = 1; i < 53; i++)
		std::cout << i << " " << fib(i) << std::endl;
	return 0;
}

This post has been edited by Aphex19: 01 August 2012 - 07:39 PM
Reason for edit:: Added spoiler tags

[GWatt]

You could use the C standard library constant M_PHI as well as computing the square root of 5 to give you more precision.

[jimblumberg]

Please place code, inside code tags, inside spoiler tags.

Jim

[jon.kiparsky]

Oops - didn't see that we were in C, sorry

This post has been edited by jon.kiparsky: 01 August 2012 - 07:13 PM

[Aphex19]

GWatt, on 02 August 2012 - 02:44 AM, said:

You could use the C standard library constant M_PHI as well as computing the square root of 5 to give you more precision.

I can't seem to find an info on M_PHI. It's no listed here and it's apparently not declared in "math.h". Anyway, I'm sure that the calculation could be made much more precise.

jimblumberg, on 02 August 2012 - 02:47 AM, said:

Please place code, inside code tags, inside spoiler tags.

Noted. Sorry about that.

This post has been edited by Aphex19: 01 August 2012 - 07:16 PM

[AdamSpeight2008]

Would Template Meta Programming considered cheating?

Trading compile-time for run-time efficiency

[Aphex19]

AdamSpeight2008, on 02 August 2012 - 03:16 AM, said:

Would Template Meta Programming considered cheating?

Trading compile-time for run-time efficiency

Would that be the equivalent of using a precompiled lookup table?

[jimblumberg]

Quote

Would Template Meta Programming considered cheating?

From post 1:

Quote

Use anything you choose

Jim

This post has been edited by jimblumberg: 01 August 2012 - 07:24 PM

[GWatt]

Aphex19: You are correct. I thought M_PHI was a standard definition. I could have sworn I've used it before.

[AdamSpeight2008]

Aphex19, on 02 August 2012 - 03:21 AM, said:

AdamSpeight2008, on 02 August 2012 - 03:16 AM, said:

Would Template Meta Programming considered cheating?

Trading compile-time for run-time efficiency

Would that be the equivalent of using a precompiled lookup table?

No it just be the output, as no calculation of Fibonacci would done a run-time

[AlexSleyore]

Spoiler

int Fib(int Place){
          unsigned long OldValue = 0;
	  unsigned long Value = 1;
          unsigned long Hold;
if(i < 1){return(0);}

for(int n = 1; n < Place;n++)
{
Hold = Value;
Value+=OldValue;
OldValue = Hold;
}
	  return(Value);
	}

Untested.. But I think thats correct...

This post has been edited by jimblumberg: 01 August 2012 - 08:03 PM
Reason for edit:: Added spoiler tags

[BetaWar]

I went ahead with the look-up table route. It takes linear time the first time through (300 iterations to be exact) then is constant for any Fibonacci number at index less than 300 and a linear growth for index numbers 300+.

NOTE - By the time you get to the 300th Fibonacci number, you are outside the precision of a double.

Spoiler

double fib(int place){
  static double* lookup = NULL;
  if(lookup == NULL){
    lookup = new double[300];
    lookup[0] = 0;
    lookup[1] = 1;
    for(int i = 2; i < 300; ++i){
      lookup[i] = lookup[i - 1] + lookup[i - 2];
    }
  }
  if(place < 300){
    return lookup[place];
  }
  return fib(place - 1) + fib(place - 2);
}

[IngeniousHax]

Very nice BetaWar, i dig that solution. I believe my solution takes quadratic time to complete (N^2)...

This post has been edited by IngeniousHax: 02 August 2012 - 11:28 AM

[AdamSpeight2008]

My cacky entry

Spoiler

long f(int x, int c, long n)
{
 return x == 0 ? c : f(x-1,n,c+n);
}
long Fib(int x)
{
 return 	f(x,0,1);
}

Linear Time Tail-Recursive