001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.numbers.combinatorics;
019
020/**
021 * <a href="http://mathworld.wolfram.com/Factorial.html">Factorial of a number</a>.
022 */
023public final class Factorial {
024
025    /** All long-representable factorials. */
026    static final long[] FACTORIALS = {
027                       1L,                  1L,                   2L,
028                       6L,                 24L,                 120L,
029                     720L,               5040L,               40320L,
030                  362880L,            3628800L,            39916800L,
031               479001600L,         6227020800L,         87178291200L,
032           1307674368000L,     20922789888000L,     355687428096000L,
033        6402373705728000L, 121645100408832000L, 2432902008176640000L
034    };
035
036    /** All factorials that can be represented as a double (values up to 170!). */
037    private static final double[] DOUBLE_FACTORIALS = {
038        1,
039        1,
040        2,
041        6,
042        24,
043        120,
044        720,
045        5040,
046        40320,
047        362880,
048        3628800,
049        3.99168E7,
050        4.790016E8,
051        6.2270208E9,
052        8.71782912E10,
053        1.307674368E12,
054        2.0922789888E13,
055        3.55687428096E14,
056        6.402373705728E15,
057        1.21645100408832E17,
058        2.43290200817664E18,
059        5.109094217170944E19,
060        1.1240007277776077E21,
061        2.585201673888498E22,
062        6.204484017332394E23,
063        1.5511210043330986E25,
064        4.0329146112660565E26,
065        1.0888869450418352E28,
066        3.0488834461171387E29,
067        8.841761993739702E30,
068        2.6525285981219107E32,
069        8.222838654177922E33,
070        2.631308369336935E35,
071        8.683317618811886E36,
072        2.9523279903960416E38,
073        1.0333147966386145E40,
074        3.7199332678990125E41,
075        1.3763753091226346E43,
076        5.230226174666011E44,
077        2.0397882081197444E46,
078        8.159152832478977E47,
079        3.345252661316381E49,
080        1.40500611775288E51,
081        6.041526306337383E52,
082        2.658271574788449E54,
083        1.1962222086548019E56,
084        5.502622159812089E57,
085        2.5862324151116818E59,
086        1.2413915592536073E61,
087        6.082818640342675E62,
088        3.0414093201713376E64,
089        1.5511187532873822E66,
090        8.065817517094388E67,
091        4.2748832840600255E69,
092        2.308436973392414E71,
093        1.2696403353658276E73,
094        7.109985878048635E74,
095        4.0526919504877214E76,
096        2.3505613312828785E78,
097        1.3868311854568984E80,
098        8.32098711274139E81,
099        5.075802138772248E83,
100        3.146997326038794E85,
101        1.98260831540444E87,
102        1.2688693218588417E89,
103        8.247650592082472E90,
104        5.443449390774431E92,
105        3.647111091818868E94,
106        2.4800355424368305E96,
107        1.711224524281413E98,
108        1.1978571669969892E100,
109        8.504785885678623E101,
110        6.1234458376886085E103,
111        4.4701154615126844E105,
112        3.307885441519386E107,
113        2.48091408113954E109,
114        1.8854947016660504E111,
115        1.4518309202828587E113,
116        1.1324281178206297E115,
117        8.946182130782976E116,
118        7.156945704626381E118,
119        5.797126020747368E120,
120        4.753643337012842E122,
121        3.945523969720659E124,
122        3.314240134565353E126,
123        2.81710411438055E128,
124        2.4227095383672734E130,
125        2.107757298379528E132,
126        1.8548264225739844E134,
127        1.650795516090846E136,
128        1.4857159644817615E138,
129        1.352001527678403E140,
130        1.2438414054641308E142,
131        1.1567725070816416E144,
132        1.087366156656743E146,
133        1.032997848823906E148,
134        9.916779348709496E149,
135        9.619275968248212E151,
136        9.426890448883248E153,
137        9.332621544394415E155,
138        9.332621544394415E157,
139        9.42594775983836E159,
140        9.614466715035127E161,
141        9.90290071648618E163,
142        1.0299016745145628E166,
143        1.081396758240291E168,
144        1.1462805637347084E170,
145        1.226520203196138E172,
146        1.324641819451829E174,
147        1.4438595832024937E176,
148        1.588245541522743E178,
149        1.7629525510902446E180,
150        1.974506857221074E182,
151        2.2311927486598138E184,
152        2.5435597334721877E186,
153        2.925093693493016E188,
154        3.393108684451898E190,
155        3.969937160808721E192,
156        4.684525849754291E194,
157        5.574585761207606E196,
158        6.689502913449127E198,
159        8.094298525273444E200,
160        9.875044200833601E202,
161        1.214630436702533E205,
162        1.506141741511141E207,
163        1.882677176888926E209,
164        2.372173242880047E211,
165        3.0126600184576594E213,
166        3.856204823625804E215,
167        4.974504222477287E217,
168        6.466855489220474E219,
169        8.47158069087882E221,
170        1.1182486511960043E224,
171        1.4872707060906857E226,
172        1.9929427461615188E228,
173        2.6904727073180504E230,
174        3.659042881952549E232,
175        5.012888748274992E234,
176        6.917786472619489E236,
177        9.615723196941089E238,
178        1.3462012475717526E241,
179        1.898143759076171E243,
180        2.695364137888163E245,
181        3.854370717180073E247,
182        5.5502938327393044E249,
183        8.047926057471992E251,
184        1.1749972043909107E254,
185        1.727245890454639E256,
186        2.5563239178728654E258,
187        3.80892263763057E260,
188        5.713383956445855E262,
189        8.62720977423324E264,
190        1.3113358856834524E267,
191        2.0063439050956823E269,
192        3.0897696138473508E271,
193        4.789142901463394E273,
194        7.471062926282894E275,
195        1.1729568794264145E278,
196        1.853271869493735E280,
197        2.9467022724950384E282,
198        4.7147236359920616E284,
199        7.590705053947219E286,
200        1.2296942187394494E289,
201        2.0044015765453026E291,
202        3.287218585534296E293,
203        5.423910666131589E295,
204        9.003691705778438E297,
205        1.503616514864999E300,
206        2.5260757449731984E302,
207        4.269068009004705E304,
208        7.257415615307999E306
209    };
210
211    /** Private constructor. */
212    private Factorial() {
213        // intentionally empty.
214    }
215
216    /**
217     * Computes the factorial of {@code n}.
218     *
219     * @param n Argument.
220     * @return {@code n!}
221     * @throws IllegalArgumentException if {@code n < 0}.
222     * @throws IllegalArgumentException if {@code n > 20} (the factorial
223     * value is too large to fit in a {@code long}).
224     */
225    public static long value(int n) {
226        if (n < 0 ||
227            n > 20) {
228            throw new CombinatoricsException(CombinatoricsException.OUT_OF_RANGE,
229                                             n, 0, 20);
230        }
231
232        return FACTORIALS[n];
233    }
234
235    /**
236     * Computes the factorial of {@code n}.
237     *
238     * <p>The result should be small enough to fit into a {@code double}: The
239     * largest {@code n} for which {@code n!} does not exceed
240     * {@code Double.MAX_VALUE} is 170. {@code Double.POSITIVE_INFINITY} is
241     * returned for {@code n > 170}.
242     *
243     * @param n Argument.
244     * @return {@code n!}
245     * @throws IllegalArgumentException if {@code n < 0}.
246     * @since 1.1
247     */
248    public static double doubleValue(int n) {
249        if (n < 0) {
250            throw new CombinatoricsException(CombinatoricsException.NEGATIVE, n);
251        }
252        if (n < DOUBLE_FACTORIALS.length) {
253            return DOUBLE_FACTORIALS[n];
254        }
255        return Double.POSITIVE_INFINITY;
256    }
257
258    /**
259     * Return the factorial of {@code n}.
260     *
261     * <p>Note: This is an internal method that exposes the tabulated factorials that can
262     * be represented as a double. No checks are performed on the argument.
263     *
264     * @param n Argument (must be in [0, 170])
265     * @return n!
266     */
267    static double uncheckedFactorial(int n) {
268        return DOUBLE_FACTORIALS[n];
269    }
270}