Fibonacci sequence: Difference between revisions
Content deleted Content added
m →Arbitrary Precision: noticed that the first digit was missing of the "partial" string. spruced it up a bit, removed string conversion |
m →BigInteger, speedier method: noticed the first digit was missing, spruced it up a little, dropped string conversion |
||
| Line 12,401: | Line 12,401: | ||
<lang vbnet>Imports System |
<lang vbnet>Imports System |
||
Imports System.Collections.Generic |
Imports System.Collections.Generic |
||
Imports System.Numerics |
Imports BI = System.Numerics.BigInteger |
||
Module Module1 |
Module Module1 |
||
' A sparse array of values calculated along the way |
' A sparse array of values calculated along the way |
||
Dim sl As SortedList(Of Integer, |
Dim sl As SortedList(Of Integer, BI) = New SortedList(Of Integer, BI)() |
||
' Square a BigInteger |
' Square a BigInteger |
||
Function sqr(ByVal n As |
Function sqr(ByVal n As BI) As BI |
||
Return n * n |
Return n * n |
||
End Function |
End Function |
||
' Helper routine for Fsl(). It adds an entry to the sorted list when necessary |
' Helper routine for Fsl(). It adds an entry to the sorted list when necessary |
||
Sub IfNec(n |
Sub IfNec(n As Integer) |
||
If Not sl.ContainsKey(n) Then sl.Add(n, Fsl(n)) |
If Not sl.ContainsKey(n) Then sl.Add(n, Fsl(n)) |
||
End Sub |
End Sub |
||
| Line 12,420: | Line 12,420: | ||
' This routine is semi-recursive, but doesn't need to evaluate every number up to n. |
' This routine is semi-recursive, but doesn't need to evaluate every number up to n. |
||
' Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3 |
' Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3 |
||
Function Fsl(ByVal n As Integer) As |
Function Fsl(ByVal n As Integer) As BI |
||
If n < 2 Then Return n |
If n < 2 Then Return n |
||
Dim n2 As Integer = n >> 1, pm As Integer = n2 + ((n And 1) << 1) - 1 : IfNec(n2) : IfNec(pm) |
Dim n2 As Integer = n >> 1, pm As Integer = n2 + ((n And 1) << 1) - 1 : IfNec(n2) : IfNec(pm) |
||
| Line 12,427: | Line 12,427: | ||
' Conventional iteration method (not used here) |
' Conventional iteration method (not used here) |
||
Function Fm(ByVal n As |
Function Fm(ByVal n As BI) As BI |
||
If n < 2 Then Return n |
If n < 2 Then Return n |
||
Dim cur As |
Dim cur As BI = 0, pre As BI = 1 |
||
For i As Integer = 0 To n - 1 |
For i As Integer = 0 To n - 1 |
||
Dim sum As |
Dim sum As BI = cur + pre : pre = cur : cur = sum : Next : Return cur |
||
pre = cur : cur = sum |
|||
Next : Return cur |
|||
End Function |
End Function |
||
Sub Main() |
Sub Main() |
||
Dim num As Integer = 2_000_000 |
Dim vlen As Integer, num As Integer = 2_000_000, digs As Integer = 35 |
||
Dim |
Dim sw As System.Diagnostics.Stopwatch = System.Diagnostics.Stopwatch.StartNew() |
||
Dim v As |
Dim v As BI = Fsl(num) : sw.[Stop]() |
||
Console. |
Console.Write("{0:n3} ms to calculate the {1:n0}th Fibonacci number, ", sw.Elapsed.TotalMilliseconds, num) |
||
| ⚫ | |||
(DateTime.Now - st).TotalMilliseconds, num) |
|||
If vlen < 10000 Then |
|||
sw.Restart() : Console.WriteLine(v) : sw.[Stop]() |
|||
Console.WriteLine("{0:n3} |
Console.WriteLine("{0:n3} ms to write it to the console.", sw.Elapsed.TotalMilliseconds) |
||
| ⚫ | |||
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) |
|||
Else |
Else |
||
Console. |
Console.Write("partial: {0}...{1}", v / BI.Pow(10, vlen - digs), v Mod BI.Pow(10, digs)) |
||
End If |
End If |
||
End Sub |
End Sub |
||
End Module</lang> |
End Module</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre>120.374 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975 |
||
| ⚫ | |||
4.649 seconds to convert to a string. |
|||
number of digits is 417975 |
|||
| ⚫ | |||
</pre> |
|||
=={{header|Vlang}}== |
=={{header|Vlang}}== |
||