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}