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
};
449

450