Anonymous user
Left factorials: Difference between revisions
→{{header|Perl 6}}: add 2nd algo that is O(N) rather than O(N^3) or so
(→{{header|Haskell}}: Incomplete!) |
(→{{header|Perl 6}}: add 2nd algo that is O(N) rather than O(N^3) or so) |
||
Line 169:
!9000 has 31678 digits.
!10000 has 35656 digits.</pre>
While the code above seems like a pretty decent "mathematical" way to write this, it's far from efficient, since it's recalculating every factorial many times for each individual left factorial, not to mention for each subsequent left factorial, so it's something like an O(N^3) algorithm, not even counting the sizes of the numbers as one of the dimensions. In Perl 6, a more idiomatic way is to write these functions as constant "triangular reduction" sequences; this works in O(N)-ish time because the sequences never have to recalculate a prior result:
<lang perl6>constant fact = 1, [\*] 1..*;
constant leftfact = 0, [\+] fact;
printf "!%d = %s\n", $_, leftfact[$_] for 0 ... 10, 20 ... 110;
printf "!%d has %d digits.\n", $_, leftfact[$_].chars for 1000, 2000 ... 10000;</lang>
Note that we just use subscripting on the list rather than an explicit function call to retrieve the desired values. If you time these two solutions, the second will run about 280 times faster than the first.
In this case, since we aren't actually interested in the factorials, we could have just written combined the two definitions into one:
<lang perl6>constant leftfact = 0, [\+] 1, [\*] 1..*;</lang>
(No significant difference in run time.)
=={{header|Python}}==
| |||