LTD Puzzle 5: Calculating the Fibonacci Sequence

[damber]

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

[chrissie1]

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

Max iterations is apparently with int64

vbnetLine number Off | Show | Select all

1. Module Module1
2.  
3.     Sub Main()
4.         Dim x As Int64
5.         Console.WriteLine("Give the number to create")
6.         Dim input As String
7.         input = Console.ReadLine()
8.         If Int64.TryParse(input, x) AndAlso x > 2 Then
9.             Dim y As Int64
10.             Dim oldz As Int64
11.             Dim z As Int64 = 0
12.             Dim newz As Int64 = 1
13.             Console.WriteLine(z & ",")
14.             Console.WriteLine(newz & ",")
15.             For y = 1 To x
16.                 Try
17.                     oldz = newz
18.                     newz += z
19.                     Console.WriteLine(y & ". " & newz & ",")
20.                     z = oldz
21.                 Catch ex As Exception
22.                     Console.WriteLine("end reached")
23.                     Exit For
24.                 End Try
25.             Next
26.         End If
27.         Console.ReadLine()
28.     End Sub
29.  
30. End Module

Code is hidden, SHOW

[chrissie1]

When using a double it reaches infinity at iteration

vbnetLine number Off | Show | Select all

1. Module Module1
2.  
3.     Sub Main()
4.         Dim x As Double
5.         Console.WriteLine("Give the number to create")
6.         Dim input As String
7.         input = Console.ReadLine()
8.         If Double.TryParse(input, x) AndAlso x > 2 Then
9.             Dim y As Double
10.             Dim oldz As Double
11.             Dim z As Double = 0
12.             Dim newz As Double = 1
13.             Console.WriteLine(z & ",")
14.             Console.WriteLine(newz & ",")
15.             For y = 1 To x
16.                 Try
17.                     oldz = newz
18.                     newz += z
19.                     Console.WriteLine(y & ". " & newz & ",")
20.                     z = oldz
21.                 Catch ex As Exception
22.                     Console.WriteLine("end reached")
23.                     Exit For
24.                 End Try
25.             Next
26.         End If
27.         Console.ReadLine()
28.     End Sub
29.  
30. End Module

Code is hidden, SHOW

[AlexCuse]

csharpLine number Off | Show | Select all

1. static void Main(string[] args)
2. {
3.     int toCount;
4.     Console.Write("Enter a number >=2 ");
5.  
6.     if (!int.TryParse(Console.ReadLine(), out toCount))
7.         Console.WriteLine("do as I say!");
8.    
9.  
10.     toCount = toCount < 2 ? 2 : toCount;
11.  
12.     List<double> fibs = new List<double>(toCount);
13.  
14.     double p2, p1, curr;
15.     p2 = 0;
16.     p1 = 0;
17.     curr = 1;
18.  
19.     fibs.Add(p1);
20.  
21.     while (curr <= double.MaxValue && fibs.Count < fibs.Capacity)
22.     {
23.         fibs.Add(curr);
24.  
25.    
26.         curr += p1;
27.         p2 = p1;
28.         p1 = curr - p2;
29.  
30.         //handle overflows when using int/long/ulong rather than double
31.         if (curr < p1)
32.             break;
33.     }
34.  
35.     foreach (double l in fibs)
36.         Console.WriteLine(l);
37.  
38.     Console.WriteLine("Sequence taken to {0} numbers", fibs.Count);
39. }

Code is hidden, SHOW

[HarleyQuinn]

A not particularly exciting VB6 version...

VB6Line number Off | Show | Select all

1. Function FiboSeq(iterations As Long) As String
2.  
3. Dim last As Double
4. Dim first As Double
5. Dim curnum As Double
6.  
7. Dim i As Long
8.  
9. first = 0
10. last = 1
11.  
12. FiboSeq = first & "," & last
13.  
14. If iterations > 2 Then
15.     For i = 2 To iterations
16.         curnum = first + last
17.         first = last
18.         last = curnum
19.         FiboSeq = FiboSeq & "," & curnum
20.     Next i
21. End If
22.  
23. 'Debug.Print FiboSeq
24.  
25. End Function

Code is hidden, SHOW

[spoulson]

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

First, a C# .NET 3.5 approach using IEnumerable.

csharpLine number Off | Show | Select all

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4.  
5. namespace Prog {
6.    class Program {
7.       static void Main(string[] args) {
8.  
9.          foreach (int x in Fibonacci.Sequence.Take(20)) {
10.             Console.WriteLine(x);
11.          }
12.  
13.       }
14.    }
15.  
16.    public static class Fibonacci {
17.       public static IEnumerable<int> Sequence {
18.          get {
19.             var FibQ = new Queue<int>(new int[] { 0, 1 });
20.             int Sum = 1;
21.  
22.             yield return 0;
23.             yield return 1;
24.  
25.             for (; ; ) {
26.                yield return Sum;
27.                FibQ.Enqueue(Sum);
28.                Sum += Sum - FibQ.Dequeue();
29.             }
30.          }
31.       }
32.    }
33. }

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

