Editing Factorial (section)

===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/>