Fibonacci sequence: Difference between revisions

← Older editNewer edit →
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;
 
static class QuikFibProgram
{
// A sparse array of values calculated along the way
private static SortedList<int, BigIntegerBI> sl = new SortedList<int, BigIntegerBI>();
 
// 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.
// Algorithm from here: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section3
public static BigIntegerBI Fsl(int n)
{
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
▲ void IfNec(int x) { if (!sl.ContainsKey(nx)) sl.Add(nx, Fsl(nx)); }
▲ // SquareHelper function to square a BigInteger
▲ BI sqr(BI x) { return nx * nx; }
}
 
// Conventional iteration method (not used here)
public static BigIntegerBI Fm(BigIntegerBI n)
{
if (n < 2) return n; BigIntegerBI cur = 0, pre = 1;
for (int i = 0; i <= n - 1; i++) { BigIntegerBI sum = cur + pre; pre = cur; cur = sum; }
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();
DateTime st = DateTime.Now;
Console.WriteLineWrite("{0:n3} ms to calculate the {1:n0}th Fibonacci number, ",▼
BigInteger v = Fsl(num);
(DateTimesw.Now - st)Elapsed.TotalMilliseconds, num);▼
▲ Console.WriteLine("{0:n3} ms to calculate the {1:n0}th Fibonacci number,",
Console.WriteLine("number of digits is {0}", vsvlen = (int)Math.LengthCeiling(BI.Log10(v)));▼
▲ (DateTime.Now - st).TotalMilliseconds, num);
stif =(vlen DateTime.Now;< 10000) {
string vs = sw.Restart(); Console.WriteLine(v); sw.ToStringStop();
Console.WriteLine("{0:n3} secondsms to convertwrite it to athe stringconsole.", (DateTimesw.Now - st)Elapsed.TotalSecondsTotalMilliseconds);
} else▼
▲ Console.WriteLine("number of digits is {0}", vs.Length);
Console.WriteLineWrite("partial: {0}...{1}", vsv / BI.SubstringPow(110, 35vlen - digs), vsv % BI.SubstringPow(vs.Length -10, 35digs));▼
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>
{{out}}
<pre>179137.978209 ms to calculate the 2,000,000th Fibonacci number, number of digits is 417975
partial: 5312949175076415430516606545038251685312949175076415430516606545038251...91799493108960825129188777803453125▼
4.728 seconds to convert to a string.
number of digits is 417975
▲partial: 53129491750764154305166065450382516...91799493108960825129188777803453125
</pre>
 
Retrieved from "https://rosettacode.org/wiki/Fibonacci_sequence"