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]

[hide]Sub Fibonacci()
Dim A, B
A = CDec(0)
B = CDec(1)
On Error GoTo Fibonacci_Exit
Do
Debug.Print A
B = B + A
Debug.Print B
A = A + B
Loop
Fibonacci_Exit:
End Sub[/hide]
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