cppLine number Off | Show | Select all

1. using namespace System;
2.  
3. template<int n>
4. struct Fibonacci {
5.    enum { Sequence = Fibonacci<n-1>.Sequence + Fibonacci<n-2>.Sequence };
6. };
7.  
8. template<>
9. struct Fibonacci<0> {
10.    enum { Sequence = 0 };
11. };
12.  
13. template<>
14. struct Fibonacci<1> {
15.    enum { Sequence = 1 };
16. };
17.  
18. template<int n>
19. class LoopFibonacci {
20. public:
21.    static inline void Print() {
22.       LoopFibonacci<n-1>::Print();
23.       Console::WriteLine(Fibonacci<n>::Sequence);
24.    }
25. };
26.  
27. template<>
28. class LoopFibonacci<0> {
29. public:
30.    static inline void Print() {
31.       Console::WriteLine(Fibonacci<0>::Sequence);
32.    }
33. };
34.  
35. int main(array<System::String ^> ^args) {
36.  
37.    LoopFibonacci<20>::Print();
38.    
39.    return 0;
40. }

Code is hidden, SHOW

[gmmastros]

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.

vb6Line number Off | Show | Select all

1. Option Explicit
2.  
3. Private Sub Command1_Click()
4.    
5.     Dim Start As Single
6.     Dim Number As Long
7.    
8.     If Not IsNumeric(txtNumberToCalculate.Text & ".0e0") Then
9.         Call MsgBox("The number to calculate must be a valid integer greater than 2.", vbInformation, "Fibonacci Sequence Error")
10.         Exit Sub
11.     End If
12.    
13.     Number = CLng(txtNumberToCalculate.Text)
14.    
15.     Start = Timer
16.     Screen.MousePointer = vbHourglass
17.     Call FibonacciSequence(Number)
18.     Debug.Print "Time: " & Timer - Start
19.     Screen.MousePointer = vbDefault
20.    
21. End Sub
22.  
23. Private Function FibonacciSequence(ByVal NumberToCalculate As Long) As String
24.  
25.     Dim arTemp() As String
26.    
27.     Dim i As Long
28.    
29.     ReDim arTemp(NumberToCalculate - 1)
30.    
31.     arTemp(0) = "0"
32.     arTemp(1) = "1"
33.      
34.     For i = 2 To NumberToCalculate - 1
35.         arTemp(i) = AddString(arTemp(i - 2), arTemp(i - 1))
36.     Next i
37.      
38.     txtResults.Text = Join(arTemp, ",")
39.  
40. End Function
41.  
42. Private Function AddString(ByVal String1 As String, ByVal String2 As String) As String
43.    
44.     Dim i As Long
45.     Dim Output() As String
46.     Dim CarryTheOne As Long
47.     Dim Digit1 As Long
48.     Dim Digit2 As Long
49.    
50.     If Len(String1) < Len(String2) Then
51.         String1 = Replace(Right(Space(Len(String2)) & String1, Len(String2)), " ", "0")
52.     Else
53.         String2 = Replace(Right(Space(Len(String1)) & String2, Len(String1)), " ", "0")
54.     End If
55.    
56.     ReDim Output(Len(String1))
57.     CarryTheOne = 0
58.     For i = Len(String1) To 1 Step -1
59.         Digit1 = Mid(String1, i, 1)
60.         Digit2 = Mid(String2, i, 1)
61.        
62.         Output(i) = (Digit1 + Digit2 + CarryTheOne) Mod 10
63.         If Digit1 + Digit2 + CarryTheOne > 9 Then
64.             CarryTheOne = 1
65.         Else
66.             CarryTheOne = 0
67.         End If
68.     Next
69.    
70.     If CarryTheOne = 1 Then
71.         Output(0) = "1"
72.     End If
73.     AddString = Join(Output, "")
74.    
75. End Function

Code is hidden, SHOW

[HarleyQuinn]

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

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

[sembee]

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

textLine number Off | Show | Select all

1. #light
2.  
3. let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0 + n1))) (1I,1I)
4.  
5. let first n = Seq.take n fibs

Code is hidden, SHOW

Claudio
http://www.fsharp.it

[AlexCuse]

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

[Emtucifor]

textLine number Off | Show | Select all

1. Sub Fibonacci()
2.     Dim A, B
3.     A = CDec(0)
4.     B = CDec(1)
5.     On Error GoTo Fibonacci_Exit
6.     Do
7.         Debug.Print A
8.         B = B + A
9.         Debug.Print B
10.         A = A + B
11.     Loop
12. Fibonacci_Exit:
13. End Sub

Code is hidden, SHOW

it calculates up to 50095301248058391139327916261, the 140th term. That's 50 octillion!

[chrissie1]

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

[tisodotsk]

My solution in PHP:

