On the complexity of calculating factorials |
| |
Authors: | Peter B Borwein |
| |
Institution: | Department of Mathematics, Statistics, and Computing Science, Dalhousie University, Halifax, Nova Scotia, Canada B3H 4H8 |
| |
Abstract: | It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)2) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n2 log n) and also to computing n! by binary splitting which is O(log nM(n log n)). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|