| 1 |
// Copyright 2009 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 Defines an Integer class for representing (potentially) |
| 17 |
* infinite length two's-complement integer values. |
| 18 |
* |
| 19 |
* For the specific case of 64-bit integers, use goog.math.Long, which is more |
| 20 |
* efficient. |
| 21 |
* |
| 22 |
*/ |
| 23 |
|
| 24 |
goog.provide('goog.math.Integer'); |
| 25 |
|
| 26 |
|
| 27 |
|
| 28 |
/** |
| 29 |
* Constructs a two's-complement integer an array containing bits of the |
| 30 |
* integer in 32-bit (signed) pieces, given in little-endian order (i.e., |
| 31 |
* lowest-order bits in the first piece), and the sign of -1 or 0. |
| 32 |
* |
| 33 |
* See the from* functions below for other convenient ways of constructing |
| 34 |
* Integers. |
| 35 |
* |
| 36 |
* The internal representation of an integer is an array of 32-bit signed |
| 37 |
* pieces, along with a sign (0 or -1) that indicates the contents of all the |
| 38 |
* other 32-bit pieces out to infinity. We use 32-bit pieces because these are |
| 39 |
* the size of integers on which Javascript performs bit-operations. For |
| 40 |
* operations like addition and multiplication, we split each number into 16-bit |
| 41 |
* pieces, which can easily be multiplied within Javascript's floating-point |
| 42 |
* representation without overflow or change in sign. |
| 43 |
* |
| 44 |
* @struct |
| 45 |
* @constructor |
| 46 |
* @param {Array<number>} bits Array containing the bits of the number. |
| 47 |
* @param {number} sign The sign of the number: -1 for negative and 0 positive. |
| 48 |
* @final |
| 49 |
*/ |
| 50 |
goog.math.Integer = function(bits, sign) { |
| 51 |
/** |
| 52 |
* @type {!Array<number>} |
| 53 |
* @private |
| 54 |
*/ |
| 55 |
this.bits_ = []; |
| 56 |
|
| 57 |
/** |
| 58 |
* @type {number} |
| 59 |
* @private |
| 60 |
*/ |
| 61 |
this.sign_ = sign; |
| 62 |
|
| 63 |
// Copy the 32-bit signed integer values passed in. We prune out those at the |
| 64 |
// top that equal the sign since they are redundant. |
| 65 |
var top = true; |
| 66 |
for (var i = bits.length - 1; i >= 0; i--) { |
| 67 |
var val = bits[i] | 0; |
| 68 |
if (!top || val != sign) { |
| 69 |
this.bits_[i] = val; |
| 70 |
top = false; |
| 71 |
} |
| 72 |
} |
| 73 |
}; |
| 74 |
|
| 75 |
|
| 76 |
// NOTE: Common constant values ZERO, ONE, NEG_ONE, etc. are defined below the |
| 77 |
// from* methods on which they depend. |
| 78 |
|
| 79 |
|
| 80 |
/** |
| 81 |
* A cache of the Integer representations of small integer values. |
| 82 |
* @type {!Object} |
| 83 |
* @private |
| 84 |
*/ |
| 85 |
goog.math.Integer.IntCache_ = {}; |
| 86 |
|
| 87 |
|
| 88 |
/** |
| 89 |
* Returns an Integer representing the given (32-bit) integer value. |
| 90 |
* @param {number} value A 32-bit integer value. |
| 91 |
* @return {!goog.math.Integer} The corresponding Integer value. |
| 92 |
*/ |
| 93 |
goog.math.Integer.fromInt = function(value) { |
| 94 |
if (-128 <= value && value < 128) { |
| 95 |
var cachedObj = goog.math.Integer.IntCache_[value]; |
| 96 |
if (cachedObj) { |
| 97 |
return cachedObj; |
| 98 |
} |
| 99 |
} |
| 100 |
|
| 101 |
var obj = new goog.math.Integer([value | 0], value < 0 ? -1 : 0); |
| 102 |
if (-128 <= value && value < 128) { |
| 103 |
goog.math.Integer.IntCache_[value] = obj; |
| 104 |
} |
| 105 |
return obj; |
| 106 |
}; |
| 107 |
|
| 108 |
|
| 109 |
/** |
| 110 |
* Returns an Integer representing the given value, provided that it is a finite |
| 111 |
* number. Otherwise, zero is returned. |
| 112 |
* @param {number} value The value in question. |
| 113 |
* @return {!goog.math.Integer} The corresponding Integer value. |
| 114 |
*/ |
| 115 |
goog.math.Integer.fromNumber = function(value) { |
| 116 |
if (isNaN(value) || !isFinite(value)) { |
| 117 |
return goog.math.Integer.ZERO; |
| 118 |
} else if (value < 0) { |
| 119 |
return goog.math.Integer.fromNumber(-value).negate(); |
| 120 |
} else { |
| 121 |
var bits = []; |
| 122 |
var pow = 1; |
| 123 |
for (var i = 0; value >= pow; i++) { |
| 124 |
bits[i] = (value / pow) | 0; |
| 125 |
pow *= goog.math.Integer.TWO_PWR_32_DBL_; |
| 126 |
} |
| 127 |
return new goog.math.Integer(bits, 0); |
| 128 |
} |
| 129 |
}; |
| 130 |
|
| 131 |
|
| 132 |
/** |
| 133 |
* Returns a Integer representing the value that comes by concatenating the |
| 134 |
* given entries, each is assumed to be 32 signed bits, given in little-endian |
| 135 |
* order (lowest order bits in the lowest index), and sign-extending the highest |
| 136 |
* order 32-bit value. |
| 137 |
* @param {Array<number>} bits The bits of the number, in 32-bit signed pieces, |
| 138 |
* in little-endian order. |
| 139 |
* @return {!goog.math.Integer} The corresponding Integer value. |
| 140 |
*/ |
| 141 |
goog.math.Integer.fromBits = function(bits) { |
| 142 |
var high = bits[bits.length - 1]; |
| 143 |
return new goog.math.Integer(bits, high & (1 << 31) ? -1 : 0); |
| 144 |
}; |
| 145 |
|
| 146 |
|
| 147 |
/** |
| 148 |
* Returns an Integer representation of the given string, written using the |
| 149 |
* given radix. |
| 150 |
* @param {string} str The textual representation of the Integer. |
| 151 |
* @param {number=} opt_radix The radix in which the text is written. |
| 152 |
* @return {!goog.math.Integer} The corresponding Integer value. |
| 153 |
*/ |
| 154 |
goog.math.Integer.fromString = function(str, opt_radix) { |
| 155 |
if (str.length == 0) { |
| 156 |
throw new Error('number format error: empty string'); |
| 157 |
} |
| 158 |
|
| 159 |
var radix = opt_radix || 10; |
| 160 |
if (radix < 2 || 36 < radix) { |
| 161 |
throw new Error('radix out of range: ' + radix); |
| 162 |
} |
| 163 |
|
| 164 |
if (str.charAt(0) == '-') { |
| 165 |
return goog.math.Integer.fromString(str.substring(1), radix).negate(); |
| 166 |
} else if (str.indexOf('-') >= 0) { |
| 167 |
throw new Error('number format error: interior "-" character'); |
| 168 |
} |
| 169 |
|
| 170 |
// Do several (8) digits each time through the loop, so as to |
| 171 |
// minimize the calls to the very expensive emulated div. |
| 172 |
var radixToPower = goog.math.Integer.fromNumber(Math.pow(radix, 8)); |
| 173 |
|
| 174 |
var result = goog.math.Integer.ZERO; |
| 175 |
for (var i = 0; i < str.length; i += 8) { |
| 176 |
var size = Math.min(8, str.length - i); |
| 177 |
var value = parseInt(str.substring(i, i + size), radix); |
| 178 |
if (size < 8) { |
| 179 |
var power = goog.math.Integer.fromNumber(Math.pow(radix, size)); |
| 180 |
result = result.multiply(power).add(goog.math.Integer.fromNumber(value)); |
| 181 |
} else { |
| 182 |
result = result.multiply(radixToPower); |
| 183 |
result = result.add(goog.math.Integer.fromNumber(value)); |
| 184 |
} |
| 185 |
} |
| 186 |
return result; |
| 187 |
}; |
| 188 |
|
| 189 |
|
| 190 |
/** |
| 191 |
* A number used repeatedly in calculations. This must appear before the first |
| 192 |
* call to the from* functions below. |
| 193 |
* @type {number} |
| 194 |
* @private |
| 195 |
*/ |
| 196 |
goog.math.Integer.TWO_PWR_32_DBL_ = (1 << 16) * (1 << 16); |
| 197 |
|
| 198 |
|
| 199 |
/** @type {!goog.math.Integer} */ |
| 200 |
goog.math.Integer.ZERO = goog.math.Integer.fromInt(0); |
| 201 |
|
| 202 |
|
| 203 |
/** @type {!goog.math.Integer} */ |
| 204 |
goog.math.Integer.ONE = goog.math.Integer.fromInt(1); |
| 205 |
|
| 206 |
|
| 207 |
/** |
| 208 |
* @type {!goog.math.Integer} |
| 209 |
* @private |
| 210 |
*/ |
| 211 |
goog.math.Integer.TWO_PWR_24_ = goog.math.Integer.fromInt(1 << 24); |
| 212 |
|
| 213 |
|
| 214 |
/** |
| 215 |
* Returns the value, assuming it is a 32-bit integer. |
| 216 |
* @return {number} The corresponding int value. |
| 217 |
*/ |
| 218 |
goog.math.Integer.prototype.toInt = function() { |
| 219 |
return this.bits_.length > 0 ? this.bits_[0] : this.sign_; |
| 220 |
}; |
| 221 |
|
| 222 |
|
| 223 |
/** @return {number} The closest floating-point representation to this value. */ |
| 224 |
goog.math.Integer.prototype.toNumber = function() { |
| 225 |
if (this.isNegative()) { |
| 226 |
return -this.negate().toNumber(); |
| 227 |
} else { |
| 228 |
var val = 0; |
| 229 |
var pow = 1; |
| 230 |
for (var i = 0; i < this.bits_.length; i++) { |
| 231 |
val += this.getBitsUnsigned(i) * pow; |
| 232 |
pow *= goog.math.Integer.TWO_PWR_32_DBL_; |
| 233 |
} |
| 234 |
return val; |
| 235 |
} |
| 236 |
}; |
| 237 |
|
| 238 |
|
| 239 |
/** |
| 240 |
* @param {number=} opt_radix The radix in which the text should be written. |
| 241 |
* @return {string} The textual representation of this value. |
| 242 |
* @override |
| 243 |
*/ |
| 244 |
goog.math.Integer.prototype.toString = function(opt_radix) { |
| 245 |
var radix = opt_radix || 10; |
| 246 |
if (radix < 2 || 36 < radix) { |
| 247 |
throw new Error('radix out of range: ' + radix); |
| 248 |
} |
| 249 |
|
| 250 |
if (this.isZero()) { |
| 251 |
return '0'; |
| 252 |
} else if (this.isNegative()) { |
| 253 |
return '-' + this.negate().toString(radix); |
| 254 |
} |
| 255 |
|
| 256 |
// Do several (6) digits each time through the loop, so as to |
| 257 |
// minimize the calls to the very expensive emulated div. |
| 258 |
var radixToPower = goog.math.Integer.fromNumber(Math.pow(radix, 6)); |
| 259 |
|
| 260 |
var rem = this; |
| 261 |
var result = ''; |
| 262 |
while (true) { |
| 263 |
var remDiv = rem.divide(radixToPower); |
| 264 |
// The right shifting fixes negative values in the case when |
| 265 |
// intval >= 2^31; for more details see |
| 266 |
// https://github.com/google/closure-library/pull/498 |
| 267 |
var intval = rem.subtract(remDiv.multiply(radixToPower)).toInt() >>> 0; |
| 268 |
var digits = intval.toString(radix); |
| 269 |
|
| 270 |
rem = remDiv; |
| 271 |
if (rem.isZero()) { |
| 272 |
return digits + result; |
| 273 |
} else { |
| 274 |
while (digits.length < 6) { |
| 275 |
digits = '0' + digits; |
| 276 |
} |
| 277 |
result = '' + digits + result; |
| 278 |
} |
| 279 |
} |
| 280 |
}; |
| 281 |
|
| 282 |
|
| 283 |
/** |
| 284 |
* Returns the index-th 32-bit (signed) piece of the Integer according to |
| 285 |
* little-endian order (i.e., index 0 contains the smallest bits). |
| 286 |
* @param {number} index The index in question. |
| 287 |
* @return {number} The requested 32-bits as a signed number. |
| 288 |
*/ |
| 289 |
goog.math.Integer.prototype.getBits = function(index) { |
| 290 |
if (index < 0) { |
| 291 |
return 0; // Allowing this simplifies bit shifting operations below... |
| 292 |
} else if (index < this.bits_.length) { |
| 293 |
return this.bits_[index]; |
| 294 |
} else { |
| 295 |
return this.sign_; |
| 296 |
} |
| 297 |
}; |
| 298 |
|
| 299 |
|
| 300 |
/** |
| 301 |
* Returns the index-th 32-bit piece as an unsigned number. |
| 302 |
* @param {number} index The index in question. |
| 303 |
* @return {number} The requested 32-bits as an unsigned number. |
| 304 |
*/ |
| 305 |
goog.math.Integer.prototype.getBitsUnsigned = function(index) { |
| 306 |
var val = this.getBits(index); |
| 307 |
return val >= 0 ? val : goog.math.Integer.TWO_PWR_32_DBL_ + val; |
| 308 |
}; |
| 309 |
|
| 310 |
|
| 311 |
/** @return {number} The sign bit of this number, -1 or 0. */ |
| 312 |
goog.math.Integer.prototype.getSign = function() { |
| 313 |
return this.sign_; |
| 314 |
}; |
| 315 |
|
| 316 |
|
| 317 |
/** @return {boolean} Whether this value is zero. */ |
| 318 |
goog.math.Integer.prototype.isZero = function() { |
| 319 |
if (this.sign_ != 0) { |
| 320 |
return false; |
| 321 |
} |
| 322 |
for (var i = 0; i < this.bits_.length; i++) { |
| 323 |
if (this.bits_[i] != 0) { |
| 324 |
return false; |
| 325 |
} |
| 326 |
} |
| 327 |
return true; |
| 328 |
}; |
| 329 |
|
| 330 |
|
| 331 |
/** @return {boolean} Whether this value is negative. */ |
| 332 |
goog.math.Integer.prototype.isNegative = function() { |
| 333 |
return this.sign_ == -1; |
| 334 |
}; |
| 335 |
|
| 336 |
|
| 337 |
/** @return {boolean} Whether this value is odd. */ |
| 338 |
goog.math.Integer.prototype.isOdd = function() { |
| 339 |
return (this.bits_.length == 0) && (this.sign_ == -1) || |
| 340 |
(this.bits_.length > 0) && ((this.bits_[0] & 1) != 0); |
| 341 |
}; |
| 342 |
|
| 343 |
|
| 344 |
/** |
| 345 |
* @param {goog.math.Integer} other Integer to compare against. |
| 346 |
* @return {boolean} Whether this Integer equals the other. |
| 347 |
*/ |
| 348 |
goog.math.Integer.prototype.equals = function(other) { |
| 349 |
if (this.sign_ != other.sign_) { |
| 350 |
return false; |
| 351 |
} |
| 352 |
var len = Math.max(this.bits_.length, other.bits_.length); |
| 353 |
for (var i = 0; i < len; i++) { |
| 354 |
if (this.getBits(i) != other.getBits(i)) { |
| 355 |
return false; |
| 356 |
} |
| 357 |
} |
| 358 |
return true; |
| 359 |
}; |
| 360 |
|
| 361 |
|
| 362 |
/** |
| 363 |
* @param {goog.math.Integer} other Integer to compare against. |
| 364 |
* @return {boolean} Whether this Integer does not equal the other. |
| 365 |
*/ |
| 366 |
goog.math.Integer.prototype.notEquals = function(other) { |
| 367 |
return !this.equals(other); |
| 368 |
}; |
| 369 |
|
| 370 |
|
| 371 |
/** |
| 372 |
* @param {goog.math.Integer} other Integer to compare against. |
| 373 |
* @return {boolean} Whether this Integer is greater than the other. |
| 374 |
*/ |
| 375 |
goog.math.Integer.prototype.greaterThan = function(other) { |
| 376 |
return this.compare(other) > 0; |
| 377 |
}; |
| 378 |
|
| 379 |
|
| 380 |
/** |
| 381 |
* @param {goog.math.Integer} other Integer to compare against. |
| 382 |
* @return {boolean} Whether this Integer is greater than or equal to the other. |
| 383 |
*/ |
| 384 |
goog.math.Integer.prototype.greaterThanOrEqual = function(other) { |
| 385 |
return this.compare(other) >= 0; |
| 386 |
}; |
| 387 |
|
| 388 |
|
| 389 |
/** |
| 390 |
* @param {goog.math.Integer} other Integer to compare against. |
| 391 |
* @return {boolean} Whether this Integer is less than the other. |
| 392 |
*/ |
| 393 |
goog.math.Integer.prototype.lessThan = function(other) { |
| 394 |
return this.compare(other) < 0; |
| 395 |
}; |
| 396 |
|
| 397 |
|
| 398 |
/** |
| 399 |
* @param {goog.math.Integer} other Integer to compare against. |
| 400 |
* @return {boolean} Whether this Integer is less than or equal to the other. |
| 401 |
*/ |
| 402 |
goog.math.Integer.prototype.lessThanOrEqual = function(other) { |
| 403 |
return this.compare(other) <= 0; |
| 404 |
}; |
| 405 |
|
| 406 |
|
| 407 |
/** |
| 408 |
* Compares this Integer with the given one. |
| 409 |
* @param {goog.math.Integer} other Integer to compare against. |
| 410 |
* @return {number} 0 if they are the same, 1 if the this is greater, and -1 |
| 411 |
* if the given one is greater. |
| 412 |
*/ |
| 413 |
goog.math.Integer.prototype.compare = function(other) { |
| 414 |
var diff = this.subtract(other); |
| 415 |
if (diff.isNegative()) { |
| 416 |
return -1; |
| 417 |
} else if (diff.isZero()) { |
| 418 |
return 0; |
| 419 |
} else { |
| 420 |
return +1; |
| 421 |
} |
| 422 |
}; |
| 423 |
|
| 424 |
|
| 425 |
/** |
| 426 |
* Returns an integer with only the first numBits bits of this value, sign |
| 427 |
* extended from the final bit. |
| 428 |
* @param {number} numBits The number of bits by which to shift. |
| 429 |
* @return {!goog.math.Integer} The shorted integer value. |
| 430 |
*/ |
| 431 |
goog.math.Integer.prototype.shorten = function(numBits) { |
| 432 |
var arr_index = (numBits - 1) >> 5; |
| 433 |
var bit_index = (numBits - 1) % 32; |
| 434 |
var bits = []; |
| 435 |
for (var i = 0; i < arr_index; i++) { |
| 436 |
bits[i] = this.getBits(i); |
| 437 |
} |
| 438 |
var sigBits = bit_index == 31 ? 0xFFFFFFFF : (1 << (bit_index + 1)) - 1; |
| 439 |
var val = this.getBits(arr_index) & sigBits; |
| 440 |
if (val & (1 << bit_index)) { |
| 441 |
val |= 0xFFFFFFFF - sigBits; |
| 442 |
bits[arr_index] = val; |
| 443 |
return new goog.math.Integer(bits, -1); |
| 444 |
} else { |
| 445 |
bits[arr_index] = val; |
| 446 |
return new goog.math.Integer(bits, 0); |
| 447 |
} |
| 448 |
}; |
| 449 |
|
| 450 |
|
| 451 |
/** @return {!goog.math.Integer} The negation of this value. */ |
| 452 |
goog.math.Integer.prototype.negate = function() { |
| 453 |
return this.not().add(goog.math.Integer.ONE); |
| 454 |
}; |
| 455 |
|
| 456 |
|
| 457 |
/** |
| 458 |
* Returns the sum of this and the given Integer. |
| 459 |
* @param {goog.math.Integer} other The Integer to add to this. |
| 460 |
* @return {!goog.math.Integer} The Integer result. |
| 461 |
*/ |
| 462 |
goog.math.Integer.prototype.add = function(other) { |
| 463 |
var len = Math.max(this.bits_.length, other.bits_.length); |
| 464 |
var arr = []; |
| 465 |
var carry = 0; |
| 466 |
|
| 467 |
for (var i = 0; i <= len; i++) { |
| 468 |
var a1 = this.getBits(i) >>> 16; |
| 469 |
var a0 = this.getBits(i) & 0xFFFF; |
| 470 |
|
| 471 |
var b1 = other.getBits(i) >>> 16; |
| 472 |
var b0 = other.getBits(i) & 0xFFFF; |
| 473 |
|
| 474 |
var c0 = carry + a0 + b0; |
| 475 |
var c1 = (c0 >>> 16) + a1 + b1; |
| 476 |
carry = c1 >>> 16; |
| 477 |
c0 &= 0xFFFF; |
| 478 |
c1 &= 0xFFFF; |
| 479 |
arr[i] = (c1 << 16) | c0; |
| 480 |
} |
| 481 |
return goog.math.Integer.fromBits(arr); |
| 482 |
}; |
| 483 |
|
| 484 |
|
| 485 |
/** |
| 486 |
* Returns the difference of this and the given Integer. |
| 487 |
* @param {goog.math.Integer} other The Integer to subtract from this. |
| 488 |
* @return {!goog.math.Integer} The Integer result. |
| 489 |
*/ |
| 490 |
goog.math.Integer.prototype.subtract = function(other) { |
| 491 |
return this.add(other.negate()); |
| 492 |
}; |
| 493 |
|
| 494 |
|
| 495 |
/** |
| 496 |
* Returns the product of this and the given Integer. |
| 497 |
* @param {goog.math.Integer} other The Integer to multiply against this. |
| 498 |
* @return {!goog.math.Integer} The product of this and the other. |
| 499 |
*/ |
| 500 |
goog.math.Integer.prototype.multiply = function(other) { |
| 501 |
if (this.isZero()) { |
| 502 |
return goog.math.Integer.ZERO; |
| 503 |
} else if (other.isZero()) { |
| 504 |
return goog.math.Integer.ZERO; |
| 505 |
} |
| 506 |
|
| 507 |
if (this.isNegative()) { |
| 508 |
if (other.isNegative()) { |
| 509 |
return this.negate().multiply(other.negate()); |
| 510 |
} else { |
| 511 |
return this.negate().multiply(other).negate(); |
| 512 |
} |
| 513 |
} else if (other.isNegative()) { |
| 514 |
return this.multiply(other.negate()).negate(); |
| 515 |
} |
| 516 |
|
| 517 |
// If both numbers are small, use float multiplication |
| 518 |
if (this.lessThan(goog.math.Integer.TWO_PWR_24_) && |
| 519 |
other.lessThan(goog.math.Integer.TWO_PWR_24_)) { |
| 520 |
return goog.math.Integer.fromNumber(this.toNumber() * other.toNumber()); |
| 521 |
} |
| 522 |
|
| 523 |
// Fill in an array of 16-bit products. |
| 524 |
var len = this.bits_.length + other.bits_.length; |
| 525 |
var arr = []; |
| 526 |
for (var i = 0; i < 2 * len; i++) { |
| 527 |
arr[i] = 0; |
| 528 |
} |
| 529 |
for (var i = 0; i < this.bits_.length; i++) { |
| 530 |
for (var j = 0; j < other.bits_.length; j++) { |
| 531 |
var a1 = this.getBits(i) >>> 16; |
| 532 |
var a0 = this.getBits(i) & 0xFFFF; |
| 533 |
|
| 534 |
var b1 = other.getBits(j) >>> 16; |
| 535 |
var b0 = other.getBits(j) & 0xFFFF; |
| 536 |
|
| 537 |
arr[2 * i + 2 * j] += a0 * b0; |
| 538 |
goog.math.Integer.carry16_(arr, 2 * i + 2 * j); |
| 539 |
arr[2 * i + 2 * j + 1] += a1 * b0; |
| 540 |
goog.math.Integer.carry16_(arr, 2 * i + 2 * j + 1); |
| 541 |
arr[2 * i + 2 * j + 1] += a0 * b1; |
| 542 |
goog.math.Integer.carry16_(arr, 2 * i + 2 * j + 1); |
| 543 |
arr[2 * i + 2 * j + 2] += a1 * b1; |
| 544 |
goog.math.Integer.carry16_(arr, 2 * i + 2 * j + 2); |
| 545 |
} |
| 546 |
} |
| 547 |
|
| 548 |
// Combine the 16-bit values into 32-bit values. |
| 549 |
for (var i = 0; i < len; i++) { |
| 550 |
arr[i] = (arr[2 * i + 1] << 16) | arr[2 * i]; |
| 551 |
} |
| 552 |
for (var i = len; i < 2 * len; i++) { |
| 553 |
arr[i] = 0; |
| 554 |
} |
| 555 |
return new goog.math.Integer(arr, 0); |
| 556 |
}; |
| 557 |
|
| 558 |
|
| 559 |
/** |
| 560 |
* Carries any overflow from the given index into later entries. |
| 561 |
* @param {Array<number>} bits Array of 16-bit values in little-endian order. |
| 562 |
* @param {number} index The index in question. |
| 563 |
* @private |
| 564 |
*/ |
| 565 |
goog.math.Integer.carry16_ = function(bits, index) { |
| 566 |
while ((bits[index] & 0xFFFF) != bits[index]) { |
| 567 |
bits[index + 1] += bits[index] >>> 16; |
| 568 |
bits[index] &= 0xFFFF; |
| 569 |
index++; |
| 570 |
} |
| 571 |
}; |
| 572 |
|
| 573 |
|
| 574 |
/** |
| 575 |
* Returns "this" Integer divided by the given one. Both "this" and the given |
| 576 |
* Integer MUST be positive. |
| 577 |
* |
| 578 |
* This method is only needed for very large numbers (>10^308), |
| 579 |
* for which the original division algorithm gets into an infinite |
| 580 |
* loop (see https://github.com/google/closure-library/issues/500). |
| 581 |
* |
| 582 |
* The algorithm has some possible performance enhancements (or |
| 583 |
* could be rewritten entirely), it's just an initial solution for |
| 584 |
* the issue linked above. |
| 585 |
* |
| 586 |
* @param {!goog.math.Integer} other The Integer to divide "this" by. |
| 587 |
* @return {!goog.math.Integer} "this" value divided by the given one. |
| 588 |
* @private |
| 589 |
*/ |
| 590 |
goog.math.Integer.prototype.slowDivide_ = function(other) { |
| 591 |
if (this.isNegative() || other.isNegative()) { |
| 592 |
throw new Error('slowDivide_ only works with positive integers.'); |
| 593 |
} |
| 594 |
|
| 595 |
var twoPower = goog.math.Integer.ONE; |
| 596 |
var multiple = other; |
| 597 |
|
| 598 |
// First we have to figure out what the highest bit of the result |
| 599 |
// is, so we increase "twoPower" and "multiple" until "multiple" |
| 600 |
// exceeds "this". |
| 601 |
while (multiple.lessThanOrEqual(this)) { |
| 602 |
twoPower = twoPower.shiftLeft(1); |
| 603 |
multiple = multiple.shiftLeft(1); |
| 604 |
} |
| 605 |
|
| 606 |
// Rewind by one power of two, giving us the highest bit of the |
| 607 |
// result. |
| 608 |
var res = twoPower.shiftRight(1); |
| 609 |
var total = multiple.shiftRight(1); |
| 610 |
|
| 611 |
// Now we starting decreasing "multiple" and "twoPower" to find the |
| 612 |
// rest of the bits of the result. |
| 613 |
var total2; |
| 614 |
multiple = multiple.shiftRight(2); |
| 615 |
twoPower = twoPower.shiftRight(2); |
| 616 |
while (!multiple.isZero()) { |
| 617 |
// whenever we can add "multiple" to the total and not exceed |
| 618 |
// "this", that means we've found a 1 bit. Else we've found a 0 |
| 619 |
// and don't need to add to the result. |
| 620 |
total2 = total.add(multiple); |
| 621 |
if (total2.lessThanOrEqual(this)) { |
| 622 |
res = res.add(twoPower); |
| 623 |
total = total2; |
| 624 |
} |
| 625 |
multiple = multiple.shiftRight(1); |
| 626 |
twoPower = twoPower.shiftRight(1); |
| 627 |
} |
| 628 |
return res; |
| 629 |
}; |
| 630 |
|
| 631 |
|
| 632 |
/** |
| 633 |
* Returns this Integer divided by the given one. |
| 634 |
* @param {!goog.math.Integer} other The Integer to divide this by. |
| 635 |
* @return {!goog.math.Integer} This value divided by the given one. |
| 636 |
*/ |
| 637 |
goog.math.Integer.prototype.divide = function(other) { |
| 638 |
if (other.isZero()) { |
| 639 |
throw new Error('division by zero'); |
| 640 |
} else if (this.isZero()) { |
| 641 |
return goog.math.Integer.ZERO; |
| 642 |
} |
| 643 |
|
| 644 |
if (this.isNegative()) { |
| 645 |
if (other.isNegative()) { |
| 646 |
return this.negate().divide(other.negate()); |
| 647 |
} else { |
| 648 |
return this.negate().divide(other).negate(); |
| 649 |
} |
| 650 |
} else if (other.isNegative()) { |
| 651 |
return this.divide(other.negate()).negate(); |
| 652 |
} |
| 653 |
|
| 654 |
// Have to degrade to slowDivide for Very Large Numbers, because |
| 655 |
// they're out of range for the floating-point approximation |
| 656 |
// technique used below. |
| 657 |
if (this.bits_.length > 30) { |
| 658 |
return this.slowDivide_(other); |
| 659 |
} |
| 660 |
|
| 661 |
// Repeat the following until the remainder is less than other: find a |
| 662 |
// floating-point that approximates remainder / other *from below*, add this |
| 663 |
// into the result, and subtract it from the remainder. It is critical that |
| 664 |
// the approximate value is less than or equal to the real value so that the |
| 665 |
// remainder never becomes negative. |
| 666 |
var res = goog.math.Integer.ZERO; |
| 667 |
var rem = this; |
| 668 |
while (rem.greaterThanOrEqual(other)) { |
| 669 |
// Approximate the result of division. This may be a little greater or |
| 670 |
// smaller than the actual value. |
| 671 |
var approx = Math.max(1, Math.floor(rem.toNumber() / other.toNumber())); |
| 672 |
|
| 673 |
// We will tweak the approximate result by changing it in the 48-th digit or |
| 674 |
// the smallest non-fractional digit, whichever is larger. |
| 675 |
var log2 = Math.ceil(Math.log(approx) / Math.LN2); |
| 676 |
var delta = (log2 <= 48) ? 1 : Math.pow(2, log2 - 48); |
| 677 |
|
| 678 |
// Decrease the approximation until it is smaller than the remainder. Note |
| 679 |
// that if it is too large, the product overflows and is negative. |
| 680 |
var approxRes = goog.math.Integer.fromNumber(approx); |
| 681 |
var approxRem = approxRes.multiply(other); |
| 682 |
while (approxRem.isNegative() || approxRem.greaterThan(rem)) { |
| 683 |
approx -= delta; |
| 684 |
approxRes = goog.math.Integer.fromNumber(approx); |
| 685 |
approxRem = approxRes.multiply(other); |
| 686 |
} |
| 687 |
|
| 688 |
// We know the answer can't be zero... and actually, zero would cause |
| 689 |
// infinite recursion since we would make no progress. |
| 690 |
if (approxRes.isZero()) { |
| 691 |
approxRes = goog.math.Integer.ONE; |
| 692 |
} |
| 693 |
|
| 694 |
res = res.add(approxRes); |
| 695 |
rem = rem.subtract(approxRem); |
| 696 |
} |
| 697 |
return res; |
| 698 |
}; |
| 699 |
|
| 700 |
|
| 701 |
/** |
| 702 |
* Returns this Integer modulo the given one. |
| 703 |
* @param {!goog.math.Integer} other The Integer by which to mod. |
| 704 |
* @return {!goog.math.Integer} This value modulo the given one. |
| 705 |
*/ |
| 706 |
goog.math.Integer.prototype.modulo = function(other) { |
| 707 |
return this.subtract(this.divide(other).multiply(other)); |
| 708 |
}; |
| 709 |
|
| 710 |
|
| 711 |
/** @return {!goog.math.Integer} The bitwise-NOT of this value. */ |
| 712 |
goog.math.Integer.prototype.not = function() { |
| 713 |
var len = this.bits_.length; |
| 714 |
var arr = []; |
| 715 |
for (var i = 0; i < len; i++) { |
| 716 |
arr[i] = ~this.bits_[i]; |
| 717 |
} |
| 718 |
return new goog.math.Integer(arr, ~this.sign_); |
| 719 |
}; |
| 720 |
|
| 721 |
|
| 722 |
/** |
| 723 |
* Returns the bitwise-AND of this Integer and the given one. |
| 724 |
* @param {goog.math.Integer} other The Integer to AND with this. |
| 725 |
* @return {!goog.math.Integer} The bitwise-AND of this and the other. |
| 726 |
*/ |
| 727 |
goog.math.Integer.prototype.and = function(other) { |
| 728 |
var len = Math.max(this.bits_.length, other.bits_.length); |
| 729 |
var arr = []; |
| 730 |
for (var i = 0; i < len; i++) { |
| 731 |
arr[i] = this.getBits(i) & other.getBits(i); |
| 732 |
} |
| 733 |
return new goog.math.Integer(arr, this.sign_ & other.sign_); |
| 734 |
}; |
| 735 |
|
| 736 |
|
| 737 |
/** |
| 738 |
* Returns the bitwise-OR of this Integer and the given one. |
| 739 |
* @param {goog.math.Integer} other The Integer to OR with this. |
| 740 |
* @return {!goog.math.Integer} The bitwise-OR of this and the other. |
| 741 |
*/ |
| 742 |
goog.math.Integer.prototype.or = function(other) { |
| 743 |
var len = Math.max(this.bits_.length, other.bits_.length); |
| 744 |
var arr = []; |
| 745 |
for (var i = 0; i < len; i++) { |
| 746 |
arr[i] = this.getBits(i) | other.getBits(i); |
| 747 |
} |
| 748 |
return new goog.math.Integer(arr, this.sign_ | other.sign_); |
| 749 |
}; |
| 750 |
|
| 751 |
|
| 752 |
/** |
| 753 |
* Returns the bitwise-XOR of this Integer and the given one. |
| 754 |
* @param {goog.math.Integer} other The Integer to XOR with this. |
| 755 |
* @return {!goog.math.Integer} The bitwise-XOR of this and the other. |
| 756 |
*/ |
| 757 |
goog.math.Integer.prototype.xor = function(other) { |
| 758 |
var len = Math.max(this.bits_.length, other.bits_.length); |
| 759 |
var arr = []; |
| 760 |
for (var i = 0; i < len; i++) { |
| 761 |
arr[i] = this.getBits(i) ^ other.getBits(i); |
| 762 |
} |
| 763 |
return new goog.math.Integer(arr, this.sign_ ^ other.sign_); |
| 764 |
}; |
| 765 |
|
| 766 |
|
| 767 |
/** |
| 768 |
* Returns this value with bits shifted to the left by the given amount. |
| 769 |
* @param {number} numBits The number of bits by which to shift. |
| 770 |
* @return {!goog.math.Integer} This shifted to the left by the given amount. |
| 771 |
*/ |
| 772 |
goog.math.Integer.prototype.shiftLeft = function(numBits) { |
| 773 |
var arr_delta = numBits >> 5; |
| 774 |
var bit_delta = numBits % 32; |
| 775 |
var len = this.bits_.length + arr_delta + (bit_delta > 0 ? 1 : 0); |
| 776 |
var arr = []; |
| 777 |
for (var i = 0; i < len; i++) { |
| 778 |
if (bit_delta > 0) { |
| 779 |
arr[i] = (this.getBits(i - arr_delta) << bit_delta) | |
| 780 |
(this.getBits(i - arr_delta - 1) >>> (32 - bit_delta)); |
| 781 |
} else { |
| 782 |
arr[i] = this.getBits(i - arr_delta); |
| 783 |
} |
| 784 |
} |
| 785 |
return new goog.math.Integer(arr, this.sign_); |
| 786 |
}; |
| 787 |
|
| 788 |
|
| 789 |
/** |
| 790 |
* Returns this value with bits shifted to the right by the given amount. |
| 791 |
* @param {number} numBits The number of bits by which to shift. |
| 792 |
* @return {!goog.math.Integer} This shifted to the right by the given amount. |
| 793 |
*/ |
| 794 |
goog.math.Integer.prototype.shiftRight = function(numBits) { |
| 795 |
var arr_delta = numBits >> 5; |
| 796 |
var bit_delta = numBits % 32; |
| 797 |
var len = this.bits_.length - arr_delta; |
| 798 |
var arr = []; |
| 799 |
for (var i = 0; i < len; i++) { |
| 800 |
if (bit_delta > 0) { |
| 801 |
arr[i] = (this.getBits(i + arr_delta) >>> bit_delta) | |
| 802 |
(this.getBits(i + arr_delta + 1) << (32 - bit_delta)); |
| 803 |
} else { |
| 804 |
arr[i] = this.getBits(i + arr_delta); |
| 805 |
} |
| 806 |
} |
| 807 |
return new goog.math.Integer(arr, this.sign_); |
| 808 |
}; |