Login or Sign Up to become a member!
LessThanDot Site Logo

LessThanDot

A Technical Community for IT Professionals

Less Than Dot is a community of passionate IT professionals and enthusiasts dedicated to sharing technical knowledge, experience, and assistance. Inside you will find reference materials, interesting technical discussions, and expert tips and commentary. Once you register for an account you will have immediate access to the forums and all past articles and commentaries.

LTD Social Sitings

Lessthandot twitter Lessthandot Linkedin Lessthandot facebook Lessthandot rss

Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.

Highly Rated Users

Forum
No Posts Rated

Top 50
Given
Received

Forum Statistics

Users
Members:
1534
Members Online:
3
Guests Online:
16

Total Post History
Posts:
80269
Topics:
18350

7-Day Post History
New Posts:
11
New Topics:
2
Active Topics:
4

Our newest member
joyento

Other

FAQ
All times are UTC [ DST ]

Google Ads

LTD Puzzle 5: Calculating the Fibonacci Sequence

Mind Boggling Puzzles, to keep that grey matter in shape...
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Please wait...

LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby damber on Fri Jul 04, 2008 7:01 pm

This weeks puzzle is a nice and simple one to ease all those with sore heads from the July 4th celebrations back into thinking code...

If you've read the Dan Brown book "The Da Vinci Code" then you'll be quite familiar with this already... we would like you to calculate 'X' numbers in the Fibonacci Sequence, which is essentially adding the previous 2 occurring numbers together to make the next .. e.g. 0,1,1,2,3,5,8,13,21,34,55,89,....etc.

  • Code should accept a single parameter to set the amount of numbers in the sequence to calculate, e.g. first 10 numbers, first 100, etc
  • Format of output should be simply a list of numbers separated by a comma between each number; e.g. 0,1,1,2,3,5,8 etc..
  • Interesting Variations score more points of course :-)
  • Sequence always starts at 0,1 - so minimum sequence length is 2.

have fun... ;-)

p.s. don't forget to use the new [hidecode] tag to hide your code and highlight the syntax
a smile is worth a thousand kind words, so smile, it's easy! :-)


CODE: $5
WORKING CODE: $500
PROPERLY DESIGNED & WORKING CODE: Priceless
User avatar
damber
LTD Admin
LTD Admin
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
 
Posts: 3134
Joined: Tue Oct 09, 2007 1:48 pm
Location: North Wales, UK
Unrated

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby chrissie1 on Fri Jul 04, 2008 7:34 pm

this is a quick and dirty example in vb.net.

Max iterations is apparently with int64

Code is hidden, SHOW
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9340
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby chrissie1 on Fri Jul 04, 2008 7:37 pm

When using a double it reaches infinity at iteration



Code is hidden, SHOW
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9340
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby AlexCuse on Sat Jul 05, 2008 4:48 pm

Code is hidden, SHOW
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5405
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby HarleyQuinn on Tue Jul 08, 2008 1:28 pm

A not particularly exciting VB6 version...
Code is hidden, SHOW
Andy
User avatar
HarleyQuinn
LTD Admin
LTD Admin
LTD Bronze - Rating: 46
 
Posts: 308
Joined: Tue Dec 18, 2007 3:14 pm
Location: Sheffield, UK
Unrated

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby spoulson on Tue Jul 08, 2008 4:03 pm

I have two entries, since neither approach has been posted yet.

First, a C# .NET 3.5 approach using IEnumerable.
Code is hidden, SHOW

And, here's a C++/CLI version that uses template meta-programming. This causes the compiler to compute all the math and unroll the loops, so the actual executed code is doing nothing more than printing the numbers. Changing to native C++ would be a matter of changing Console::WriteLine() to printf() function, updating the main() signature to main(int argc, const char *argv[]), and replacing "using ..." with "#include <stdlib.h>".

Code is hidden, SHOW
User avatar
spoulson
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 115LTD Bronze - Rating: 115LTD Bronze - Rating: 115
 
Posts: 205
Joined: Mon Jun 02, 2008 2:37 am
Location: Middletown, DE, USA

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby gmmastros on Tue Jul 08, 2008 6:24 pm

Another VB6 version.

Unlike all the other submissions, this version can calculate fibonacci numbers that are very long without losing any significant digits (like using the double/float data type). I tested this with calculating the first 10,000 fibonacci number. This version is probably limited to the amount of text that can fit in to a vb6 text box.

Code is hidden, SHOW
-George
User avatar
gmmastros
LTD Admin
LTD Admin
LTD Gold - Rating: 1616LTD Gold - Rating: 1616LTD Gold - Rating: 1616LTD Gold - Rating: 1616LTD Gold - Rating: 1616
LTD Gold - Rating: 1616LTD Gold - Rating: 1616LTD Gold - Rating: 1616LTD Gold - Rating: 1616LTD Gold - Rating: 1616
LTD Gold - Rating: 1616LTD Gold - Rating: 1616
 
Posts: 2314
Joined: Tue Oct 09, 2007 5:19 pm

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby HarleyQuinn on Wed Jul 09, 2008 12:00 am

Nice one George, I originally went with an array solution but dropped it for the shorter code (I've given you a point as I didn't have time to make either of my solutions as nicely outputted as yours!) :D

Plus, the limitation of a textbox is gotten around by outputting to a file and that's probably only one more line of code if you're going absolutely minimal ;)
Andy
User avatar
HarleyQuinn
LTD Admin
LTD Admin
LTD Bronze - Rating: 46
 
