Rosetta Code

Fibonacci sequence: Difference between revisions

Page Discussion

Fibonacci sequence (view source)

Revision as of 19:17, 23 February 2019

95 bytes added ,  5 years ago
m
→‎Arbitrary Precision: streamline code, remove Linq requirement.
(Latitude language added)
m (→‎Arbitrary Precision: streamline code, remove Linq requirement.)
Line 2,153:
===Arbitrary Precision===
{{libheader|System.Numerics}}
This large step recurrence routine can calculate the two millionth Fibonacci number in aboutunder 1 / 5 second at tio.run. This routine can generate the fifty millionth Fibonacci number in aboutunder 30 seconds at tio.run. The unused conventional iterative method times out at two million on tio.run, you can only go to around 1,290,000 or so to keep the calculation time (plus string conversion time) under the 60 second timeout limit there. ItWhen using this large step recurrence method, it takes around 225 seconds to convert the two millionth Fibonacci number (417975 digits) tointo a string (inso orderthat toone may count those digits).
 
<lang csharp>using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
 
Line 2,169 ⟶ 2,168:
public static BigInteger Fsl(int n)
{
ifint n2 = (n <>> 21; if (!sl.ContainsKey(n2)) returnsl.Add(n2, nFsl(n2));
int n2 = n >> 1;▼
if ((n & 1) != 1)
{
if (!sl.IndexOfKeyContainsKey(n2) <- 01)) sl.Add(n2 - 1, Fsl(n2 - 1));
ifreturn (2 * sl.IndexOfKey([n2 - 1)] < 0)+ sl.Add([n2]) -* 1, Fsl(sl[n2 - 1))];
} else {▼
return ((2 * sl.ElementAt(sl.IndexOfKey(n2 - 1)).Value) + sl.ElementAt(sl.IndexOfKey(n2)).Value) *
if (!sl.ContainsKey(n2 + 1)) sl.Add(n2 + 1, sl.ElementAt(sl.IndexOfKeyFsl(n2 + 1)).Value;
return BigInteger.Pow(sl.ElementAt(sl.IndexOfKey([n2)).Value], 2) + BigInteger.Pow(sl[n2 + 1], 2);▼
}▼
▲ else
{▼
if (sl.IndexOfKey(n2) < 0) sl.Add(n2, Fsl(n2));
if (sl.IndexOfKey(n2 + 1) < 0) sl.Add(n2 + 1, Fsl(n2 + 1));
▲ return BigInteger.Pow(sl.ElementAt(sl.IndexOfKey(n2)).Value, 2) +
BigInteger.Pow(sl.ElementAt(sl.IndexOfKey(n2 + 1)).Value, 2);
}
}
Line 2,192 ⟶ 2,184:
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,198 ⟶ 2,190:
public static void Main()
{
▲ int n2num = n >> 12_000_000;
DateTime st = DateTime.Now;
BigIntegersl.Add(0, v0); = Fslsl.Add(2_000_0001, 1);
BigInteger v = Fsl(num);
Console.WriteLine("{0:n3} ms to calculate it,", (DateTime.Now - st).TotalMilliseconds);▼
Console.WriteLine("{0:n3} ms to calculate the {1:n0}th Fibonacci number,",
▲ Console.WriteLine("{0:n3} ms to calculate it,", (DateTime.Now - st).TotalMilliseconds, num);
st = DateTime.Now;
string vs = v.ToString();
Line 2,211 ⟶ 2,206:
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}}
<pre>191176.946510 ms to calculate itthe 2,000,000th Fibonacci number,
214.847720 seconds to convert to a string.
number of digits is 417975</pre>
partial: 53129491750764154305166065450382516...91799493108960825129188777803453125</pre>
 
=={{header|Cat}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/62785"