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


⚫
' A sparse array of values calculated along the way
⚫
' Square a BigInteger
Function sqr(ByVal n As BigInteger) As BigInteger
Dim sl As SortedList(Of Integer, BigInteger) = New SortedList(Of Integer, BigInteger)()
⚫
Return n * n
⚫
End Function


⚫
' Square a BigInteger
⚫
' A sparse array of values calculated along the way
Dim sl As SortedList(Of Integer, BigInteger) = New SortedList(Of Integer, BigInteger)()
Function sqr(ByVal n As BigInteger) As BigInteger
⚫
Return n * n
⚫
End Function


' This routine calls itself as needed, but doesn't need to evaluate every number up to n.
' Helper routine for Fsl(). It adds an entry to the sorted list when necessary
Sub IfNec(n as integer)
⚫
' Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
⚫
If Not sl.ContainsKey(n) Then sl.Add(n, Fsl(n))
⚫
Function Fsl(ByVal n As Integer) As BigInteger
⚫
End Sub
⚫
If n < 2 Then Return n

⚫
Dim n2 as Integer = n >> 1
' This routine is semi-recursive, but doesn't need to evaluate every number up to n.
If (n And 1) <> 1 Then
⚫
' Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
⚫
If sl.IndexOfKey(n2) < 0 Then sl.Add(n2, Fsl(n2))
⚫
Function Fsl(ByVal n As Integer) As BigInteger
If sl.IndexOfKey(n2 - 1) < 0 Then sl.Add(n2 - 1, Fsl(n2 - 1))
⚫
If n < 2 Then Return n
Return ((2 * sl.ElementAt(sl.IndexOfKey(n2 - 1)).Value) + sl.ElementAt(sl.IndexOfKey(n2)).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)))
⚫
Else
⚫
End Function
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)
⚫
End If
⚫
End Function


' Conventional iteration method (not used here)
' Conventional iteration method (not used here)
Function Fm(ByVal n As BigInteger) As BigInteger
Function Fm(ByVal n As BigInteger) As BigInteger
If n < 2 Then Return n
If n < 2 Then Return n
Dim cur As BigInteger = 0, pre As BigInteger = 1
Dim cur As BigInteger = 0, pre As BigInteger = 1
For i As Integer = 0 To n - 1
For i As Integer = 0 To n - 1
Dim sum As BigInteger = cur + pre
Dim sum As BigInteger = cur + pre
pre = cur : cur = sum
pre = cur : cur = sum
Next
Next : Return cur
⚫
End Function
Return cur
⚫
End Function


Sub Main()
Sub Main()
⚫
Dim num As Integer = 2_000_000
Dim st As DateTime = DateTime.Now
Dim st As DateTime = DateTime.Now
Dim v As BigInteger = Fsl(2_000_000)
Dim v As BigInteger = Fsl(num)
Console.WriteLine("{0:n3} ms to calculate it,", (DateTime.Now - st).TotalMilliseconds)
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)
⚫
Else
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>188.536 ms to calculate it,
<pre>177.831 ms to calculate the 2,000,000th Fibonacci number,
22.008 seconds to convert to a string.
4.649 seconds to convert to a string.
number of digits is 417975</pre>
number of digits is 417975
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125
</pre>


=={{header|Wart}}==
=={{header|Wart}}==
Retrieved from "https://rosettacode.org/wiki/Fibonacci_sequence"