| 1 |
// Copyright 2006 The Closure Library Authors. All Rights Reserved. |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS-IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
/** |
| 16 |
* @fileoverview Additional mathematical functions. |
| 17 |
*/ |
| 18 |
|
| 19 |
goog.provide('goog.math'); |
| 20 |
|
| 21 |
goog.require('goog.array'); |
| 22 |
goog.require('goog.asserts'); |
| 23 |
|
| 24 |
|
| 25 |
/** |
| 26 |
* Returns a random integer greater than or equal to 0 and less than {@code a}. |
| 27 |
* @param {number} a The upper bound for the random integer (exclusive). |
| 28 |
* @return {number} A random integer N such that 0 <= N < a. |
| 29 |
*/ |
| 30 |
goog.math.randomInt = function(a) { |
| 31 |
return Math.floor(Math.random() * a); |
| 32 |
}; |
| 33 |
|
| 34 |
|
| 35 |
/** |
| 36 |
* Returns a random number greater than or equal to {@code a} and less than |
| 37 |
* {@code b}. |
| 38 |
* @param {number} a The lower bound for the random number (inclusive). |
| 39 |
* @param {number} b The upper bound for the random number (exclusive). |
| 40 |
* @return {number} A random number N such that a <= N < b. |
| 41 |
*/ |
| 42 |
goog.math.uniformRandom = function(a, b) { |
| 43 |
return a + Math.random() * (b - a); |
| 44 |
}; |
| 45 |
|
| 46 |
|
| 47 |
/** |
| 48 |
* Takes a number and clamps it to within the provided bounds. |
| 49 |
* @param {number} value The input number. |
| 50 |
* @param {number} min The minimum value to return. |
| 51 |
* @param {number} max The maximum value to return. |
| 52 |
* @return {number} The input number if it is within bounds, or the nearest |
| 53 |
* number within the bounds. |
| 54 |
*/ |
| 55 |
goog.math.clamp = function(value, min, max) { |
| 56 |
return Math.min(Math.max(value, min), max); |
| 57 |
}; |
| 58 |
|
| 59 |
|
| 60 |
/** |
| 61 |
* The % operator in JavaScript returns the remainder of a / b, but differs from |
| 62 |
* some other languages in that the result will have the same sign as the |
| 63 |
* dividend. For example, -1 % 8 == -1, whereas in some other languages |
| 64 |
* (such as Python) the result would be 7. This function emulates the more |
| 65 |
* correct modulo behavior, which is useful for certain applications such as |
| 66 |
* calculating an offset index in a circular list. |
| 67 |
* |
| 68 |
* @param {number} a The dividend. |
| 69 |
* @param {number} b The divisor. |
| 70 |
* @return {number} a % b where the result is between 0 and b (either 0 <= x < b |
| 71 |
* or b < x <= 0, depending on the sign of b). |
| 72 |
*/ |
| 73 |
goog.math.modulo = function(a, b) { |
| 74 |
var r = a % b; |
| 75 |
// If r and b differ in sign, add b to wrap the result to the correct sign. |
| 76 |
return (r * b < 0) ? r + b : r; |
| 77 |
}; |
| 78 |
|
| 79 |
|
| 80 |
/** |
| 81 |
* Performs linear interpolation between values a and b. Returns the value |
| 82 |
* between a and b proportional to x (when x is between 0 and 1. When x is |
| 83 |
* outside this range, the return value is a linear extrapolation). |
| 84 |
* @param {number} a A number. |
| 85 |
* @param {number} b A number. |
| 86 |
* @param {number} x The proportion between a and b. |
| 87 |
* @return {number} The interpolated value between a and b. |
| 88 |
*/ |
| 89 |
goog.math.lerp = function(a, b, x) { |
| 90 |
return a + x * (b - a); |
| 91 |
}; |
| 92 |
|
| 93 |
|
| 94 |
/** |
| 95 |
* Tests whether the two values are equal to each other, within a certain |
| 96 |
* tolerance to adjust for floating point errors. |
| 97 |
* @param {number} a A number. |
| 98 |
* @param {number} b A number. |
| 99 |
* @param {number=} opt_tolerance Optional tolerance range. Defaults |
| 100 |
* to 0.000001. If specified, should be greater than 0. |
| 101 |
* @return {boolean} Whether {@code a} and {@code b} are nearly equal. |
| 102 |
*/ |
| 103 |
goog.math.nearlyEquals = function(a, b, opt_tolerance) { |
| 104 |
return Math.abs(a - b) <= (opt_tolerance || 0.000001); |
| 105 |
}; |
| 106 |
|
| 107 |
|
| 108 |
// TODO(user): Rename to normalizeAngle, retaining old name as deprecated |
| 109 |
// alias. |
| 110 |
/** |
| 111 |
* Normalizes an angle to be in range [0-360). Angles outside this range will |
| 112 |
* be normalized to be the equivalent angle with that range. |
| 113 |
* @param {number} angle Angle in degrees. |
| 114 |
* @return {number} Standardized angle. |
| 115 |
*/ |
| 116 |
goog.math.standardAngle = function(angle) { |
| 117 |
return goog.math.modulo(angle, 360); |
| 118 |
}; |
| 119 |
|
| 120 |
|
| 121 |
/** |
| 122 |
* Normalizes an angle to be in range [0-2*PI). Angles outside this range will |
| 123 |
* be normalized to be the equivalent angle with that range. |
| 124 |
* @param {number} angle Angle in radians. |
| 125 |
* @return {number} Standardized angle. |
| 126 |
*/ |
| 127 |
goog.math.standardAngleInRadians = function(angle) { |
| 128 |
return goog.math.modulo(angle, 2 * Math.PI); |
| 129 |
}; |
| 130 |
|
| 131 |
|
| 132 |
/** |
| 133 |
* Converts degrees to radians. |
| 134 |
* @param {number} angleDegrees Angle in degrees. |
| 135 |
* @return {number} Angle in radians. |
| 136 |
*/ |
| 137 |
goog.math.toRadians = function(angleDegrees) { |
| 138 |
return angleDegrees * Math.PI / 180; |
| 139 |
}; |
| 140 |
|
| 141 |
|
| 142 |
/** |
| 143 |
* Converts radians to degrees. |
| 144 |
* @param {number} angleRadians Angle in radians. |
| 145 |
* @return {number} Angle in degrees. |
| 146 |
*/ |
| 147 |
goog.math.toDegrees = function(angleRadians) { |
| 148 |
return angleRadians * 180 / Math.PI; |
| 149 |
}; |
| 150 |
|
| 151 |
|
| 152 |
/** |
| 153 |
* For a given angle and radius, finds the X portion of the offset. |
| 154 |
* @param {number} degrees Angle in degrees (zero points in +X direction). |
| 155 |
* @param {number} radius Radius. |
| 156 |
* @return {number} The x-distance for the angle and radius. |
| 157 |
*/ |
| 158 |
goog.math.angleDx = function(degrees, radius) { |
| 159 |
return radius * Math.cos(goog.math.toRadians(degrees)); |
| 160 |
}; |
| 161 |
|
| 162 |
|
| 163 |
/** |
| 164 |
* For a given angle and radius, finds the Y portion of the offset. |
| 165 |
* @param {number} degrees Angle in degrees (zero points in +X direction). |
| 166 |
* @param {number} radius Radius. |
| 167 |
* @return {number} The y-distance for the angle and radius. |
| 168 |
*/ |
| 169 |
goog.math.angleDy = function(degrees, radius) { |
| 170 |
return radius * Math.sin(goog.math.toRadians(degrees)); |
| 171 |
}; |
| 172 |
|
| 173 |
|
| 174 |
/** |
| 175 |
* Computes the angle between two points (x1,y1) and (x2,y2). |
| 176 |
* Angle zero points in the +X direction, 90 degrees points in the +Y |
| 177 |
* direction (down) and from there we grow clockwise towards 360 degrees. |
| 178 |
* @param {number} x1 x of first point. |
| 179 |
* @param {number} y1 y of first point. |
| 180 |
* @param {number} x2 x of second point. |
| 181 |
* @param {number} y2 y of second point. |
| 182 |
* @return {number} Standardized angle in degrees of the vector from |
| 183 |
* x1,y1 to x2,y2. |
| 184 |
*/ |
| 185 |
goog.math.angle = function(x1, y1, x2, y2) { |
| 186 |
return goog.math.standardAngle( |
| 187 |
goog.math.toDegrees(Math.atan2(y2 - y1, x2 - x1))); |
| 188 |
}; |
| 189 |
|
| 190 |
|
| 191 |
/** |
| 192 |
* Computes the difference between startAngle and endAngle (angles in degrees). |
| 193 |
* @param {number} startAngle Start angle in degrees. |
| 194 |
* @param {number} endAngle End angle in degrees. |
| 195 |
* @return {number} The number of degrees that when added to |
| 196 |
* startAngle will result in endAngle. Positive numbers mean that the |
| 197 |
* direction is clockwise. Negative numbers indicate a counter-clockwise |
| 198 |
* direction. |
| 199 |
* The shortest route (clockwise vs counter-clockwise) between the angles |
| 200 |
* is used. |
| 201 |
* When the difference is 180 degrees, the function returns 180 (not -180) |
| 202 |
* angleDifference(30, 40) is 10, and angleDifference(40, 30) is -10. |
| 203 |
* angleDifference(350, 10) is 20, and angleDifference(10, 350) is -20. |
| 204 |
*/ |
| 205 |
goog.math.angleDifference = function(startAngle, endAngle) { |
| 206 |
var d = |
| 207 |
goog.math.standardAngle(endAngle) - goog.math.standardAngle(startAngle); |
| 208 |
if (d > 180) { |
| 209 |
d = d - 360; |
| 210 |
} else if (d <= -180) { |
| 211 |
d = 360 + d; |
| 212 |
} |
| 213 |
return d; |
| 214 |
}; |
| 215 |
|
| 216 |
|
| 217 |
/** |
| 218 |
* Returns the sign of a number as per the "sign" or "signum" function. |
| 219 |
* @param {number} x The number to take the sign of. |
| 220 |
* @return {number} -1 when negative, 1 when positive, 0 when 0. Preserves |
| 221 |
* signed zeros and NaN. |
| 222 |
*/ |
| 223 |
goog.math.sign = function(x) { |
| 224 |
if (x > 0) { |
| 225 |
return 1; |
| 226 |
} |
| 227 |
if (x < 0) { |
| 228 |
return -1; |
| 229 |
} |
| 230 |
return x; // Preserves signed zeros and NaN. |
| 231 |
}; |
| 232 |
|
| 233 |
|
| 234 |
/** |
| 235 |
* JavaScript implementation of Longest Common Subsequence problem. |
| 236 |
* http://en.wikipedia.org/wiki/Longest_common_subsequence |
| 237 |
* |
| 238 |
* Returns the longest possible array that is subarray of both of given arrays. |
| 239 |
* |
| 240 |
* @param {IArrayLike<S>} array1 First array of objects. |
| 241 |
* @param {IArrayLike<T>} array2 Second array of objects. |
| 242 |
* @param {Function=} opt_compareFn Function that acts as a custom comparator |
| 243 |
* for the array ojects. Function should return true if objects are equal, |
| 244 |
* otherwise false. |
| 245 |
* @param {Function=} opt_collectorFn Function used to decide what to return |
| 246 |
* as a result subsequence. It accepts 2 arguments: index of common element |
| 247 |
* in the first array and index in the second. The default function returns |
| 248 |
* element from the first array. |
| 249 |
* @return {!Array<S|T>} A list of objects that are common to both arrays |
| 250 |
* such that there is no common subsequence with size greater than the |
| 251 |
* length of the list. |
| 252 |
* @template S,T |
| 253 |
*/ |
| 254 |
goog.math.longestCommonSubsequence = function( |
| 255 |
array1, array2, opt_compareFn, opt_collectorFn) { |
| 256 |
|
| 257 |
var compare = opt_compareFn || function(a, b) { return a == b; }; |
| 258 |
|
| 259 |
var collect = opt_collectorFn || function(i1, i2) { return array1[i1]; }; |
| 260 |
|
| 261 |
var length1 = array1.length; |
| 262 |
var length2 = array2.length; |
| 263 |
|
| 264 |
var arr = []; |
| 265 |
for (var i = 0; i < length1 + 1; i++) { |
| 266 |
arr[i] = []; |
| 267 |
arr[i][0] = 0; |
| 268 |
} |
| 269 |
|
| 270 |
for (var j = 0; j < length2 + 1; j++) { |
| 271 |
arr[0][j] = 0; |
| 272 |
} |
| 273 |
|
| 274 |
for (i = 1; i <= length1; i++) { |
| 275 |
for (j = 1; j <= length2; j++) { |
| 276 |
if (compare(array1[i - 1], array2[j - 1])) { |
| 277 |
arr[i][j] = arr[i - 1][j - 1] + 1; |
| 278 |
} else { |
| 279 |
arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]); |
| 280 |
} |
| 281 |
} |
| 282 |
} |
| 283 |
|
| 284 |
// Backtracking |
| 285 |
var result = []; |
| 286 |
var i = length1, j = length2; |
| 287 |
while (i > 0 && j > 0) { |
| 288 |
if (compare(array1[i - 1], array2[j - 1])) { |
| 289 |
result.unshift(collect(i - 1, j - 1)); |
| 290 |
i--; |
| 291 |
j--; |
| 292 |
} else { |
| 293 |
if (arr[i - 1][j] > arr[i][j - 1]) { |
| 294 |
i--; |
| 295 |
} else { |
| 296 |
j--; |
| 297 |
} |
| 298 |
} |
| 299 |
} |
| 300 |
|
| 301 |
return result; |
| 302 |
}; |
| 303 |
|
| 304 |
|
| 305 |
/** |
| 306 |
* Returns the sum of the arguments. |
| 307 |
* @param {...number} var_args Numbers to add. |
| 308 |
* @return {number} The sum of the arguments (0 if no arguments were provided, |
| 309 |
* {@code NaN} if any of the arguments is not a valid number). |
| 310 |
*/ |
| 311 |
goog.math.sum = function(var_args) { |
| 312 |
return /** @type {number} */ ( |
| 313 |
goog.array.reduce( |
| 314 |
arguments, function(sum, value) { return sum + value; }, 0)); |
| 315 |
}; |
| 316 |
|
| 317 |
|
| 318 |
/** |
| 319 |
* Returns the arithmetic mean of the arguments. |
| 320 |
* @param {...number} var_args Numbers to average. |
| 321 |
* @return {number} The average of the arguments ({@code NaN} if no arguments |
| 322 |
* were provided or any of the arguments is not a valid number). |
| 323 |
*/ |
| 324 |
goog.math.average = function(var_args) { |
| 325 |
return goog.math.sum.apply(null, arguments) / arguments.length; |
| 326 |
}; |
| 327 |
|
| 328 |
|
| 329 |
/** |
| 330 |
* Returns the unbiased sample variance of the arguments. For a definition, |
| 331 |
* see e.g. http://en.wikipedia.org/wiki/Variance |
| 332 |
* @param {...number} var_args Number samples to analyze. |
| 333 |
* @return {number} The unbiased sample variance of the arguments (0 if fewer |
| 334 |
* than two samples were provided, or {@code NaN} if any of the samples is |
| 335 |
* not a valid number). |
| 336 |
*/ |
| 337 |
goog.math.sampleVariance = function(var_args) { |
| 338 |
var sampleSize = arguments.length; |
| 339 |
if (sampleSize < 2) { |
| 340 |
return 0; |
| 341 |
} |
| 342 |
|
| 343 |
var mean = goog.math.average.apply(null, arguments); |
| 344 |
var variance = |
| 345 |
goog.math.sum.apply(null, goog.array.map(arguments, function(val) { |
| 346 |
return Math.pow(val - mean, 2); |
| 347 |
})) / (sampleSize - 1); |
| 348 |
|
| 349 |
return variance; |
| 350 |
}; |
| 351 |
|
| 352 |
|
| 353 |
/** |
| 354 |
* Returns the sample standard deviation of the arguments. For a definition of |
| 355 |
* sample standard deviation, see e.g. |
| 356 |
* http://en.wikipedia.org/wiki/Standard_deviation |
| 357 |
* @param {...number} var_args Number samples to analyze. |
| 358 |
* @return {number} The sample standard deviation of the arguments (0 if fewer |
| 359 |
* than two samples were provided, or {@code NaN} if any of the samples is |
| 360 |
* not a valid number). |
| 361 |
*/ |
| 362 |
goog.math.standardDeviation = function(var_args) { |
| 363 |
return Math.sqrt(goog.math.sampleVariance.apply(null, arguments)); |
| 364 |
}; |
| 365 |
|
| 366 |
|
| 367 |
/** |
| 368 |
* Returns whether the supplied number represents an integer, i.e. that is has |
| 369 |
* no fractional component. No range-checking is performed on the number. |
| 370 |
* @param {number} num The number to test. |
| 371 |
* @return {boolean} Whether {@code num} is an integer. |
| 372 |
*/ |
| 373 |
goog.math.isInt = function(num) { |
| 374 |
return isFinite(num) && num % 1 == 0; |
| 375 |
}; |
| 376 |
|
| 377 |
|
| 378 |
/** |
| 379 |
* Returns whether the supplied number is finite and not NaN. |
| 380 |
* @param {number} num The number to test. |
| 381 |
* @return {boolean} Whether {@code num} is a finite number. |
| 382 |
* @deprecated Use {@link isFinite} instead. |
| 383 |
*/ |
| 384 |
goog.math.isFiniteNumber = function(num) { |
| 385 |
return isFinite(num); |
| 386 |
}; |
| 387 |
|
| 388 |
|
| 389 |
/** |
| 390 |
* @param {number} num The number to test. |
| 391 |
* @return {boolean} Whether it is negative zero. |
| 392 |
*/ |
| 393 |
goog.math.isNegativeZero = function(num) { |
| 394 |
return num == 0 && 1 / num < 0; |
| 395 |
}; |
| 396 |
|
| 397 |
|
| 398 |
/** |
| 399 |
* Returns the precise value of floor(log10(num)). |
| 400 |
* Simpler implementations didn't work because of floating point rounding |
| 401 |
* errors. For example |
| 402 |
* <ul> |
| 403 |
* <li>Math.floor(Math.log(num) / Math.LN10) is off by one for num == 1e+3. |
| 404 |
* <li>Math.floor(Math.log(num) * Math.LOG10E) is off by one for num == 1e+15. |
| 405 |
* <li>Math.floor(Math.log10(num)) is off by one for num == 1e+15 - 1. |
| 406 |
* </ul> |
| 407 |
* @param {number} num A floating point number. |
| 408 |
* @return {number} Its logarithm to base 10 rounded down to the nearest |
| 409 |
* integer if num > 0. -Infinity if num == 0. NaN if num < 0. |
| 410 |
*/ |
| 411 |
goog.math.log10Floor = function(num) { |
| 412 |
if (num > 0) { |
| 413 |
var x = Math.round(Math.log(num) * Math.LOG10E); |
| 414 |
return x - (parseFloat('1e' + x) > num ? 1 : 0); |
| 415 |
} |
| 416 |
return num == 0 ? -Infinity : NaN; |
| 417 |
}; |
| 418 |
|
| 419 |
|
| 420 |
/** |
| 421 |
* A tweaked variant of {@code Math.floor} which tolerates if the passed number |
| 422 |
* is infinitesimally smaller than the closest integer. It often happens with |
| 423 |
* the results of floating point calculations because of the finite precision |
| 424 |
* of the intermediate results. For example {@code Math.floor(Math.log(1000) / |
| 425 |
* Math.LN10) == 2}, not 3 as one would expect. |
| 426 |
* @param {number} num A number. |
| 427 |
* @param {number=} opt_epsilon An infinitesimally small positive number, the |
| 428 |
* rounding error to tolerate. |
| 429 |
* @return {number} The largest integer less than or equal to {@code num}. |
| 430 |
*/ |
| 431 |
goog.math.safeFloor = function(num, opt_epsilon) { |
| 432 |
goog.asserts.assert(!goog.isDef(opt_epsilon) || opt_epsilon > 0); |
| 433 |
return Math.floor(num + (opt_epsilon || 2e-15)); |
| 434 |
}; |
| 435 |
|
| 436 |
|
| 437 |
/** |
| 438 |
* A tweaked variant of {@code Math.ceil}. See {@code goog.math.safeFloor} for |
| 439 |
* details. |
| 440 |
* @param {number} num A number. |
| 441 |
* @param {number=} opt_epsilon An infinitesimally small positive number, the |
| 442 |
* rounding error to tolerate. |
| 443 |
* @return {number} The smallest integer greater than or equal to {@code num}. |
| 444 |
*/ |
| 445 |
goog.math.safeCeil = function(num, opt_epsilon) { |
| 446 |
goog.asserts.assert(!goog.isDef(opt_epsilon) || opt_epsilon > 0); |
| 447 |
return Math.ceil(num - (opt_epsilon || 2e-15)); |
| 448 |
}; |