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
020import org.apache.commons.numbers.gamma.LogGamma;
021
022/**
023 * Class for computing the natural logarithm of the factorial of a number.
024 * It allows to allocate a cache of precomputed values.
025 * In case of cache miss, computation is performed by a call to
026 * {@link LogGamma#value(double)}.
027 */
028public final class LogFactorial {
029    /**
030     * Size of precomputed factorials.
031     * @see Factorial
032     */
033    private static final int FACTORIALS_CACHE_SIZE = 21;
034    /**
035     * Precomputed values of the function: {@code logFactorials[i] = Math.log(i!)}.
036     */
037    private final double[] logFactorials;
038
039    /**
040     * Creates an instance, reusing the already computed values if available.
041     *
042     * @param numValues Number of values of the function to compute.
043     * @param cache Cached values.
044     * @throws IllegalArgumentException if {@code n < 0}.
045     */
046    private LogFactorial(int numValues,
047                         double[] cache) {
048        if (numValues < 0) {
049            throw new CombinatoricsException(CombinatoricsException.NEGATIVE, numValues);
050        }
051
052        logFactorials = new double[numValues];
053
054        final int beginCopy = 2;
055        final int endCopy;
056        if (cache == null || cache.length <= beginCopy) {
057            endCopy = beginCopy;
058        } else {
059            endCopy = Math.min(cache.length, numValues);
060        }
061
062
063        // Copy available values.
064        if (endCopy - beginCopy > 0) {
065            System.arraycopy(cache, beginCopy, logFactorials, beginCopy, endCopy - beginCopy);
066        }
067
068        // Precompute.
069        for (int i = endCopy; i < numValues; i++) {
070            logFactorials[i] = logFactorials[i - 1] + Math.log(i);
071        }
072    }
073
074    /**
075     * Creates an instance with no precomputed values.
076     * @return instance with no precomputed values
077     */
078    public static LogFactorial create() {
079        return new LogFactorial(0, null);
080    }
081
082    /**
083     * Creates an instance with the specified cache size.
084     *
085     * @param cacheSize Number of precomputed values of the function.
086     * @return a new instance where {@code cacheSize} values have been
087     * precomputed.
088     * @throws IllegalArgumentException if {@code cacheSize < 0}.
089     */
090    public LogFactorial withCache(final int cacheSize) {
091        return new LogFactorial(cacheSize, logFactorials);
092    }
093
094    /**
095     * Computes \( log_e(n!) \).
096     *
097     * @param n Argument.
098     * @return {@code log(n!)}.
099     * @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}