14 replies to this topic

[HAL 9000]

I made a non recursive Fibonacci function in C for fun because it can't solve 100 fast with recursion.
Did anyone else besides me do it this way

#include<stdio.h>

/*prototypes*/
double fib(int n);

int main(void)
{
	int i;
	
	for(i = 0;i <= 100;++ i)
	{
		printf("%1.0f \n",fib(i));
	}

	return 0;
}

/*non recursive fibonacci function*/
double fib(int n)
{
	double prev = -1;
	double result = 1;
	double sum;
	int i;
	
	for(i = 0;i <= n;++ i)
	{
		sum = result + prev;
		prev = result;
		result = sum;
	}
	
	return result;
}

Edited by HAL 9000, 23 June 2008 - 12:32 AM.

[samy]

Hi HAL 9000!

Your code looks good. I have not tried your code but it seems to be working. I want to ask a question (just for sharing fun along with you) as to how long your code can extent i.e until what number.

[WingedPanther]

I tend to do factorials, permutations, and combinations in loops for the same reason.

[samy]

Hi WingedPanther!

Would you like to share the fun with us by giving the program for factorials, permutations, and combinations?

[John]

HAL 9000 said:

I made a non recursive Fibonacci function in C for fun because it can't solve 100 fast with recursion.
Did anyone else besides me do it this way

#include<stdio.h>


/*prototypes*/

double fib(int n);


int main(void)

{

	int i;

	

	for(i = 0;i <= 100;++ i)

	{

		printf("%1.0f \n",fib(i));

	}


	return 0;

}


/*non recursive fibonacci function*/

double fib(int n)

{

	double prev = -1;

	double result = 1;

	double sum;

	int i;

	

	for(i = 0;i <= n;++ i)

	{

		sum = result + prev;

		prev = result;

		result = sum;

	}

	

	return result;

}

A few months ago, I posted this:

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <math.h>

using namespace std;


//Non-recrusive: O(1)

unsigned long fib(int n)

{

     return (1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n));

}


//Recrusive: O(n)

unsigned long fib2(int n)

{

    if(n <= 2) return 1;

    else return fib2(n - 1) + fib2(n - 2);

}


//Iterative: O(n)

unsigned long fib3(int n)

{

    int u = 0;

    int v = 1;

    int i, t;


    for(i = 2; i <= n; i++)

    {

        t = u + v;

        u = v;

        v = t;

    }

    return v;        

}

Edited by dargueta, 26 November 2010 - 02:12 PM.
Fixed code tags

[WingedPanther]

samy said:

Hi WingedPanther!

Would you like to share the fun with us by giving the program for factorials, permutations, and combinations?

int factorial(int n){

  int fact=1;

  for (int i=1;i<=n;i++) fact*=i;

  return fact;

}


int permutation(int n,r){

  int perm=1;

  for (int i=n-r+1;i<=n;i++) perm*=i;

  return perm;

}


int combination(int n,r){

  return permutation(n,r)/factorial(r);

}

[samy]

Hi WingedPanther!

Your code is awesome. I think you have a great mind.

Good going. :cool:

[WingedPanther]

It's a side-effect of being a mathematician: math algorithms come REALLY easily to me.

[samy]

Hi WingedPanther!

I think you love mathematics. Have you tried some thing like derivatives or integrations, sine, cosine, etc.

[WingedPanther]

I've got a master's in math... yes, I love math :)

[G_Morgan]

Out of interest why are you returning a double?

//edit - the OP that is.//

[Roman Y]

hehe was searching the web yesterday in search for none recursive fibonacci function all of the sites that I've come thought of none recursive as iterative, but what I meant was a none recursive from the mathematical point of view. Anyway I have developed the function in my math class today. So here is the function (I'm not writing the whole file just the function should work in most languages with standard libraries):

double fibonacci(int n)

{

	return (((1/sqrt(5))*(pow((1+sqrt(5))/2, n)) - ((1/sqrt(5))*(pow((1-sqrt(5))/2, n)))));

}

and it should also be faster than the iterative and recursive functions (programming wise).