Editing Factorial (section)

==Properties==
===Growth and approximation===
[[File:Mplwp factorial stirling loglog2.svg|thumb|Comparison of the factorial, Stirling's approximation, and the simpler approximation {{nowrap|<math>(n/e)^n</math>,}} on a doubly logarithmic scale]]
[[File:Stirling series relative error.svg|thumb|upright=1.6|[[Relative error]] in a truncated Stirling series vs. number of terms]]
{{main|Stirling's approximation}}

As a function {{nowrap|of <math>n</math>,}} the factorial has faster than [[exponential growth]], but grows more slowly than a [[double exponential function]].<ref>{{cite book | last = Cameron | first = Peter J. | author-link = Peter Cameron (mathematician) | contribution = 2.4: Orders of magnitude | isbn = 978-0-521-45133-8 | pages = 12–14 | publisher = Cambridge University Press | title = Combinatorics: Topics, Techniques, Algorithms | year = 1994}}</ref> Its growth rate is similar {{nowrap|to <math>n^n</math>,}} but slower by an exponential factor. One way of approaching this result is by taking the [[natural logarithm]] of the factorial, which turns its product formula into a sum, and then estimating the sum by an integral:
<math display="block">\ln n! = \sum_{x=1}^n \ln x \approx \int_1^n\ln x\, dx=n\ln n-n+1.</math>
Exponentiating the result (and ignoring the negligible <math>+1</math> term) approximates <math>n!</math> as {{nowrap|<math>(n/e)^n</math>.<ref>{{cite book | last = Magnus | first = Robert | contribution = 11.10: Stirling's approximation | contribution-url = https://books.google.com/books?id=5hvxDwAAQBAJ&pg=PA391 | doi = 10.1007/978-3-030-46321-2 | isbn = 978-3-030-46321-2 | location = Cham | mr = 4178171 | page = 391 | publisher = Springer | series = Springer Undergraduate Mathematics Series | title = Fundamental Mathematical Analysis | year = 2020| s2cid = 226465639 }}</ref>}}
More carefully bounding the sum both above and below by an integral, using the [[trapezoid rule]], shows that this estimate needs a correction factor proportional {{nowrap|to <math>\sqrt n</math>.}} The constant of proportionality for this correction can be found from the [[Wallis product]], which expresses <math>\pi</math> as a limiting ratio of factorials and powers of two. The result of these corrections is [[Stirling's approximation]]:<ref>{{cite book | last = Palmer | first = Edgar M. | contribution = Appendix II: Stirling's formula | isbn = 0-471-81577-2 | location = Chichester | mr = 795795 | pages = 127–128 | publisher = John Wiley & Sons | series = Wiley-Interscience Series in Discrete Mathematics | title = Graphical Evolution: An introduction to the theory of random graphs | year = 1985}}</ref>
<math display="block">n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\,.</math>
Here, the <math>\sim</math> symbol means that, as <math>n</math> goes to infinity, the ratio between the left and right sides approaches one in the [[Limit (mathematics)|limit]].
Stirling's formula provides the first term in an [[asymptotic series]] that becomes even more accurate when taken to greater numbers of terms:<ref name="asymptotic">{{cite journal | last1 = Chen | first1 = Chao-Ping | last2 = Lin | first2 = Long | doi = 10.1016/j.aml.2012.06.025 | issue = 12 | journal = Applied Mathematics Letters | mr = 2967837 | pages = 2322–2326 | title = Remarks on asymptotic expansions for the gamma function | volume = 25 | year = 2012| doi-access = free }}</ref>
<math display="block">
n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1 +\frac{1}{12n}+\frac{1}{288n^2} - \frac{139}{51840n^3} -\frac{571}{2488320n^4}+ \cdots \right).</math>
An alternative version uses only odd exponents in the correction terms:<ref name=asymptotic/>
<math display=block>
n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \exp\left(\frac{1}{12n} - \frac{1}{360n^3} + \frac{1}{1260n^5} -\frac{1}{1680n^7}+ \cdots \right).</math>
Many other variations of these formulas have also been developed, by [[Srinivasa Ramanujan]], [[Bill Gosper]], and others.<ref name=asymptotic/>

The [[binary logarithm]] of the factorial, used to analyze [[comparison sort]]ing, can be very accurately estimated using Stirling's approximation. In the formula below, the <math>O(1)</math> term invokes [[big O notation]].<ref name=knuth-sorting>{{cite book|title=The Art of Computer Programming, Volume 3: Sorting and Searching|first=Donald E.|last=Knuth|author-link=Donald Knuth|edition=2nd|publisher=Addison-Wesley|year=1998|isbn=978-0-321-63578-5|page=182|url=https://books.google.com/books?id=cYULBAAAQBAJ&pg=PA182}}</ref>
<math display=block>\log_2 n! = n\log_2 n-(\log_2 e)n + \frac12\log_2 n + O(1).</math>

===Divisibility and digits===
{{main|Legendre's formula}}
The product formula for the factorial implies that <math>n!</math> is [[divisible]] by all [[prime number]]s that are at {{nowrap|most <math>n</math>,}} and by no larger prime numbers.<ref name=beiler>{{cite book|title=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|series=Dover Recreational Math Series|first=Albert H.|last=Beiler|publisher=Courier Corporation|year=1966|edition=2nd|isbn=978-0-486-21096-4|page=49|url=https://books.google.com/books?id=NbbbL9gMJ88C&pg=PA49}}</ref> More precise information about its divisibility is given by [[Legendre's formula]], which gives the exponent of each prime <math>p</math> in the prime factorization of <math>n!</math> as<ref>{{harvnb|Chvátal|2021}}. "1.4: Legendre's formula". pp. 6–7.</ref><ref name=padic>{{cite book | last = Robert | first = Alain M. | author-link = Alain M. Robert | contribution = 3.1: The {{nowrap|<math>p</math>-adic}} valuation of a factorial | doi = 10.1007/978-1-4757-3254-2 | isbn = 0-387-98669-3 | mr = 1760253 | pages = 241–242 | publisher = Springer-Verlag | location = New York | series = [[Graduate Texts in Mathematics]] | title = A Course in {{nowrap|<math>p</math>-adic}} Analysis | volume = 198 | year = 2000}}</ref>
<math display=block>\sum_{i=1}^\infty \left \lfloor \frac n {p^i} \right \rfloor=\frac{n - s_p(n)}{p - 1}.</math>
Here <math>s_p(n)</math> denotes the sum of the {{nowrap|[[radix|base]]-<math>p</math>}} digits {{nowrap|of <math>n</math>,}} and the exponent given by this formula can also be interpreted in advanced mathematics as the [[p-adic valuation|{{mvar|p}}-adic valuation]] of the factorial.<ref name=padic/> Applying Legendre's formula to the product formula for [[binomial coefficient]]s produces [[Kummer's theorem]], a similar result on the exponent of each prime in the factorization of a binomial coefficient.<ref>{{cite book | last1 = Peitgen | author1-link=Heinz-Otto Peitgen | first1 = Heinz-Otto | last2 = Jürgens | first2 = Hartmut | author2-link = Hartmut Jürgens | last3 = Saupe | first3 = Dietmar | author3-link = Dietmar Saupe | contribution = Kummer's result and Legendre's identity | doi = 10.1007/b97624 | location = New York | pages = 399–400 | publisher = Springer | title = Chaos and Fractals: New Frontiers of Science | year = 2004| isbn=978-1-4684-9396-2 }}</ref> Grouping the prime factors of the factorial into [[prime power]]s in different ways produces the [[multiplicative partitions of factorials]].<ref>{{Cite journal|last1=Alladi|first1=Krishnaswami|last2=Grinstead|first2=Charles|authorlink1=Krishnaswami Alladi |title=On the decomposition of n! into prime powers|journal=[[Journal of Number Theory]]|year=1977 |language=en|volume=9|issue=4|pages=452–458|doi=10.1016/0022-314x(77)90006-3|doi-access=free}}</ref>

The special case of Legendre's formula for <math>p=5</math> gives the number of [[trailing zero#Factorial|trailing zeros]] in the decimal representation of the factorials.<ref name=koshy/> According to this formula, the number of zeros can be obtained by subtracting the base-5 digits of <math>n</math> from <math>n</math>, and dividing the result by four.<ref>{{cite OEIS|A027868|Number of trailing zeros in n!; highest power of 5 dividing n!}}</ref> Legendre's formula implies that the exponent of the prime <math>p=2</math> is always larger than the exponent for {{nowrap|<math>p=5</math>,}} so each factor of five can be paired with a factor of two to produce one of these trailing zeros.<ref name=koshy>{{cite book|title=Elementary Number Theory with Applications|first=Thomas|last=Koshy|edition=2nd|publisher=Elsevier|year=2007|isbn=978-0-08-054709-1|contribution=Example 3.12|page=178|contribution-url=https://books.google.com/books?id=d5Z5I3gnFh0C&pg=PA178}}</ref> The leading digits of the factorials are distributed according to [[Benford's law]].<ref>{{cite journal | last = Diaconis | first = Persi | author-link = Persi Diaconis | doi = 10.1214/aop/1176995891 | issue = 1 | journal = [[Annals of Probability]] | mr = 422186 | pages = 72–81 | title = The distribution of leading digits and uniform distribution mod 1 | volume = 5 | year = 1977| doi-access = free }}</ref> Every sequence of digits, in any base, is the sequence of initial digits of some factorial number in that base.<ref>{{cite journal|last=Bird|first=R. S.|author-link=Richard Bird (computer scientist)|doi=10.1080/00029890.1972.11993051|journal=[[The American Mathematical Monthly]]|jstor=2978087|mr=302553|pages=367–370|title=Integers with given initial digits|volume=79|year=1972|issue=4}}</ref>

Another result on divisibility of factorials, [[Wilson's theorem]], states that <math>(n-1)!+1</math> is divisible by <math>n</math> if and only if <math>n</math> is a [[prime number]].<ref name=beiler/> For any given {{nowrap|integer <math>x</math>,}} the [[Kempner function]] of <math>x</math> is given by the smallest <math>n</math> for which <math>x</math> divides {{nowrap|<math>n!</math>.<ref>{{cite journal | jstor = 2972639 | first = A. J. | last = Kempner | title = Miscellanea | journal = [[The American Mathematical Monthly]] | volume = 25 | pages = 201–210 | year = 1918 | doi = 10.2307/2972639 | issue = 5}}</ref>}} For almost all numbers (all but a subset of exceptions with [[asymptotic density]] zero), it coincides with the largest prime factor {{nowrap|of <math>x</math>.<ref>{{cite journal|title=The smallest factorial that is a multiple of {{mvar|n}} (solution to problem 6674)|journal=[[The American Mathematical Monthly]]|volume=101|year=1994|page=179|url=http://www-fourier.ujf-grenoble.fr/~marin/une_autre_crypto/articles_et_extraits_livres/irationalite/Erdos_P._Kastanas_I.The_smallest_factorial...-.pdf|first1=Paul|last1=Erdős|author1-link=Paul Erdős|first2=Ilias|last2=Kastanas|doi=10.2307/2324376|jstor=2324376}}.</ref>}}

The product of two factorials, {{nowrap|<math>m!\cdot n!</math>,}} always evenly divides {{nowrap|<math>(m+n)!</math>.<ref name=bhargava/>}} There are infinitely many factorials that equal the product of other factorials: if <math>n</math> is itself any product of factorials, then <math>n!</math> equals that same product multiplied by one more factorial, {{nowrap|<math>(n-1)!</math>.}} The only known examples of factorials that are products of other factorials but are not of this "trivial" form are {{nowrap|<math>9!=7!\cdot 3!\cdot 3!\cdot 2!</math>,}} {{nowrap|<math>10!=7!\cdot 6!=7!\cdot 5!\cdot 3!</math>,}} and {{nowrap|<math>16!=14!\cdot 5!\cdot 2!</math>.<ref>{{harvnb|Guy|2004}}. "B23: Equal products of factorials". p. 123.</ref>}} It would follow from the [[abc conjecture|{{mvar|abc}} conjecture]] that there are only finitely many nontrivial examples.<ref>{{cite journal | last = Luca | first = Florian | author-link = Florian Luca | doi = 10.1017/S0305004107000308 | issue = 3 | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]] | mr = 2373957 | pages = 533–542 | title = On factorials which are products of factorials | volume = 143 | year = 2007| bibcode = 2007MPCPS.143..533L | s2cid = 120875316 }}</ref>

The [[greatest common divisor]] of the values of a [[Primitive part and content|primitive polynomial]] of degree <math>d</math> over the integers evenly divides {{nowrap|<math>d!</math>.<ref name=bhargava>{{cite journal | last = Bhargava | first = Manjul | author-link = Manjul Bhargava | url = https://scholar.archive.org/work/dk6exbnlyrhp3bai62vnokou2q | title = The factorial function and generalizations | journal = [[The American Mathematical Monthly]] | volume = 107 | year = 2000 | pages = 783–799 | doi = 10.2307/2695734 | issue = 9 | jstor = 2695734 | citeseerx = 10.1.1.585.2265 }}</ref>}}

===Continuous interpolation and non-integer generalization===
[[File:Generalized factorial function more infos.svg|thumb|upright=1.6|The gamma function (shifted one unit left to match the factorials) continuously interpolates the factorial to non-integer values]]
[[File:Gamma abs 3D.png|thumb|Absolute values of the complex gamma function, showing poles at non-positive integers]]
{{Main|Gamma function}}
There are infinitely many ways to extend the factorials to a [[continuous function]].<ref name=davis/> The most widely used of these<ref name=borwein-corless/> uses the [[gamma function]], which can be defined for positive real numbers as the [[integral]]
<math display=block> \Gamma(z) = \int_0^\infty x^{z-1} e^{-x}\,dx.</math>
The resulting function is related to the factorial of a non-negative integer <math>n</math> by the equation
<math display=block> n!=\Gamma(n+1),</math>
which can be used as a definition of the factorial for non-integer arguments.
At all values <math>x</math> for which both <math>\Gamma(x)</math> and <math>\Gamma(x-1)</math> are defined, the gamma function obeys the [[functional equation]]
<math display=block> \Gamma(n)=(n-1)\Gamma(n-1),</math>
generalizing the [[recurrence relation]] for the factorials.<ref name=davis>{{cite journal | last = Davis | first = Philip J. | author-link = Philip J. Davis | doi = 10.1080/00029890.1959.11989422 | journal = [[The American Mathematical Monthly]] | jstor = 2309786 | mr = 106810 | pages = 849–869 | title = Leonhard Euler's integral: A historical profile of the gamma function | url = https://www.maa.org/programs/maa-awards/writing-awards/leonhard-eulers-integral-an-historical-profile-of-the-gamma-function | volume = 66 | year = 1959 | issue = 10 | access-date = 2021-12-20  | archive-date = 2023-01-01  | archive-url = https://web.archive.org/web/20230101190952/https://www.maa.org/programs/maa-awards/writing-awards/leonhard-eulers-integral-an-historical-profile-of-the-gamma-function | url-status = dead }}</ref>

The same integral converges more generally for any [[complex number]] <math>z</math> whose real part is positive. It can be extended to the non-integer points in the rest of the [[complex plane]] by solving for Euler's [[reflection formula]]
<math display=block>\Gamma(z)\Gamma(1-z)=\frac{\pi}{\sin\pi z}.</math>
However, this formula cannot be used at integers because, for them, the <math>\sin\pi z</math> term would produce a [[division by zero]]. The result of this extension process is an [[analytic function]], the [[analytic continuation]] of the integral formula for the gamma function. It has a nonzero value at all complex numbers, except for the non-positive integers where it has [[Zeros and poles|simple poles]]. Correspondingly, this provides a definition for the factorial at all complex numbers other than the negative integers.<ref name=borwein-corless>{{cite journal | last1 = Borwein | first1 = Jonathan M. | author1-link = Jonathan Borwein | last2 = Corless | first2 = Robert M. | doi = 10.1080/00029890.2018.1420983 | issue = 5 | journal = [[The American Mathematical Monthly]] | mr = 3785875 | pages = 400–424 | title = Gamma and factorial in the ''Monthly'' | volume = 125 | year = 2018| arxiv = 1703.05349 | s2cid = 119324101 }}</ref>
One property of the gamma function, distinguishing it from other continuous interpolations of the factorials, is given by the [[Bohr–Mollerup theorem]], which states that the gamma function (offset by one) is the only [[log-convex]] function on the positive real numbers that interpolates the factorials and obeys the same functional equation. A related uniqueness theorem of [[Helmut Wielandt]] states that the complex gamma function and its scalar multiples are the only [[holomorphic function]]s on the positive complex half-plane that obey the functional equation and remain bounded for complex numbers with real part between 1 and 2.<ref>{{cite journal | last = Remmert | first = Reinhold | author-link = Reinhold Remmert | doi = 10.1080/00029890.1996.12004726 | issue = 3 | journal = [[The American Mathematical Monthly]] | jstor = 2975370 | mr = 1376175 | pages = 214–220 | title = Wielandt's theorem about the {{nowrap|<math>\Gamma</math>-function}} | volume = 103 | year = 1996}}</ref>

Other complex functions that interpolate the factorial values include [[Hadamard's gamma function]], which is an [[entire function]] over all the complex numbers, including the non-positive integers.<ref>{{cite book|first=J.|last=Hadamard|author-link=Jacques Hadamard|chapter=Sur l'expression du produit {{math|1·2·3· · · · ·(''n''−1)}} par une fonction entière|title=Œuvres de Jacques Hadamard|publisher=Centre National de la Recherche Scientifiques|location=Paris|date=1968|chapter-url=http://www.luschny.de/math/factorial/hadamard/HadamardFactorial.pdf|orig-date=1894|language=fr}}
</ref><ref>{{cite journal | last = Alzer | first = Horst | doi = 10.1007/s12188-008-0009-5 | issue = 1 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg | mr = 2541340 | pages = 11–23 | title = A superadditive property of Hadamard's gamma function | volume = 79 | year = 2009| s2cid = 123691692 }}</ref> In the [[p-adic number|{{mvar|p}}-adic number]]s, it is not possible to continuously interpolate the factorial function directly, because the factorials of large integers (a dense subset of the {{mvar|p}}-adics) converge to zero according to Legendre's formula, forcing any continuous function that is close to their values to be zero everywhere. Instead, the [[p-adic gamma function|{{mvar|p}}-adic gamma function]] provides a continuous interpolation of a modified form of the factorial, omitting the factors in the factorial that are divisible by {{mvar|p}}.<ref>{{harvnb|Robert|2000}}. "7.1: The gamma function {{nowrap|<math>\Gamma_p</math>".}} pp. 366–385.</ref>

The [[digamma function]] is the [[logarithmic derivative]] of the gamma function. Just as the gamma function provides a continuous interpolation of the factorials, offset by one, the digamma function provides a continuous interpolation of the [[harmonic number]]s, offset by the [[Euler–Mascheroni constant]].<ref>{{cite journal | last = Ross | first = Bertram | doi = 10.1080/0025570X.1978.11976704 | issue = 3 | journal = [[Mathematics Magazine]] | jstor = 2689999 | mr = 1572267 | pages = 176–179 | title = The psi function | volume = 51 | year = 1978}}</ref>

===Computation===
[[File:Vintage Texas Instruments Model SR-50A Handheld LED Electronic Calculator, Made in the USA, Price Was $109.50 in 1975 (8715012843).jpg|thumb|[[TI SR-50|TI SR-50A]], a 1975 calculator with a factorial key (third row, center right)]]
The factorial function is a common feature in [[scientific calculator]]s.<ref>{{cite book|title=Understandable Statistics: Concepts and Methods|first1=Charles Henry|last1=Brase|first2=Corrinne Pellillo|last2=Brase|edition=11th|publisher=Cengage Learning|year=2014|isbn=978-1-305-14290-9|page=182|url=https://books.google.com/books?id=a8OiAgAAQBAJ&pg=PA182}}</ref> It is also included in scientific programming libraries such as the [[Python (programming language)|Python]] mathematical functions module<ref>{{cite web|url=https://docs.python.org/3/library/math.html|title=math — Mathematical functions|work=Python 3 Documentation: The Python Standard Library|access-date=2021-12-21}}</ref> and the [[Boost (C++ libraries)|Boost C++ library]].<ref>{{cite web|url=https://www.boost.org/doc/libs/1_78_0/libs/math/doc/html/math_toolkit/factorials/sf_factorial.html| title=Factorial|work=Boost 1.78.0 Documentation: Math Special Functions|access-date=2021-12-21}}</ref> If efficiency is not a concern, computing factorials is trivial: just successively multiply a variable initialized {{nowrap|to <math>1</math>}} by the integers up {{nowrap|to <math>n</math>.}} The simplicity of this computation makes it a common example in the use of different computer programming styles and methods.<ref>{{cite book|title=Drawing Programs: The Theory and Practice of Schematic Functional Programming|first1=Tom|last1=Addis|first2=Jan|last2=Addis|publisher=Springer| year=2009| isbn=978-1-84882-618-2| pages=149–150|url=https://books.google.com/books?id=cWM7ZBfEl_0C&pg=PA149}}</ref>

The computation of <math>n!</math> can be expressed in [[pseudocode]] using [[iteration]]<ref>{{cite book|title=MATLAB Programming for Engineers|first=Stephen J.|last=Chapman|edition=6th|publisher=Cengage Learning|year=2019| isbn=978-0-357-03052-3| page=215|contribution=Example 5.2: The factorial function|contribution-url=https://books.google.com/books?id=jVEzEAAAQBAJ&pg=PA215}}</ref> as
 define factorial(''n''):
   ''f'' := 1
   for ''i'' := 1, 2, 3, ..., ''n'':
     ''f'' := ''f'' * ''i''
   return ''f''
or using [[Recursion (computer science)|recursion]]<ref>{{cite book|title=The Computing Universe: A Journey through a Revolution|first1=Tony|last1=Hey|first2=Gyuri|last2=Pápay|publisher=Cambridge University Press|year=2014|isbn=9781316123225|page=64|url=https://books.google.com/books?id=q4FIBQAAQBAJ&pg=PA64}}</ref> based on its recurrence relation as
 define factorial(''n''):
   if (''n'' = 0) return 1
   return ''n'' * factorial(''n'' − 1)
Other methods suitable for its computation include [[memoization]],<ref>{{cite book|title=Hands-On Functional Programming with C++: An effective guide to writing accelerated functional code using C++17 and C++20| first=Alexandru|last=Bolboaca | publisher=Packt Publishing|year=2019|isbn=978-1-78980-921-3|page=188|url=https://books.google.com/books?id=GwSgDwAAQBAJ&pg=PA188}}</ref> [[dynamic programming]],<ref>{{cite book|title=Mastering Mathematica: Programming Methods and Applications| first=John W.|last=Gray|publisher=Academic Press|year=2014|isbn=978-1-4832-1403-0|pages=233–234| url=https://books.google.com/books?id=a4riBQAAQBAJ&pg=PA233}}</ref> and [[functional programming]].<ref>{{cite book|title=Scala From a Functional Programming Perspective: An Introduction to the Programming Language|volume=9980|series=Lecture Notes in Computer Science| first=Vicenç| last=Torra| publisher=Springer|year=2016|isbn=978-3-319-46481-7|page=96|url=https://books.google.com/books?id=eMwcDQAAQBAJ&pg=PA96}}</ref> The [[computational complexity]] of these algorithms may be analyzed using the unit-cost [[random-access machine]] model of computation, in which each arithmetic operation takes constant time and each number uses a constant amount of storage space. In this model, these methods can compute <math>n!</math> in time {{nowrap|<math>O(n)</math>,}} and the iterative version uses space {{nowrap|<math>O(1)</math>.}} Unless optimized for [[tail recursion]], the recursive version takes linear space to store its [[call stack]].<ref>{{cite book|title=Functional Programming and Its Applications: An Advanced Course| publisher=Cambridge University Press|series=CREST Advanced Courses|contribution=LISP, programming, and implementation| first=Gerald Jay|last=Sussman|author-link=Gerald Jay Sussman|year=1982|pages=29–72|isbn=978-0-521-24503-6}} See in particular [https://books.google.com/books?id=O_M8AAAAIAAJ&pg=PA34 p. 34].</ref> However, this model of computation is only suitable when <math>n</math> is small enough to allow <math>n!</math> to fit into a [[machine word]].<ref>{{cite journal | last = Chaudhuri | first = Ranjan | date = June 2003 | doi = 10.1145/782941.782977 | issue = 2 | journal = ACM SIGCSE Bulletin | pages = 43–44 | publisher = Association for Computing Machinery | title = Do the arithmetic operations really execute in constant time? | volume = 35| s2cid = 13629142 }}</ref> The values 12! and 20! are the largest factorials that can be stored in, respectively, the [[32-bit computing|32-bit]]<ref name=fateman/> and [[64-bit computing|64-bit]] [[Integer (computer science)|integers]].<ref name=sigplan>{{cite journal | last1 = Winkler | first1 = Jürgen F. H. | last2 = Kauer | first2 = Stefan | date = March 1997 | doi = 10.1145/251634.251638 | issue = 3 | journal = ACM SIGPLAN Notices | pages = 38–41 | publisher = Association for Computing Machinery | title = Proving assertions is also useful | volume = 32| s2cid = 17347501 | doi-access = free }}</ref> [[Floating point]] can represent larger factorials, but approximately rather than exactly, and will still overflow for factorials larger than {{nowrap|<math>170!</math>.<ref name=fateman>{{cite web| url=http://people.eecs.berkeley.edu/~fateman/papers/factorial.pdf|title=Comments on Factorial Programs|date=April 11, 2006| publisher=University of California, Berkeley|first=Richard J.|last=Fateman|author-link=Richard Fateman}}</ref>}}

The exact computation of larger factorials involves [[arbitrary-precision arithmetic]], because of [[Factorial#Growth_and_approximation|fast growth]] and [[integer overflow]].  Time of computation can be analyzed as a function of the number of digits or bits in the result.<ref name=sigplan/> By Stirling's formula, <math>n!</math> has <math>b = O(n\log n)</math> bits.<ref name=borwein/> The [[Schönhage–Strassen algorithm]] can produce a {{nowrap|<math>b</math>-bit}} product in time {{nowrap|<math>O(b\log b\log\log b)</math>,}} and faster [[multiplication algorithm]]s taking time <math>O(b\log b)</math> are known.<ref>{{cite journal | last1 = Harvey | first1 = David | last2 = van der Hoeven | first2 = Joris | author2-link = Joris van der Hoeven | doi = 10.4007/annals.2021.193.2.4 | issue = 2 | journal = [[Annals of Mathematics]] | mr = 4224716 | pages = 563–617 | series = Second Series | title = Integer multiplication in time <math>O(n \log n)</math>| volume = 193 | year = 2021| s2cid = 109934776 | url = https://hal.archives-ouvertes.fr/hal-02070778/file/nlogn.pdf }}</ref> However, computing the factorial involves repeated products, rather than a single multiplication, so these time bounds do not apply directly.  In this setting, computing <math>n!</math> by multiplying the numbers from 1 {{nowrap|to <math>n</math>}} in sequence is inefficient, because it involves <math>n</math> multiplications, a constant fraction of which take time <math>O(n\log^2 n)</math> each, giving total time {{nowrap|<math>O(n^2\log^2 n)</math>.}} A better approach is to perform the multiplications as a [[divide-and-conquer algorithm]] that multiplies a sequence of <math>i</math> numbers by splitting it into two subsequences of <math>i/2</math> numbers, multiplies each subsequence, and combines the results with one last multiplication. This approach to the factorial takes total time {{nowrap|<math>O(n\log^3 n)</math>:}} one logarithm comes from the number of bits in the factorial, a second comes from the multiplication algorithm, and a third comes from the divide and conquer.<ref>{{cite book|last=Arndt|first=Jörg| title=Matters Computational: Ideas, Algorithms, Source Code|publisher=Springer|year=2011|url=http://jjj.de/fxt/fxtbook.pdf| contribution=34.1.1.1: Computation of the factorial|pages=651–652}} See also "34.1.5: Performance", pp. 655–656.</ref>

Even better efficiency is obtained by computing {{math|''n''!}} from its prime factorization, based on the principle that [[exponentiation by squaring]] is faster than expanding an exponent into a product.<ref name=borwein>{{cite journal | last = Borwein | first = Peter B. | author-link = Peter Borwein | doi = 10.1016/0196-6774(85)90006-9 | issue = 3 | journal = [[Journal of Algorithms]] | mr = 800727 | pages = 376–380 | title = On the complexity of calculating factorials | volume = 6 | year = 1985}}</ref><ref name=schonhage>{{cite book|first=Arnold|last=Schönhage|year=1994|title=Fast algorithms: a multitape Turing machine implementation|publisher=B.I. Wissenschaftsverlag|page=226}}</ref> An algorithm for this by [[Arnold Schönhage]] begins by finding the list of the primes up {{nowrap|to <math>n</math>,}} for instance using the [[sieve of Eratosthenes]], and uses Legendre's formula to compute the exponent for each prime. Then it computes the product of the prime powers with these exponents, using a recursive algorithm, as follows:
* Use divide and conquer to compute the product of the primes whose exponents are odd
* Divide all of the exponents by two (rounding down to an integer), recursively compute the product of the prime powers with these smaller exponents, and square the result
* Multiply together the results of the two previous steps
The product of all primes up to <math>n</math> is an <math>O(n)</math>-bit number, by the [[prime number theorem]], so the time for the first step is <math>O(n\log^2 n)</math>, with one logarithm coming from the divide and conquer and another coming from the multiplication algorithm. In the recursive calls to the algorithm, the prime number theorem can again be invoked to prove that the numbers of bits in the corresponding products decrease by a constant factor at each level of recursion, so the total time for these steps at all levels of recursion adds in a [[geometric series]] {{nowrap|to <math>O(n\log^2 n)</math>.}} The time for the squaring in the second step and the multiplication in the third step are again {{nowrap|<math>O(n\log^2 n)</math>,}} because each is a single multiplication of a number with <math>O(n\log n)</math> bits. Again, at each level of recursion the numbers involved have a constant fraction as many bits (because otherwise repeatedly squaring them would produce too large a final result) so again the amounts of time for these steps in the recursive calls add in a geometric series {{nowrap|to <math>O(n\log^2 n)</math>.}} Consequentially, the whole algorithm takes {{nowrap|time <math>O(n\log^2 n)</math>,}} proportional to a single multiplication with the same number of bits in its result.<ref name=schonhage/>