# Fibonacci challenge

• (3 Pages)
• 1
• 2
• 3

## 41 Replies - 38711 Views - Last Post: 13 May 2015 - 03:56 AM

### #1 IngeniousHax

• |>|20-514<|{3|2

Reputation: 83
• Posts: 1,379
• Joined: 28-March 09

# Fibonacci challenge

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

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.

Is This A Good Question/Topic? 3

## Replies To: Fibonacci challenge

### #2 Aphex19

• Born again Pastafarian.

Reputation: 616
• Posts: 1,873
• Joined: 02-August 09

## Re: Fibonacci challenge

Posted 01 August 2012 - 06:15 PM

Here's a slightly unconventional approach using a formula.
Spoiler

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

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

Was This Post Helpful? 0

### #3 GWatt

Reputation: 305
• Posts: 3,102
• Joined: 01-December 05

## Re: Fibonacci challenge

Posted 01 August 2012 - 06:44 PM

You could use the C standard library constant M_PHI as well as computing the square root of 5 to give you more precision.
Was This Post Helpful? 0

### #4 jimblumberg

Reputation: 4912
• Posts: 15,342
• Joined: 25-December 09

## Re: Fibonacci challenge

Posted 01 August 2012 - 06:47 PM

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

Jim
Was This Post Helpful? 0

### #5 jon.kiparsky

• Pancakes!

Reputation: 9530
• Posts: 16,478
• Joined: 19-March 11

## Re: Fibonacci challenge

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

Was This Post Helpful? 0

### #6 Aphex19

• Born again Pastafarian.

Reputation: 616
• Posts: 1,873
• Joined: 02-August 09

## Re: Fibonacci challenge

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

Was This Post Helpful? 0

### #7 AdamSpeight2008

• MrCupOfT

Reputation: 2294
• Posts: 9,531
• Joined: 29-May 08

## Re: Fibonacci challenge

Posted 01 August 2012 - 07:16 PM

Would Template Meta Programming considered cheating?

Trading compile-time for run-time efficiency
Was This Post Helpful? 0

### #8 Aphex19

• Born again Pastafarian.

Reputation: 616
• Posts: 1,873
• Joined: 02-August 09

## Re: Fibonacci challenge

Posted 01 August 2012 - 07:21 PM

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?
Was This Post Helpful? 0

### #9 jimblumberg

Reputation: 4912
• Posts: 15,342
• Joined: 25-December 09

## Re: Fibonacci challenge

Posted 01 August 2012 - 07:23 PM

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

Was This Post Helpful? 0

### #10 GWatt

Reputation: 305
• Posts: 3,102
• Joined: 01-December 05

## Re: Fibonacci challenge

Posted 01 August 2012 - 07:27 PM

Aphex19: You are correct. I thought M_PHI was a standard definition. I could have sworn I've used it before.
Was This Post Helpful? 0

### #11 AdamSpeight2008

• MrCupOfT

Reputation: 2294
• Posts: 9,531
• Joined: 29-May 08

## Re: Fibonacci challenge

Posted 01 August 2012 - 07:46 PM

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
Was This Post Helpful? 0

### #12 AlexSleyore

• New D.I.C Head

Reputation: 2
• Posts: 18
• Joined: 23-July 12

## Re: Fibonacci challenge

Posted 01 August 2012 - 07:56 PM

Spoiler

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

Was This Post Helpful? 0

### #13 BetaWar

• #include "soul.h"

Reputation: 1372
• Posts: 7,886
• Joined: 07-September 06

## Re: Fibonacci challenge

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.

Spoiler

Was This Post Helpful? 1

### #14 IngeniousHax

• |>|20-514<|{3|2

Reputation: 83
• Posts: 1,379
• Joined: 28-March 09

## Re: Fibonacci challenge

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

Was This Post Helpful? 0

### #15 AdamSpeight2008

• MrCupOfT

Reputation: 2294
• Posts: 9,531
• Joined: 29-May 08

## Re: Fibonacci challenge

Posted 02 August 2012 - 11:59 AM

My cacky entry

Spoiler

Was This Post Helpful? 2

• (3 Pages)
• 1
• 2
• 3

 .related ul{list-style-type:circle;font-size:12px;font-weight:bold;}.related li{margin-bottom:5px;background-position:left 7px!important;margin-left:-35px;}.related h2{font-size:18px;font-weight:bold;}.related a{color:blue;}