root / trunk / libraries / libTopology / src / org / geotools / referencefork / math / XMath.java @ 22875
History | View | Annotate | Download (16.7 KB)
| 1 |
/*
|
|---|---|
| 2 |
* GeoTools - The Open Source Java GIS Toolkit
|
| 3 |
* http://geotools.org
|
| 4 |
*
|
| 5 |
* (C) 2001-2008, Open Source Geospatial Foundation (OSGeo)
|
| 6 |
*
|
| 7 |
* This library is free software; you can redistribute it and/or
|
| 8 |
* modify it under the terms of the GNU Lesser General Public
|
| 9 |
* License as published by the Free Software Foundation;
|
| 10 |
* version 2.1 of the License.
|
| 11 |
*
|
| 12 |
* This library is distributed in the hope that it will be useful,
|
| 13 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
| 14 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
| 15 |
* Lesser General Public License for more details.
|
| 16 |
*/
|
| 17 |
package org.geotools.referencefork.math; |
| 18 |
|
| 19 |
//import org.geotools.resources.XArray;
|
| 20 |
//import static org.geotools.resources.XMath.next;
|
| 21 |
//import static org.geotools.resources.XMath.previous;
|
| 22 |
|
| 23 |
|
| 24 |
/**
|
| 25 |
* Simple mathematical functions in addition to the ones provided in {@link Math}.
|
| 26 |
*
|
| 27 |
* @since 2.5
|
| 28 |
* @source $URL$
|
| 29 |
* @version $Id$
|
| 30 |
* @author Martin Desruisseaux (IRD)
|
| 31 |
*/
|
| 32 |
public final class XMath { |
| 33 |
/**
|
| 34 |
* Table of some integer powers of 10. Used for fast computation of {@link #pow10(int)}.
|
| 35 |
*/
|
| 36 |
private static final double[] POW10 = { |
| 37 |
1E+00, 1E+01, 1E+02, 1E+03, 1E+04, 1E+05, 1E+06, 1E+07, 1E+08, 1E+09, |
| 38 |
1E+10, 1E+11, 1E+12, 1E+13, 1E+14, 1E+15, 1E+16, 1E+17, 1E+18, 1E+19, |
| 39 |
1E+20, 1E+21, 1E+22 |
| 40 |
// Do not add more elements, unless we verified that 1/x is accurate.
|
| 41 |
// Last time we tried, it was not accurate anymore starting at 1E+23.
|
| 42 |
}; |
| 43 |
|
| 44 |
/**
|
| 45 |
* The sequence of prime numbers computed so far. Will be expanded as needed.
|
| 46 |
* We limit ourself to 16 bits numbers because they are suffisient for computing
|
| 47 |
* divisors of any 32 bits number.
|
| 48 |
*/
|
| 49 |
private static short[] primes = new short[] {2, 3}; |
| 50 |
|
| 51 |
/**
|
| 52 |
* Maximum length allowed for the {@link #primes} array. This is the index
|
| 53 |
* of the first prime number that can not be stored as 16 bits unsigned.
|
| 54 |
*/
|
| 55 |
private static final int MAX_PRIMES_LENGTH = 6542; |
| 56 |
|
| 57 |
/**
|
| 58 |
* Do not allow instantiation of this class.
|
| 59 |
*/
|
| 60 |
private XMath() {
|
| 61 |
} |
| 62 |
|
| 63 |
/**
|
| 64 |
* Computes 10 raised to the power of <var>x</var>. This method delegates to
|
| 65 |
* {@link #pow10(int)} if <var>x</var> is an integer, or to {@link Math#pow}
|
| 66 |
* otherwise.
|
| 67 |
*
|
| 68 |
* @param x The exponent.
|
| 69 |
* @return 10 raised to the given exponent.
|
| 70 |
*/
|
| 71 |
public static double pow10(final double x) { |
| 72 |
final int ix = (int) x; |
| 73 |
if (ix == x) {
|
| 74 |
return pow10(ix);
|
| 75 |
} else {
|
| 76 |
return Math.pow(10, x); |
| 77 |
} |
| 78 |
} |
| 79 |
|
| 80 |
/**
|
| 81 |
* Computes 10 raised to the power of <var>x</var>. This method tries to be slightly more
|
| 82 |
* accurate than <code>{@linkplain Math#pow Math.pow}(10,x)</code>, sometime at the cost
|
| 83 |
* of performance.
|
| 84 |
* <p>
|
| 85 |
* The {@code Math.pow(10,x)} method doesn't always return the closest IEEE floating point
|
| 86 |
* representation. More accurate calculations are slower and usually not necessary, but the
|
| 87 |
* base 10 is a special case since it is used for scaling axes or formatting human-readable
|
| 88 |
* output, in which case the precision may matter.
|
| 89 |
*
|
| 90 |
* @param x The exponent.
|
| 91 |
* @return 10 raised to the given exponent.
|
| 92 |
*/
|
| 93 |
public static strictfp double pow10(final int x) { |
| 94 |
if (x >= 0) { |
| 95 |
if (x < POW10.length) {
|
| 96 |
return POW10[x];
|
| 97 |
} |
| 98 |
} else if (x != Integer.MIN_VALUE) { |
| 99 |
final int nx = -x; |
| 100 |
if (nx < POW10.length) {
|
| 101 |
return 1 / POW10[nx]; |
| 102 |
} |
| 103 |
} |
| 104 |
try {
|
| 105 |
/*
|
| 106 |
* Double.parseDouble("1E"+x) give gives as good or better numbers than Math.pow(10,x)
|
| 107 |
* for ALL integer powers, but is slower. We hope that the current workaround is only
|
| 108 |
* temporary. See http://developer.java.sun.com/developer/bugParade/bugs/4358794.html
|
| 109 |
*/
|
| 110 |
return Double.parseDouble("1E" + x); |
| 111 |
} catch (NumberFormatException exception) { |
| 112 |
return StrictMath.pow(10, x); |
| 113 |
} |
| 114 |
} |
| 115 |
|
| 116 |
/**
|
| 117 |
* Returns the sign of <var>x</var>. This method returns
|
| 118 |
* -1 if <var>x</var> is negative,
|
| 119 |
* 0 if <var>x</var> is zero or {@code NaN} and
|
| 120 |
* +1 if <var>x</var> is positive.
|
| 121 |
*
|
| 122 |
* @param x The number from which to get the sign.
|
| 123 |
* @return {@code +1} if <var>x</var> is positive, {@code -1} if negative, or 0 otherwise.
|
| 124 |
*
|
| 125 |
* @see Math#signum(double)
|
| 126 |
*/
|
| 127 |
public static int sgn(final double x) { |
| 128 |
if (x > 0) return +1; |
| 129 |
if (x < 0) return -1; |
| 130 |
else return 0; |
| 131 |
} |
| 132 |
|
| 133 |
/**
|
| 134 |
* Returns the sign of <var>x</var>. This method returns
|
| 135 |
* -1 if <var>x</var> is negative,
|
| 136 |
* 0 if <var>x</var> is zero or {@code NaN} and
|
| 137 |
* +1 if <var>x</var> is positive.
|
| 138 |
*
|
| 139 |
* @param x The number from which to get the sign.
|
| 140 |
* @return {@code +1} if <var>x</var> is positive, {@code -1} if negative, or 0 otherwise.
|
| 141 |
*
|
| 142 |
* @see Math#signum(float)
|
| 143 |
*/
|
| 144 |
public static int sgn(final float x) { |
| 145 |
if (x > 0) return +1; |
| 146 |
if (x < 0) return -1; |
| 147 |
else return 0; |
| 148 |
} |
| 149 |
|
| 150 |
/**
|
| 151 |
* Returns the sign of <var>x</var>. This method returns
|
| 152 |
* -1 if <var>x</var> is negative,
|
| 153 |
* 0 if <var>x</var> is zero and
|
| 154 |
* +1 if <var>x</var> is positive.
|
| 155 |
*
|
| 156 |
* @param x The number from which to get the sign.
|
| 157 |
* @return {@code +1} if <var>x</var> is positive, {@code -1} if negative, or 0 otherwise.
|
| 158 |
*/
|
| 159 |
public static int sgn(long x) { |
| 160 |
if (x > 0) return +1; |
| 161 |
if (x < 0) return -1; |
| 162 |
else return 0; |
| 163 |
} |
| 164 |
|
| 165 |
/**
|
| 166 |
* Returns the sign of <var>x</var>. This method returns
|
| 167 |
* -1 if <var>x</var> is negative,
|
| 168 |
* 0 if <var>x</var> is zero and
|
| 169 |
* +1 if <var>x</var> is positive.
|
| 170 |
*
|
| 171 |
* @param x The number from which to get the sign.
|
| 172 |
* @return {@code +1} if <var>x</var> is positive, {@code -1} if negative, or 0 otherwise.
|
| 173 |
*/
|
| 174 |
public static int sgn(int x) { |
| 175 |
if (x > 0) return +1; |
| 176 |
if (x < 0) return -1; |
| 177 |
else return 0; |
| 178 |
} |
| 179 |
|
| 180 |
/**
|
| 181 |
* Returns the sign of <var>x</var>. This method returns
|
| 182 |
* -1 if <var>x</var> is negative,
|
| 183 |
* 0 if <var>x</var> is zero and
|
| 184 |
* +1 if <var>x</var> is positive.
|
| 185 |
*
|
| 186 |
* @param x The number from which to get the sign.
|
| 187 |
* @return {@code +1} if <var>x</var> is positive, {@code -1} if negative, or 0 otherwise.
|
| 188 |
*/
|
| 189 |
public static short sgn(short x) { |
| 190 |
if (x > 0) return (short) +1; |
| 191 |
if (x < 0) return (short) -1; |
| 192 |
else return (short) 0; |
| 193 |
} |
| 194 |
|
| 195 |
/**
|
| 196 |
* Returns the sign of <var>x</var>. This method returns
|
| 197 |
* -1 if <var>x</var> is negative,
|
| 198 |
* 0 if <var>x</var> is zero and
|
| 199 |
* +1 if <var>x</var> is positive.
|
| 200 |
*
|
| 201 |
* @param x The number from which to get the sign.
|
| 202 |
* @return {@code +1} if <var>x</var> is positive, {@code -1} if negative, or 0 otherwise.
|
| 203 |
*/
|
| 204 |
public static byte sgn(byte x) { |
| 205 |
if (x > 0) return (byte) +1; |
| 206 |
if (x < 0) return (byte) -1; |
| 207 |
else return (byte) 0; |
| 208 |
} |
| 209 |
|
| 210 |
/**
|
| 211 |
* Rounds the specified value, providing that the difference between the original value and
|
| 212 |
* the rounded value is not greater than the specified amount of floating point units. This
|
| 213 |
* method can be used for hiding floating point error likes 2.9999999996.
|
| 214 |
*
|
| 215 |
* @param value The value to round.
|
| 216 |
* @param maxULP The maximal change allowed in ULPs (Unit in the Last Place).
|
| 217 |
* @return The rounded value, of {@code value} if it was not close enough to an integer.
|
| 218 |
*/
|
| 219 |
// public static double roundIfAlmostInteger(final double value, int maxULP) {
|
| 220 |
// final double target = Math.rint(value);
|
| 221 |
// if (value != target) {
|
| 222 |
// final boolean pos = (value < target);
|
| 223 |
// double candidate = value;
|
| 224 |
// while (--maxULP >= 0) {
|
| 225 |
// candidate = pos ? next(candidate) : previous(candidate);
|
| 226 |
// if (candidate == target) {
|
| 227 |
// return target;
|
| 228 |
// }
|
| 229 |
// }
|
| 230 |
// }
|
| 231 |
// return value;
|
| 232 |
// }
|
| 233 |
|
| 234 |
/**
|
| 235 |
* Tries to remove at least {@code n} fraction digits in the decimal representation of
|
| 236 |
* the specified value. This method tries small changes to {@code value}, by adding or
|
| 237 |
* substracting up to {@code maxULP} (Unit in the Last Place). If there is no small
|
| 238 |
* change that remove at least {@code n} fraction digits, then the value is returned
|
| 239 |
* unchanged. This method is used for hiding rounding errors, like in conversions from
|
| 240 |
* radians to degrees.
|
| 241 |
* <P>
|
| 242 |
* Example:
|
| 243 |
* {@code XMath.trimLastDecimalDigits(-61.500000000000014, 12, 4)} returns {@code -61.5}.
|
| 244 |
*
|
| 245 |
* @param value The value to fix.
|
| 246 |
* @param maxULP The maximal change allowed in ULPs (Unit in the Last Place).
|
| 247 |
* A typical value is 4.
|
| 248 |
* @param n The minimum amount of fraction digits.
|
| 249 |
* @return The trimmed value, or the unchanged {@code value} if there is no small change
|
| 250 |
* that remove at least {@code n} fraction digits.
|
| 251 |
*/
|
| 252 |
// public static double trimDecimalFractionDigits(final double value, final int maxULP, int n) {
|
| 253 |
// double lower = value;
|
| 254 |
// double upper = value;
|
| 255 |
// n = countDecimalFractionDigits(value) - n;
|
| 256 |
// if (n > 0) {
|
| 257 |
// for (int i=0; i<maxULP; i++) {
|
| 258 |
// if (countDecimalFractionDigits(lower = previous(lower)) <= n) return lower;
|
| 259 |
// if (countDecimalFractionDigits(upper = next (upper)) <= n) return upper;
|
| 260 |
// }
|
| 261 |
// }
|
| 262 |
// return value;
|
| 263 |
// }
|
| 264 |
|
| 265 |
/**
|
| 266 |
* Counts the fraction digits in the string representation of the specified value. This method
|
| 267 |
* is equivalent to a calling <code>{@linkplain Double#toString(double) Double.toString}(value)</code>
|
| 268 |
* and counting the number of digits after the decimal separator.
|
| 269 |
*
|
| 270 |
* @param value The value for which to count the fraction digits.
|
| 271 |
* @return The number of fraction digits.
|
| 272 |
*/
|
| 273 |
public static int countDecimalFractionDigits(final double value) { |
| 274 |
final String asText = Double.toString(value); |
| 275 |
final int exp = asText.indexOf('E'); |
| 276 |
int upper, power;
|
| 277 |
if (exp >= 0) { |
| 278 |
upper = exp; |
| 279 |
power = Integer.parseInt(asText.substring(exp+1)); |
| 280 |
} else {
|
| 281 |
upper = asText.length(); |
| 282 |
power = 0;
|
| 283 |
} |
| 284 |
while ((asText.charAt(--upper)) == '0'); |
| 285 |
return Math.max(upper - asText.indexOf('.') - power, 0); |
| 286 |
} |
| 287 |
|
| 288 |
/**
|
| 289 |
* Returns a {@link Float#NaN NaN} number for the specified index. Valid NaN numbers have
|
| 290 |
* bit fields ranging from {@code 0x7f800001} through {@code 0x7fffffff} or {@code 0xff800001}
|
| 291 |
* through {@code 0xffffffff}. The standard {@link Float#NaN} has bit fields {@code 0x7fc00000}.
|
| 292 |
* See {@link Float#intBitsToFloat} for more details on NaN bit values.
|
| 293 |
*
|
| 294 |
* @param index The index, from -2097152 to 2097151 inclusive.
|
| 295 |
* @return One of the legal {@link Float#NaN NaN} values as a float.
|
| 296 |
* @throws IndexOutOfBoundsException if the specified index is out of bounds.
|
| 297 |
*
|
| 298 |
* @see Float#intBitsToFloat
|
| 299 |
*/
|
| 300 |
public static float toNaN(int index) throws IndexOutOfBoundsException { |
| 301 |
index += 0x200000;
|
| 302 |
if (index>=0 && index<=0x3FFFFF) { |
| 303 |
final float value = Float.intBitsToFloat(0x7FC00000 + index); |
| 304 |
assert Float.isNaN(value) : value; |
| 305 |
return value;
|
| 306 |
} |
| 307 |
else {
|
| 308 |
throw new IndexOutOfBoundsException(Integer.toHexString(index)); |
| 309 |
} |
| 310 |
} |
| 311 |
|
| 312 |
/**
|
| 313 |
* Returns the <var>i</var><sup>th</sup> prime number. This method returns (2,3,5,7,11...)
|
| 314 |
* for index (0,1,2,3,4...). This method is designed for relatively small prime numbers only;
|
| 315 |
* don't use it for large values.
|
| 316 |
*
|
| 317 |
* @param index The prime number index, starting at index 0 for prime number 2.
|
| 318 |
* @return The prime number at the specified index.
|
| 319 |
* @throws IndexOutOfBoundsException if the specified index is too large.
|
| 320 |
*
|
| 321 |
* @see java.math.BigInteger#isProbablePrime
|
| 322 |
*/
|
| 323 |
// public static synchronized int primeNumber(final int index) throws IndexOutOfBoundsException {
|
| 324 |
// // 6541 is the largest index returning a 16 bits unsigned prime number.
|
| 325 |
// if (index < 0 || index >= MAX_PRIMES_LENGTH) {
|
| 326 |
// throw new IndexOutOfBoundsException(String.valueOf(index));
|
| 327 |
// }
|
| 328 |
// short[] primes = XMath.primes;
|
| 329 |
// if (index >= primes.length) {
|
| 330 |
// int i = primes.length;
|
| 331 |
// int n = primes[i - 1] & 0xFFFF;
|
| 332 |
// primes = XArray.resize(primes, Math.min((index | 0xF) + 1, MAX_PRIMES_LENGTH));
|
| 333 |
// do {
|
| 334 |
//next: while (true) {
|
| 335 |
// n += 2;
|
| 336 |
// for (int j=1; j<i; j++) {
|
| 337 |
// if (n % (primes[j] & 0xFFFF) == 0) {
|
| 338 |
// continue next;
|
| 339 |
// }
|
| 340 |
// // We could stop the search at the first value greater than sqrt(n), but
|
| 341 |
// // given that the array is relatively short (because we limit ourself to
|
| 342 |
// // 16 bits prime numbers), it probably doesn't worth.
|
| 343 |
// }
|
| 344 |
// assert n < 0xFFFF : i;
|
| 345 |
// primes[i] = (short) n;
|
| 346 |
// break;
|
| 347 |
// }
|
| 348 |
// } while (++i < primes.length);
|
| 349 |
// XMath.primes = primes;
|
| 350 |
// }
|
| 351 |
// return primes[index] & 0xFFFF;
|
| 352 |
// }
|
| 353 |
|
| 354 |
/**
|
| 355 |
* Returns the divisors of the specified number as positive integers. For any value other
|
| 356 |
* than {@code O} (which returns an empty array), the first element in the returned array
|
| 357 |
* is always {@code 1} and the last element is always the absolute value of {@code number}.
|
| 358 |
*
|
| 359 |
* @param number The number for which to compute the divisors.
|
| 360 |
* @return The divisors in strictly increasing order.
|
| 361 |
*/
|
| 362 |
// public static int[] divisors(int number) {
|
| 363 |
// if (number == 0) {
|
| 364 |
// return new int[0];
|
| 365 |
// }
|
| 366 |
// number = Math.abs(number);
|
| 367 |
// int[] divisors = new int[16];
|
| 368 |
// divisors[0] = 1;
|
| 369 |
// int count = 1;
|
| 370 |
// /*
|
| 371 |
// * Searchs for the first divisors among the prime numbers. We stop the search at the
|
| 372 |
// * square root of 'n' because every values above that point can be inferred from the
|
| 373 |
// * values before that point, i.e. if n=p1*p2 and p2 is greater than 'sqrt', than p1
|
| 374 |
// * most be lower than 'sqrt'.
|
| 375 |
// */
|
| 376 |
// final int sqrt = (int) (Math.sqrt(number) + 1E-6); // Really wants rounding toward 0.
|
| 377 |
// for (int p,i=0; (p=primeNumber(i)) <= sqrt; i++) {
|
| 378 |
// if (number % p == 0) {
|
| 379 |
// if (count == divisors.length) {
|
| 380 |
// divisors = XArray.resize(divisors, count*2);
|
| 381 |
// }
|
| 382 |
// divisors[count++] = p;
|
| 383 |
// }
|
| 384 |
// }
|
| 385 |
// /*
|
| 386 |
// * Completes the divisors past 'sqrt'. The numbers added here may or may not be prime
|
| 387 |
// * numbers. Side note: checking that they are prime numbers would be costly, but this
|
| 388 |
// * algorithm doesn't need that.
|
| 389 |
// */
|
| 390 |
// int source = count;
|
| 391 |
// if (count*2 > divisors.length) {
|
| 392 |
// divisors = XArray.resize(divisors, count*2);
|
| 393 |
// }
|
| 394 |
// int d1 = divisors[--source];
|
| 395 |
// int d2 = number / d1;
|
| 396 |
// if (d1 != d2) {
|
| 397 |
// divisors[count++] = d2;
|
| 398 |
// }
|
| 399 |
// while (--source >= 0) {
|
| 400 |
// divisors[count++] = number / divisors[source];
|
| 401 |
// }
|
| 402 |
// /*
|
| 403 |
// * Checks the products of divisors found so far. For example if 2 and 3 are divisors,
|
| 404 |
// * checks if 6 is a divisor as well. The products found will themself be used for
|
| 405 |
// * computing new products.
|
| 406 |
// */
|
| 407 |
// for (int i=1; i<count; i++) {
|
| 408 |
// d1 = divisors[i];
|
| 409 |
// for (int j=i; j<count; j++) {
|
| 410 |
// d2 = d1 * divisors[j];
|
| 411 |
// if (number % d2 == 0) {
|
| 412 |
// int p = org.geotools.resources.Java6.binarySearch(divisors, j, count, d2);
|
| 413 |
// if (p < 0) {
|
| 414 |
// p = ~p; // ~ operator, not minus
|
| 415 |
// if (count == divisors.length) {
|
| 416 |
// divisors = XArray.resize(divisors, count*2);
|
| 417 |
// }
|
| 418 |
// System.arraycopy(divisors, p, divisors, p+1, count-p);
|
| 419 |
// divisors[p] = d2;
|
| 420 |
// count++;
|
| 421 |
// }
|
| 422 |
// }
|
| 423 |
// }
|
| 424 |
// }
|
| 425 |
// divisors = XArray.resize(divisors, count);
|
| 426 |
// assert XArray.isStrictlySorted(divisors);
|
| 427 |
// return divisors;
|
| 428 |
// }
|
| 429 |
} |