Factorial: Difference between revisions
→C# - Arbitrary Precision: added faster algo
(Added Odin variant) |
(→C# - Arbitrary Precision: added faster algo) |
||
Line 1,888:
===Arbitrary Precision===
{{libheader|System.Numerics}}
<code>FactorialQ()</code> can calculate 1000000! in around 40 seconds over at Tio.run.</br>
The "product tree" algorithm multiplies pairs of items on a list until there is only one item. Even though around the same number of multiply operations occurs (compared to the plain "accumulator" method), this is faster because the "bigger" numbers are generated near the end of the algorithm, instead of around halfway through. There is a significant space overhead incurred due to the creation of the temporary array to hold the partial results. The additional time overhead for array creation is negligible compared with the time savings of not dealing with the very large numbers until near the end of the algorithm.</br>
For example, 200000!, when one sums up the number of digits of each product for all 199999 multiplications, the plain method is nearly 93 billion, while the product tree method is only about 17.3 million.
<syntaxhighlight lang="csharp">using System;
using System.Numerics;
Line 1,902 ⟶ 1,905:
{
return Enumerable.Range(1, number).Aggregate(new BigInteger(1), (acc, num) => acc * num);
}
static public BI FactorialQ(int number) // functional quick, uses prodtree method
{
var s = Enumerable.Range(1, number).Select(num => new BI(num)).ToArray();
int top = s.Length, nt, i, j;
while (top > 1) {
for (i = 0, j = top, nt = top >> 1; i < nt; i++) s[i] *= s[--j];
top = nt + ((top & 1) == 1 ? 1 : 0);
}
return s[0];
}
| |||