Fibonacci challenge

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

36 Replies - 30488 Views - Last Post: 05 December 2014 - 06:04 PM

#1 IngeniousHax  Icon User is offline

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

Reputation: 79
  • View blog
  • Posts: 1,365
  • 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? 2
  • +

Replies To: Fibonacci challenge

#2 Aphex19  Icon User is offline

  • Born again Pastafarian.
  • member icon

Reputation: 615
  • View blog
  • 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  Icon User is offline

  • member icon

Reputation: 278
  • View blog
  • Posts: 3,079
  • 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  Icon User is online

  • member icon


Reputation: 4290
  • View blog
  • Posts: 13,454
  • 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  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 8029
  • View blog
  • Posts: 13,741
  • 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  Icon User is offline

  • Born again Pastafarian.
  • member icon

Reputation: 615
  • View blog
  • Posts: 1,873
  • Joined: 02-August 09

Re: Fibonacci challenge

Posted 01 August 2012 - 07:14 PM

View PostGWatt, 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.

View Postjimblumberg, 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  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,500
  • 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  Icon User is offline

  • Born again Pastafarian.
  • member icon

Reputation: 615
  • View blog
  • Posts: 1,873
  • Joined: 02-August 09

Re: Fibonacci challenge

Posted 01 August 2012 - 07:21 PM

View PostAdamSpeight2008, 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  Icon User is online

  • member icon


Reputation: 4290
  • View blog
  • Posts: 13,454
  • 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  Icon User is offline

  • member icon

Reputation: 278
  • View blog
  • Posts: 3,079
  • 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  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,500
  • Joined: 29-May 08

Re: Fibonacci challenge

Posted 01 August 2012 - 07:46 PM

View PostAphex19, on 02 August 2012 - 03:21 AM, said:

View PostAdamSpeight2008, 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  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1200
  • View blog
  • Posts: 7,309
  • 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  Icon User is offline

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

Reputation: 79
  • View blog
  • Posts: 1,365
  • 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  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,500
  • 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