Fibonacci sequence: Difference between revisions
Content added Content deleted
m (→Arbitrary Precision: accidently omitted line in last edit) |
m (→BigInteger, speedier method: streamlined code) |
||
Line 10,397: | Line 10,397: | ||
This method doesn't need to iterate the entire list, and is much faster. The 2000000 (two millionth) Fibonacci number can be found in a fraction of a second.<br/>Algorithm from [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html here, see section 3, ''Finding Fibonacci Numbers Fully''.] |
This method doesn't need to iterate the entire list, and is much faster. The 2000000 (two millionth) Fibonacci number can be found in a fraction of a second.<br/>Algorithm from [http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html here, see section 3, ''Finding Fibonacci Numbers Fully''.] |
||
<lang vbnet>Imports System |
<lang vbnet>Imports System |
||
Imports System.Collections.Generic |
|||
Imports System.Numerics |
Imports System.Numerics |
||
Module Module1 |
Module Module1 |
||
⚫ | |||
⚫ | |||
Dim sl As SortedList(Of Integer, BigInteger) = New SortedList(Of Integer, BigInteger)() |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
Function sqr(ByVal n As BigInteger) As BigInteger |
|||
⚫ | |||
⚫ | |||
' Helper routine for Fsl(). It adds an entry to the sorted list when necessary |
|||
Sub IfNec(n as integer) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
' This routine is semi-recursive, but doesn't need to evaluate every number up to n. |
|||
If (n And 1) <> 1 Then |
|||
⚫ | |||
⚫ | |||
⚫ | |||
If sl.IndexOfKey(n2 - 1) < 0 Then sl.Add(n2 - 1, Fsl(n2 - 1)) |
|||
⚫ | |||
Return ((2 * sl.ElementAt(sl.IndexOfKey(n2 - 1)).Value) + sl.ElementAt(sl.IndexOfKey(n2)).Value) * |
|||
Dim n2 As Integer = n >> 1, pm As Integer = n2 + ((n And 1) << 1) - 1 : IfNec(n2) : IfNec(pm) |
|||
Return If(n2 > pm, (2 * sl(pm) + sl(n2)) * sl(n2), sqr(sl(n2)) + sqr(sl(pm))) |
|||
⚫ | |||
⚫ | |||
If sl.IndexOfKey(n2) < 0 Then sl.Add(n2, Fsl(n2)) |
|||
If sl.IndexOfKey(n2 + 1) < 0 Then sl.Add(n2 + 1, Fsl(n2 + 1)) |
|||
Return sqr(sl.ElementAt(sl.IndexOfKey(n2)).Value) + sqr(sl.ElementAt(sl.IndexOfKey(n2 + 1)).Value) |
|||
⚫ | |||
⚫ | |||
' Conventional iteration method (not used here) |
|||
Function Fm(ByVal n As BigInteger) As BigInteger |
|||
If n < 2 Then Return n |
|||
Dim cur As BigInteger = 0, pre As BigInteger = 1 |
|||
For i As Integer = 0 To n - 1 |
|||
Dim sum As BigInteger = cur + pre |
|||
pre = cur : cur = sum |
|||
Next : Return cur |
|||
⚫ | |||
Return cur |
|||
⚫ | |||
Sub Main() |
Sub Main() |
||
⚫ | |||
Dim st As DateTime = DateTime.Now |
Dim st As DateTime = DateTime.Now |
||
Dim v As BigInteger = Fsl( |
Dim v As BigInteger = Fsl(num) |
||
Console.WriteLine("{0:n3} ms to calculate |
Console.WriteLine("{0:n3} ms to calculate the {1:n0}th Fibonacci number,", |
||
(DateTime.Now - st).TotalMilliseconds, num) |
|||
st = DateTime.Now |
st = DateTime.Now |
||
Dim vs As String = v.ToString() |
Dim vs As String = v.ToString() |
||
Console.WriteLine("{0:n3} seconds to convert to a string.", (DateTime.Now - st).TotalSeconds) |
Console.WriteLine("{0:n3} seconds to convert to a string.", (DateTime.Now - st).TotalSeconds) |
||
Console.WriteLine("number of digits is {0}", vs.Length) |
Console.WriteLine("number of digits is {0}", vs.Length) |
||
' the following is executed conditionally due to the large size |
|||
If vs.Length < 10000 Then |
If vs.Length < 10000 Then |
||
st = DateTime.Now |
st = DateTime.Now |
||
Console.WriteLine(vs) |
Console.WriteLine(vs) |
||
Console.WriteLine("{0:n3} ms to write it to the console.", (DateTime.Now - st).TotalMilliseconds) |
Console.WriteLine("{0:n3} ms to write it to the console.", (DateTime.Now - st).TotalMilliseconds) |
||
⚫ | |||
Console.WriteLine("partial: {0}...{1}", vs.Substring(1, 35), vs.Substring(vs.Length - 35)) |
|||
End If |
End If |
||
End Sub |
End Sub |
||
End Module</lang> |
End Module</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre>177.831 ms to calculate the 2,000,000th Fibonacci number, |
||
4.649 seconds to convert to a string. |
|||
number of digits is 417975 |
number of digits is 417975 |
||
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125 |
|||
</pre> |
|||
=={{header|Wart}}== |
=={{header|Wart}}== |