Fibonacci sequence: Difference between revisions
Content deleted Content added
m →{{header|REXX}}: added whitespace. |
m →Arbitrary Precision: noticed that the first digit was missing of the "partial" string. spruced it up a bit, removed string conversion |
||
Line 2,215:
<lang csharp>using System;
using System.Collections.Generic;
using BI = System.Numerics.BigInteger;
{
// A sparse array of values calculated along the way
// Square a BigInteger▼
return n * n;▼
// Helper routine for Fsl(). It adds an entry to the sorted list when necessary▼
if (!sl.ContainsKey(n)) sl.Add(n, Fsl(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
{
if (n < 2) return n;
int n2 = n >> 1, pm = n2 + ((n & 1) << 1) - 1; IfNec(n2); IfNec(pm);
return n2 > pm ? (2 * sl[pm] + sl[n2]) * sl[n2] : sqr(sl[n2]) + sqr(sl[pm]);
▲ // Helper routine for Fsl(). It adds an entry to the sorted list when necessary
}
// Conventional iteration method (not used here)
public static
{
if (n < 2) return n;
for (int i = 0; i <= n - 1; i++) {
return cur;
}
public static void Main()
{
int num = 2_000_000, digs = 35, vlen;
var sw = System.Diagnostics.Stopwatch.StartNew(); var v = Fsl(num); sw.Stop();
▲ Console.WriteLine("{0:n3} ms to calculate the {1:n0}th Fibonacci number,",
▲ (DateTime.Now - st).TotalMilliseconds, num);
Console.WriteLine("{0:n3}
} else▼
▲ Console.WriteLine("number of digits is {0}", vs.Length);
Console.
▲ else
▲ Console.WriteLine("partial: {0}...{1}", vs.Substring(1, 35), vs.Substring(vs.Length - 35));
}
}</lang>
{{out}}
<pre>
partial:
▲partial: 53129491750764154305166065450382516...91799493108960825129188777803453125
</pre>
|