phpLine number Off | Show | Select all

1. <?php
2. //ltd5.php - LTD Puzzle 5: Calculating the Fibonacci Sequence
3. //via Topic2055: LTD Puzzle 5: Calculating the Fibonacci Sequence
4. //------------------------------------------------------------------------------
5. //limits:
6. //79 number exceed linear range (return 1.44723340247E+16)
7. //1478 number exceed the exponential range (return INF)
8. function FibonacciSequence($length)
9. {
10.     $first=0;
11.     $second=1;
12.     $sequence=$first.','.$second;
13.     for($i=2; $i <= $length; $i++){
14.         $sequence.=','.($new=$first+$second);
15.         $first=$second;
16.         $second=$new;
17.     }
18.     return $sequence;
19. }
20. //------------------------------------------------------------------------------
21. for($i=2;$i <= 78;$i++){
22.     echo 'FibonacciSequence('.$i.'): '.FibonacciSequence($i).'<br>';
23. }
24. //------------------------------------------------------------------------------
25. ?>

Code is hidden, SHOW

Output (first 10 lines):

textLine number Off | Hide | Select all

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

[luckenbach]

I chose to do it in perl this time for fun

perlLine number Off | Show | Select all

1. #!/usr/bin/perl
2.  
3. use strict;
4. use warnings;
5.  
6. #Inital values
7. my $a = '0';
8. my $b = '1';
9. my $i = '0';
10.  
11. print "How many Fibonacci digits should we calculate\n";
12.  
13. my $stop = <STDIN>;
14. chomp($stop);
15.  
16. while($stop >= $i){
17.         # now we add a+b
18.         my $next_number;
19.         $next_number = $a + $b;
20.         $i++;
21.         print $next_number .", ";
22.         $a = $b;
23.         $b = $next_number;
24. }
25.  

Code is hidden, SHOW

Made one a little shorter and less drawn out

perlLine number Off | Show | Select all

1. my ($i, $a, $b, $stop) = (("0") x 2, 1, $ARGV[0]);
2. while($stop >= $i){( $a, $b ) = ( $b, $a+$b ); $i++; print $b . "\n";}
3.  

Code is hidden, SHOW

[janroesner]

Ruby fun single liner:

rubyLine number Off | Show | Select all

1. puts 1.upto(100).inject([0,1]){|ary, number| ary.push(ary[-1]+ary[-2]); ary}

Code is hidden, SHOW

Cheers

[frob23]

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.

textLine number Off | Show | Select all

1. #!/usr/bin/dc
2. [Length of sequence to compute: ]n?sa0k2sb0sc1sd[lcdn[, ]nld+ldscsdlb1+dsb
3. la!<e]selexlc

Code is hidden, SHOW

This time with comments:

textLine number Off | Show | Select all

1. #!/usr/bin/dc
2. [Length of sequence to compute: ]n?sa   # Get the length to compute
3. 0k2sb0sc1sd             # Set up our variables
4.  
5. # e() -- Program Loop
6. [lcdn[, ]n      # Print c, leave c on stack
7. ld+ldscsd       # stack=c+d, c=d, d=stack
8. lb1+dsb         # b=b+1
9. la!<e           # if a!<b then e()
10. ]selex          # Save e() and execute it
11. lcn         # Print final number in sequence

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.

textLine number Off | Show | Select all

1. #!/usr/bin/dc
2. # Get the length to compute
3. [Length of sequence to compute: ]n?sa
4. 0k2sb0sc1sd # Set up our variables
5. 5000dsfsh   # MAX_LOOP at one time
6.  
7. [lasflexq]sg
8. [lcdn[, ]n      # Print c, leave c on stack
9. ld+ldscsd       # stack=c+d, c=d, d=stack
10. lb1+dsb         # b=b+1
11. lf!<e           # if f!<b then e()
12. ]se         # Save e() and execute it
13.  
14. [lfla>e         # if a>f then f=a
15. lalf>g          # if f>a: g()
16. lflh+sf         # Add MAX_LOOP to f
17. lix]si          # LOOP
18. lix         # Call main loop
19. lcn         # Print final number in sequence

Code is hidden, SHOW

[whitekalashnikov]

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

luaLine number Off | Show | Select all

1. local i,j = 0,1
2. for x = 1,100 do
3.     print(i)
4.     i = i + j
5.     print(j)
6.     j = i + j
7. end

Code is hidden, SHOW

The output:

outputLine number Off | Show | Select all

1. 0
2. 1
3. 1
4. 2
5. 3
6. 5
7. 8
8. 13
9. 21
10. 34
11. 55
12. 89
13. 144
14. 233
15. 377
16. 610
17. 987
18. 1597
19. 2584
20. 4181
21. 6765
22. 10946
23. 17711
24. 28657
25. 46368
26. .
27. .
28. .
29. 6.6233869353085e+040
30. 1.0716865181971e+041
31. 1.734025211728e+041

Code is hidden, SHOW