Fibonacci sequence: Difference between revisions
m
→BigInteger, speedier method: streamlined code
m (→Arbitrary Precision: accidently omitted line in last edit) |
m (→BigInteger, speedier method: streamlined code) |
||
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''.]
<lang vbnet>Imports System
Imports System.Collections.Generic
Imports System.Numerics
Module Module1
' Square a BigInteger▼
Dim sl As
Return n * n▼
End Function▼
▲ ' A sparse array of values calculated along the way
Function sqr(ByVal
Sub IfNec(n as integer)
' Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3▼
Function Fsl(ByVal n As Integer) As BigInteger▼
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 sl.IndexOfKey(n2) < 0 Then sl.Add(n2, Fsl(n2))
Dim n2 As Integer = n >> 1, pm As Integer = n2 + ((n And 1) << 1) - 1
Return If(n2 > pm, (2 * sl(pm) + sl(n2)) * sl(n2), sqr(sl(n2)) + sqr(sl(pm)))
Else▼
▲ End If
▲ End Function
Next : Return
▲ End Function
Sub Main()
Dim st As DateTime = DateTime.Now
Dim v As BigInteger = Fsl(
Console.WriteLine("{0:n3} ms to calculate
(DateTime.Now - st).TotalMilliseconds, num)
st = DateTime.Now
Dim vs As String = v.ToString()
Console.WriteLine("{0:n3} seconds to convert to a string.", (DateTime.Now - st).TotalSeconds)
Console.WriteLine("number of digits is {0}", vs.Length)
If vs.Length < 10000 Then
st = DateTime.Now
Console.WriteLine(vs)
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 Sub
End Module</lang>
{{out}}
<pre>
number of digits is 417975
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125
</pre>
=={{header|Wart}}==
| |||