Fibonacci sequence: Difference between revisions

Content added Content deleted
m (→‎BigInteger, speedier method: streamlined code)
m (→‎Arbitrary Precision: a little more streamlining)
Line 2,164: Line 2,164:
private static SortedList<int, BigInteger> sl = new SortedList<int, BigInteger>();
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)
⚫
{
⚫
return n * n;
⚫
}

// Helper routine for Fsl(). It adds an entry to the sorted list when necessary
public static void IfNec(int n)
⚫
{
⚫
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
// Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
public static BigInteger Fsl(int n)
public static BigInteger Fsl(int n)
{
{
if (n < 2) return n;
if (n < 2) return n;
int n2 = n >> 1; if (!sl.ContainsKey(n2)) sl.Add(n2, Fsl(n2));
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]);
if ((n & 1) != 1)
⚫
{
⚫
if (!sl.ContainsKey(n2 - 1)) sl.Add(n2 - 1, Fsl(n2 - 1));
⚫
return (2 * sl[n2 - 1] + sl[n2]) * sl[n2];
⚫
} else {
if (!sl.ContainsKey(n2 + 1)) sl.Add(n2 + 1, Fsl(n2 + 1));
return BigInteger.Pow(sl[n2], 2) + BigInteger.Pow(sl[n2 + 1], 2);
⚫
}
}
}


Line 2,184: Line 2,189:
{
{
if (n < 2) return n; BigInteger cur = 0, pre = 1;
if (n < 2) return n; BigInteger cur = 0, pre = 1;
for (int i = 0; i <= n - 1; i++)
for (int i = 0; i <= n - 1; i++) { BigInteger sum = cur + pre; pre = cur; cur = sum; }
{ BigInteger sum = cur + pre; pre = cur; cur = sum; }
return cur;
return cur;
}
}
Line 2,200: Line 2,204:
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)
if (vs.Length < 10000)
{
{
Line 2,208: Line 2,211:
}
}
else
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>
}</lang>
{{out}}
{{out}}
<pre>175.416 ms to calculate the 2,000,000th Fibonacci number,
<pre>179.978 ms to calculate the 2,000,000th Fibonacci number,
4.651 seconds to convert to a string.
4.728 seconds to convert to a string.
number of digits is 417975
number of digits is 417975
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125</pre>
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125
</pre>


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