Fibonacci sequence: Difference between revisions
m
→Arbitrary Precision: a little more streamlining
m (→BigInteger, speedier method: streamlined code) |
m (→Arbitrary Precision: a little more streamlining) |
||
Line 2,164:
private static SortedList<int, BigInteger> sl = new SortedList<int, BigInteger>();
// Square a BigInteger
// This routine calls itself as needed, but doesn't need to evaluate every number up to n.▼
public static BigInteger sqr(BigInteger n)
// Helper routine for Fsl(). It adds an entry to the sorted list when necessary
public static void IfNec(int n)
▲ // This routine
// Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
public static BigInteger Fsl(int n)
{
if (n < 2) return n;
int n2 = n >> 1
▲ {
▲ if (!sl.ContainsKey(n2 - 1)) sl.Add(n2 - 1, Fsl(n2 - 1));
▲ return (2 * sl[n2 - 1] + sl[n2]) * sl[n2];
▲ } else {
▲ }
}
Line 2,184 ⟶ 2,189:
{
if (n < 2) return n; BigInteger cur = 0, pre = 1;
for (int i = 0; i <= n - 1; i++) { BigInteger sum = cur + pre; pre = cur; cur = sum; }
return cur;
}
Line 2,200 ⟶ 2,204:
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)
{
Line 2,208 ⟶ 2,211:
}
else
Console.WriteLine("partial: {0}...{1}", vs.Substring(1, 35), vs.Substring(vs.Length - 35));▼
▲ {
▲ Console.WriteLine("partial: {0}...{1}", vs.Substring(1,35), vs.Substring(vs.Length-35));
▲ }
}
}</lang>
{{out}}
<pre>
4.
number of digits is 417975
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125
</pre>
=={{header|Cat}}==
|