Posts: 308
Joined: Tue Dec 18, 2007 3:14 pm
Location: Sheffield, UK
Unrated

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby sembee on Wed Jul 09, 2008 9:57 am

Hi,
what about a lazy functional solution written with F#?

Code is hidden, SHOW

Claudio
http://www.fsharp.it
sembee
Newbie
Newbie
LTD Bronze - Rating: 14
 
Posts: 1
Joined: Wed Jul 09, 2008 9:53 am

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby AlexCuse on Wed Jul 09, 2008 1:47 pm

That's awesome sembee. That very thing came to mind last night when I was trying to focus on school work (I had tried going down that road for the prime number puzzle, but found that sequence was not really orderly enough to use that particular function effectively).
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5405
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby Emtucifor on Fri Jul 11, 2008 8:09 pm

Code is hidden, SHOW

it calculates up to 50095301248058391139327916261, the 140th term. That's 50 octillion!
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby chrissie1 on Fri Jul 18, 2008 10:30 am

There are 2 types of winner - a "People's Champion" (the one with the most rating points across all their posts) and the LTD Admin's Champion (selected with our special formula....honest...well, maybe it's just the ones that the admins thought were particularly good :-))

So...

People's Champion: sembee scoring 13 points for his very short and sweet answer.

LTD Admin's Champion: George for using strings to get the job done.


Congratulations to all.. and good luck on next weeks puzzle :-)
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9340
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby tisodotsk on Fri Aug 08, 2008 7:59 pm

My solution in PHP:

Code is hidden, SHOW

Output (first 10 lines):
  1. FibonacciSequence(2): 0,1,1
  2. FibonacciSequence(3): 0,1,1,2
  3. FibonacciSequence(4): 0,1,1,2,3
  4. FibonacciSequence(5): 0,1,1,2,3,5
  5. FibonacciSequence(6): 0,1,1,2,3,5,8
  6. FibonacciSequence(7): 0,1,1,2,3,5,8,13
  7. FibonacciSequence(8): 0,1,1,2,3,5,8,13,21
  8. FibonacciSequence(9): 0,1,1,2,3,5,8,13,21,34
  9. FibonacciSequence(10): 0,1,1,2,3,5,8,13,21,34,55
  10. FibonacciSequence(11): 0,1,1,2,3,5,8,13,21,34,55,89
  11. FibonacciSequence(12): 0,1,1,2,3,5,8,13,21,34,55,89,144
I try to improve my English language skills. Most things i do better than this.
tisodotsk
Apprentice
Apprentice
LTD Bronze - Rating: 62LTD Bronze - Rating: 62
 
Posts: 22
Joined: Fri Aug 08, 2008 12:45 pm
Location: Bratislava, Slovakia

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby luckenbach on Sat Jan 22, 2011 6:04 pm

I chose to do it in perl this time for fun :)

Code is hidden, SHOW


Made one a little shorter and less drawn out

Code is hidden, SHOW
luckenbach
Newbie
Newbie
LTD Bronze - Rating: 7
 
Posts: 2
Joined: Thu Jan 20, 2011 4:09 am

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby janroesner on Sat Aug 18, 2012 6:42 pm

Ruby fun single liner:

Code is hidden, SHOW


Cheers
janroesner
Newbie
Newbie
LTD Bronze - Rating: 3
 
Posts: 1
Joined: Sat Aug 18, 2012 6:40 pm

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby frob23 on Wed Sep 05, 2012 12:51 am

This is a problem that dc(1) was made to solve. With its arbitrary precision, you're only bound by the size of your stack (recursive macro call) and not the size of your variables. I was able to calculate the values up to around the 12,900th term using this (I ran into issues after that). And those issues are related to the recursion. This could probably be solved to work with terms even larger than that by putting the loop itself into a shell script and using a temporary file to store the numbers between runs. But I've already taken longer writing this than it took to write the actual program and reworking it to handle as many terms as anyone could ever want is too much for me right now.

Code is hidden, SHOW


This time with comments:
Code is hidden, SHOW


OK, I'm not going to do every puzzle in dc. This was just one where it actually makes sense.

OK, I couldn't help myself. I was able to increase the overall length by breaking the calculation into chunks of smaller sequences to calculate. By using nested loops, I was able to reduce the stack usage. I ran it and was well over 50,000 values before I got bored watching it spit out values; I had changed it for the test run to number the output.
Code is hidden, SHOW
frob23
Newbie
Newbie
LTD Bronze - Rating: 15
 
Posts: 2
Joined: Tue Sep 04, 2012 11:04 pm

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby whitekalashnikov on Sat Nov 10, 2012 2:22 pm

Hi, here's one I made in Lua (for 100 iterations):
Code is hidden, SHOW

The output:
Code is hidden, SHOW
whitekalashnikov
Newbie
Newbie
LTD Bronze - Rating: 5
 
Posts: 2
Joined: Sat Nov 10, 2012 2:15 pm

Re: LTD Puzzle 5: Calculating the Fibonacci Sequence

Postby biglittle007 on Tue Aug 20, 2013 1:47 pm

Another PHP code:

Code is hidden, SHOW
biglittle007
Newbie
Newbie
 
Posts: 3
Joined: Wed Aug 14, 2013 9:16 pm
Unrated