Fibonacci sequence: Difference between revisions

Content added Content deleted
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: Line 2,215:
<lang csharp>using System;
<lang csharp>using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Numerics;
using BI = System.Numerics.BigInteger;

static class QuikFib
class Program
{
{
// A sparse array of values calculated along the way
// A sparse array of values calculated along the way
private static SortedList<int, BigInteger> sl = new SortedList<int, BigInteger>();
static SortedList<int, BI> sl = new SortedList<int, BI>();

⚫
// Square a BigInteger
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.
// 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)
static BI Fsl(int n)
{
{
if (n < 2) return n;
if (n < 2) return n;
int n2 = n >> 1, pm = n2 + ((n & 1) << 1) - 1; IfNec(n2); IfNec(pm);
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]);
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
⚫
void IfNec(int x) { if (!sl.ContainsKey(x)) sl.Add(x, Fsl(x)); }
⚫
// Helper function to square a BigInteger
⚫
BI sqr(BI x) { return x * x; }
}
}

// Conventional iteration method (not used here)
// Conventional iteration method (not used here)
public static BigInteger Fm(BigInteger n)
public static BI Fm(BI n)
{
{
if (n < 2) return n; BigInteger cur = 0, pre = 1;
if (n < 2) return n; BI cur = 0, pre = 1;
for (int i = 0; i <= n - 1; i++) { BigInteger sum = cur + pre; pre = cur; cur = sum; }
for (int i = 0; i <= n - 1; i++) { BI sum = cur + pre; pre = cur; cur = sum; }
return cur;
return cur;
}
}

public static void Main()
public static void Main()
{
{
int num = 2_000_000;
int num = 2_000_000, digs = 35, vlen;
var sw = System.Diagnostics.Stopwatch.StartNew(); var v = Fsl(num); sw.Stop();
DateTime st = DateTime.Now;
⚫
Console.Write("{0:n3} ms to calculate the {1:n0}th Fibonacci number, ",
BigInteger v = Fsl(num);
⚫
sw.Elapsed.TotalMilliseconds, num);
⚫
Console.WriteLine("{0:n3} ms to calculate the {1:n0}th Fibonacci number,",
⚫
Console.WriteLine("number of digits is {0}", vlen = (int)Math.Ceiling(BI.Log10(v)));
⚫
(DateTime.Now - st).TotalMilliseconds, num);
st = DateTime.Now;
if (vlen < 10000) {
string vs = v.ToString();
sw.Restart(); Console.WriteLine(v); sw.Stop();
Console.WriteLine("{0:n3} seconds to convert to a string.", (DateTime.Now - st).TotalSeconds);
Console.WriteLine("{0:n3} ms to write it to the console.", sw.Elapsed.TotalMilliseconds);
⚫
} else
⚫
Console.WriteLine("number of digits is {0}", vs.Length);
⚫
Console.Write("partial: {0}...{1}", v / BI.Pow(10, vlen - digs), v % BI.Pow(10, digs));
if (vs.Length < 10000)
{
st = DateTime.Now;
Console.WriteLine(vs);
Console.WriteLine("{0:n3} ms to write it to the console.", (DateTime.Now - st).TotalMilliseconds);
}
⚫
else
⚫
Console.WriteLine("partial: {0}...{1}", vs.Substring(1, 35), vs.Substring(vs.Length - 35));
}
}
}</lang>
}</lang>
{{out}}
{{out}}
<pre>179.978 ms to calculate the 2,000,000th Fibonacci number,
<pre>137.209 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975
⚫
partial: 85312949175076415430516606545038251...91799493108960825129188777803453125
4.728 seconds to convert to a string.
number of digits is 417975
⚫
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Fibonacci_sequence"