1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.numbers.combinatorics;
19
20 import org.apache.commons.numbers.gamma.LogGamma;
21
22 /**
23 * Class for computing the natural logarithm of the factorial of a number.
24 * It allows to allocate a cache of precomputed values.
25 * In case of cache miss, computation is performed by a call to
26 * {@link LogGamma#value(double)}.
27 */
28 public final class LogFactorial {
29 /**
30 * Size of precomputed factorials.
31 * @see Factorial
32 */
33 private static final int FACTORIALS_CACHE_SIZE = 21;
34 /**
35 * Precomputed values of the function: {@code logFactorials[i] = Math.log(i!)}.
36 */
37 private final double[] logFactorials;
38
39 /**
40 * Creates an instance, reusing the already computed values if available.
41 *
42 * @param numValues Number of values of the function to compute.
43 * @param cache Cached values.
44 * @throw IllegalArgumentException if {@code n < 0}.
45 */
46 private LogFactorial(int numValues,
47 double[] cache) {
48 if (numValues < 0) {
49 throw new CombinatoricsException(CombinatoricsException.NEGATIVE, numValues);
50 }
51
52 logFactorials = new double[numValues];
53
54 final int beginCopy = 2;
55 int endCopy;
56 if (cache == null || cache.length <= beginCopy) {
57 endCopy = beginCopy;
58 } else {
59 endCopy = Math.min(cache.length, numValues);
60 }
61
62
63 // Copy available values.
64 if (endCopy - beginCopy > 0) {
65 System.arraycopy(cache, beginCopy, logFactorials, beginCopy, endCopy - beginCopy);
66 }
67
68 // Precompute.
69 for (int i = endCopy; i < numValues; i++) {
70 logFactorials[i] = logFactorials[i - 1] + Math.log(i);
71 }
72 }
73
74 /**
75 * Creates an instance with no precomputed values.
76 * @return instance with no precomputed values
77 */
78 public static LogFactorial create() {
79 return new LogFactorial(0, null);
80 }
81
82 /**
83 * Creates an instance with the specified cache size.
84 *
85 * @param cacheSize Number of precomputed values of the function.
86 * @return a new instance where {@code cacheSize} values have been
87 * precomputed.
88 * @throws IllegalArgumentException if {@code cacheSize < 0}.
89 */
90 public LogFactorial withCache(final int cacheSize) {
91 return new LogFactorial(cacheSize, logFactorials);
92 }
93
94 /**
95 * Computes \( log_e(n!) \).
96 *
97 * @param n Argument.
98 * @return {@code log(n!)}.
99 * @throws IllegalArgumentException if {@code n < 0}.
100 */
101 public double value(int n) {
102 if (n < 0) {
103 throw new CombinatoricsException(CombinatoricsException.NEGATIVE, n);
104 }
105
106 // Use cache of precomputed values.
107 if (n < logFactorials.length) {
108 return logFactorials[n];
109 }
110
111 // Use cache of precomputed factorial values.
112 if (n < FACTORIALS_CACHE_SIZE) {
113 return Math.log(Factorial.value(n));
114 }
115
116 // Delegate.
117 return LogGamma.value(n + 1.0);
118 }
119 }