001// ============================================================================
002//   Copyright 2006-2012 Daniel W. Dyer
003//
004//   Licensed under the Apache License, Version 2.0 (the "License");
005//   you may not use this file except in compliance with the License.
006//   You may obtain a copy of the License at
007//
008//       http://www.apache.org/licenses/LICENSE-2.0
009//
010//   Unless required by applicable law or agreed to in writing, software
011//   distributed under the License is distributed on an "AS IS" BASIS,
012//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013//   See the License for the specific language governing permissions and
014//   limitations under the License.
015// ============================================================================
016package squidpony.squidmath;
017
018import java.math.BigInteger;
019import java.util.LinkedHashMap;
020
021/**
022 * Mathematical operations not provided by {@link Math java.lang.Math}.
023 * <br>
024 * Originally part of the <a href="http://maths.uncommons.org/">Uncommon Maths software package</a> as Maths.
025 * @author Daniel Dyer
026 */
027public final class MathExtras
028{
029    // The biggest factorial that can be calculated using 64-bit signed longs.
030    private static final int MAX_LONG_FACTORIAL = 20;
031
032    // Cache BigInteger factorial values because they are expensive to generate.
033    private static final int CACHE_SIZE = 256;
034    static final long[] factorialsStart = new long[]{
035            0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600,
036            6227020800L, 87178291200L, 1307674368000L, 20922789888000L, 355687428096000L,
037            6402373705728000L, 121645100408832000L, 2432902008176640000L
038    };
039    private static final LinkedHashMap<Integer, BigInteger> BIG_FACTORIALS
040        = new LinkedHashMap<Integer, BigInteger>();
041
042
043    private MathExtras()
044    {
045        // Prevent instantiation.
046    }
047
048
049    /**
050     * Calculates the factorial of n where n is a number in the
051     * range 0 - 20.  Zero factorial is equal to 1.  For values of
052     * n greater than 20 you must use {@link #bigFactorial(int)}.
053     * @param n The factorial to calculate.
054     * @return The factorial of n.
055     * @see #bigFactorial(int)
056     */
057    public static long factorial(int n)
058    {
059        if (n < 0 || n > MAX_LONG_FACTORIAL)
060        {
061            throw new IllegalArgumentException("Argument must be in the range 0 - 20.");
062        }
063        /*
064        long factorial = 1;
065        for (int i = n; i > 1; i--)
066        {
067            factorial *= i;
068        }*/
069        return factorialsStart[n];
070    }
071
072
073    /**
074     * Calculates the factorial of n where n is a positive integer.
075     * Zero factorial is equal to 1.  For values of n up to 20, consider
076     * using {@link #factorial(int)} instead since it uses a faster
077     * implementation.
078     * @param n The factorial to calculate.
079     * @return The factorial of n.
080     * @see #factorial(int)
081     */
082    public static BigInteger bigFactorial(int n)
083    {
084        if (n < 0)
085        {
086            throw new IllegalArgumentException("Argument must greater than or equal to zero.");
087        }
088
089        BigInteger factorial = null;
090        if (n < CACHE_SIZE) // Check for a cached value.
091        {
092            factorial = BIG_FACTORIALS.get(n);
093        }
094
095        if (factorial == null)
096        {
097            factorial = BigInteger.ONE;
098            for (int i = n; i > 1; i--)
099            {
100                factorial = factorial.multiply(BigInteger.valueOf(i));
101            }
102            if (n < CACHE_SIZE) // Cache value.
103            {
104                if(!BIG_FACTORIALS.containsKey(n))
105                    BIG_FACTORIALS.put(n, factorial);
106            }
107        }
108
109        return factorial;
110    }
111
112
113    /**
114     * Calculate the first argument raised to the power of the second.
115     * This method only supports non-negative powers.
116     * @param value The number to be raised.
117     * @param power The exponent (must be positive).
118     * @return {@code value} raised to {@code power}.
119     */
120    public static long raiseToPower(int value, int power)
121    {
122        if (power < 0)
123        {
124            throw new IllegalArgumentException("This method does not support negative powers.");
125        }
126        long result = 1;
127        for (int i = 0; i < power; i++)
128        {
129            result *= value;
130        }
131        return result;
132    }
133
134
135    /**
136     * Calculate logarithms for arbitrary bases.
137     * @param base The base for the logarithm.
138     * @param arg The value to calculate the logarithm for.
139     * @return The log of {@code arg} in the specified {@code base}.
140     */
141    public static double log(double base, double arg)
142    {
143        // Use natural logarithms and change the base.
144        return Math.log(arg) / Math.log(base);
145    }
146
147
148    /**
149     * Checks that two values are approximately equal (plus or minus a specified tolerance).
150     * @param value1 The first value to compare.
151     * @param value2 The second value to compare.
152     * @param tolerance How much (in percentage terms, as a percentage of the first value)
153     * the values are allowed to differ and still be considered equal.  Expressed as a value
154     * between 0 and 1.
155     * @return true if the values are approximately equal, false otherwise.
156     */
157    public static boolean approxEquals(double value1,
158                                       double value2,
159                                       double tolerance)
160    {
161        if (tolerance < 0 || tolerance > 1)
162        {
163            throw new IllegalArgumentException("Tolerance must be between 0 and 1.");
164        }
165        return Math.abs(value1 - value2) <= value1 * tolerance;
166    }
167
168
169    /**
170     * If the specified value is not greater than or equal to the specified minimum and
171     * less than or equal to the specified maximum, adjust it so that it is.
172     * @param value The value to check.
173     * @param min The minimum permitted value.
174     * @param max The maximum permitted value.
175     * @return {@code value} if it is between the specified limits, {@code min} if the value
176     * is too low, or {@code max} if the value is too high.
177     * @since 1.2
178     */
179    public static int restrictRange(int value, int min, int max)
180    {
181        return Math.min((Math.max(value, min)), max);
182    }
183
184
185    /**
186     * If the specified value is not greater than or equal to the specified minimum and
187     * less than or equal to the specified maximum, adjust it so that it is.
188     * @param value The value to check.
189     * @param min The minimum permitted value.
190     * @param max The maximum permitted value.
191     * @return {@code value} if it is between the specified limits, {@code min} if the value
192     * is too low, or {@code max} if the value is too high.
193     * @since 1.2
194     */
195    public static long restrictRange(long value, long min, long max)
196    {
197        return Math.min((Math.max(value, min)), max);
198    }
199
200
201    /**
202     * If the specified value is not greater than or equal to the specified minimum and
203     * less than or equal to the specified maximum, adjust it so that it is.
204     * @param value The value to check.
205     * @param min The minimum permitted value.
206     * @param max The maximum permitted value.
207     * @return {@code value} if it is between the specified limits, {@code min} if the value
208     * is too low, or {@code max} if the value is too high.
209     * @since 1.2
210     */
211    public static double restrictRange(double value, double min, double max)
212    {
213        return Math.min((Math.max(value, min)), max);
214    }
215
216
217    /**
218     * Determines the greatest common divisor of a pair of natural numbers
219     * using the Euclidean algorithm.  This method only works with natural
220     * numbers.  If negative integers are passed in, the absolute values will
221     * be used.  The return value is always positive.
222     * @param a The first value.
223     * @param b The second value.
224     * @return The greatest common divisor.
225     * @since 1.2
226     */
227    public static long greatestCommonDivisor(long a, long b)
228    {
229        a = Math.abs(a);
230        b = Math.abs(b);
231        while (b != 0)
232        {
233            long temp = b;
234            b = a % b;
235            a = temp;
236        }
237        return a;
238    }
239}