Here's my little piece treasure.

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.

Posted 31 July 2012 - 05:20 PM

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.

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.

Posted 01 August 2012 - 06:15 PM

Here's a slightly unconventional approach using a formula.

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

Posted 01 August 2012 - 06:47 PM

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

Jim

Jim

Posted 01 August 2012 - 07:11 PM

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

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

Posted 01 August 2012 - 07:14 PM

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

Posted 01 August 2012 - 07:16 PM

Would Template Meta Programming considered cheating?

Trading compile-time for run-time efficiency

Trading compile-time for run-time efficiency

Posted 01 August 2012 - 07:23 PM

Quote

Would Template Meta Programming considered cheating?

Quote

Use anything you choose

Jim

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

Posted 01 August 2012 - 07:56 PM

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

Posted 01 August 2012 - 08:58 PM

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.

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); }

Posted 02 August 2012 - 11:26 AM

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

Posted 02 August 2012 - 11:59 AM

My cacky entry

Spoiler

Linear Time Tail-Recursive

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

- Caffeine Lounge
- Corner Cubicle
- Student Campus
- Software Development
- Industry News
- Introduce Yourself
- Nightmare.In.Code

- C and C++
- VB.NET
- Java
- C#
- ASP.NET
- .NET Framework
- VB6
- PHP
- Mobile Development
- Python
- Ruby
- Game Development
- Databases
- ColdFusion
- Assembly
- Other Languages
- 52 Weeks Of Code

- Web Development
- HTML & CSS
- JavaScript
- Graphic Design
- Flash & ActionScript
- Blogging
- SEO & Advertising
- Web Servers & Hosting
- Site Check

- Introduction to C++ Metaprogramming: Basics
- Pointers, and a possible problem - if you're not careful!
- Generating Random Numbers - The C++ Way
- Hello World: Your first C and C++ Programs
- Network programming under UNIX
- Implementation Inheritance
- Change Theme in Code::Blocks
- A New Webcam Api Tutorial in C++ for Windows
- External Sorting with C
- C++ Windows Charting Library Part 6
**345 More C++ Tutorials...**

- C Snippets
- C++ Snippets
- Java Snippets
- Visual Basic Snippets
- C# Snippets
- VB.NET Snippets
- ASP.NET Snippets
- PHP Snippets
- Python Snippets
- Ruby Snippets
- ColdFusion Snippets
- SQL Snippets
- Assembly Snippets
- Functional Programming Snippets
- Perl Snippets
- HTML/CSS Snippets
- Javascript Snippets
- Flash/ActionScript Snippets
- ASP Snippets
- Linux, Unix, and Bash Snippets
- Other Languages Snippets
- Regex

Copyright 2001-2016 **MediaGroup1 LLC**, All Rights Reserved

A**MediaGroup1 LLC** Production - Version 6.0.2.1.36

Server: secure3

A

Server: secure3