3 ms·
probably not very big. factorials are pretty boring in the sense that it's relatively trivial to compute a factorial almost as big as your hard drive. 99% of th
by adgjlsfhk1 1y ago
probably not very big. factorials are pretty boring in the sense that it's relatively trivial to compute a factorial almost as big as your hard drive. 99% of the time will happen in a single multiply
- cperciva 1y ago99% of the time will happen in a single multiply Far from it. Asymptotically it's a proportion 2/log(N) of the compute cost.
- LegionMammal978 1y agoYeah, most algorithms that run in O(n polylog(n)) time, including most divide-and-conquer bigint arithmetic, will ultimately be dominated by how much memory you have available. For some experiments a while back, I would create a terabyte-long swapfile to extend the range of what GMP could do, and it still filled up within a couple CPU-weeks at most.