goog.math.long.js 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807
  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. * @fileoverview Defines a Long class for representing a 64-bit two's-complement
  16. * integer value, which faithfully simulates the behavior of a Java "long". This
  17. * implementation is derived from LongLib in GWT.
  18. *
  19. */
  20. // goog.provide('goog.math.Long');
  21. var goog = {}; goog.math = {};
  22. /**
  23. * Constructs a 64-bit two's-complement integer, given its low and high 32-bit
  24. * values as *signed* integers. See the from* functions below for more
  25. * convenient ways of constructing Longs.
  26. *
  27. * The internal representation of a long is the two given signed, 32-bit values.
  28. * We use 32-bit pieces because these are the size of integers on which
  29. * Javascript performs bit-operations. For operations like addition and
  30. * multiplication, we split each number into 16-bit pieces, which can easily be
  31. * multiplied within Javascript's floating-point representation without overflow
  32. * or change in sign.
  33. *
  34. * In the algorithms below, we frequently reduce the negative case to the
  35. * positive case by negating the input(s) and then post-processing the result.
  36. * Note that we must ALWAYS check specially whether those values are MIN_VALUE
  37. * (-2^63) because -MIN_VALUE == MIN_VALUE (since 2^63 cannot be represented as
  38. * a positive number, it overflows back into a negative). Not handling this
  39. * case would often result in infinite recursion.
  40. *
  41. * @param {number} low The low (signed) 32 bits of the long.
  42. * @param {number} high The high (signed) 32 bits of the long.
  43. * @constructor
  44. * @final
  45. */
  46. goog.math.Long = function(low, high) {
  47. /**
  48. * @type {number}
  49. * @private
  50. */
  51. this.low_ = low | 0; // force into 32 signed bits.
  52. /**
  53. * @type {number}
  54. * @private
  55. */
  56. this.high_ = high | 0; // force into 32 signed bits.
  57. };
  58. // NOTE: Common constant values ZERO, ONE, NEG_ONE, etc. are defined below the
  59. // from* methods on which they depend.
  60. /**
  61. * A cache of the Long representations of small integer values.
  62. * @type {!Object}
  63. * @private
  64. */
  65. goog.math.Long.IntCache_ = {};
  66. /**
  67. * Returns a Long representing the given (32-bit) integer value.
  68. * @param {number} value The 32-bit integer in question.
  69. * @return {!goog.math.Long} The corresponding Long value.
  70. */
  71. goog.math.Long.fromInt = function(value) {
  72. if (-128 <= value && value < 128) {
  73. var cachedObj = goog.math.Long.IntCache_[value];
  74. if (cachedObj) {
  75. return cachedObj;
  76. }
  77. }
  78. var obj = new goog.math.Long(value | 0, value < 0 ? -1 : 0);
  79. if (-128 <= value && value < 128) {
  80. goog.math.Long.IntCache_[value] = obj;
  81. }
  82. return obj;
  83. };
  84. /**
  85. * Returns a Long representing the given value, provided that it is a finite
  86. * number. Otherwise, zero is returned.
  87. * @param {number} value The number in question.
  88. * @return {!goog.math.Long} The corresponding Long value.
  89. */
  90. goog.math.Long.fromNumber = function(value) {
  91. if (isNaN(value) || !isFinite(value)) {
  92. return goog.math.Long.ZERO;
  93. } else if (value <= -goog.math.Long.TWO_PWR_63_DBL_) {
  94. return goog.math.Long.MIN_VALUE;
  95. } else if (value + 1 >= goog.math.Long.TWO_PWR_63_DBL_) {
  96. return goog.math.Long.MAX_VALUE;
  97. } else if (value < 0) {
  98. return goog.math.Long.fromNumber(-value).negate();
  99. } else {
  100. return new goog.math.Long(
  101. (value % goog.math.Long.TWO_PWR_32_DBL_) | 0,
  102. (value / goog.math.Long.TWO_PWR_32_DBL_) | 0);
  103. }
  104. };
  105. /**
  106. * Returns a Long representing the 64-bit integer that comes by concatenating
  107. * the given high and low bits. Each is assumed to use 32 bits.
  108. * @param {number} lowBits The low 32-bits.
  109. * @param {number} highBits The high 32-bits.
  110. * @return {!goog.math.Long} The corresponding Long value.
  111. */
  112. goog.math.Long.fromBits = function(lowBits, highBits) {
  113. return new goog.math.Long(lowBits, highBits);
  114. };
  115. /**
  116. * Returns a Long representation of the given string, written using the given
  117. * radix.
  118. * @param {string} str The textual representation of the Long.
  119. * @param {number=} opt_radix The radix in which the text is written.
  120. * @return {!goog.math.Long} The corresponding Long value.
  121. */
  122. goog.math.Long.fromString = function(str, opt_radix) {
  123. if (str.length == 0) {
  124. throw Error('number format error: empty string');
  125. }
  126. var radix = opt_radix || 10;
  127. if (radix < 2 || 36 < radix) {
  128. throw Error('radix out of range: ' + radix);
  129. }
  130. if (str.charAt(0) == '-') {
  131. return goog.math.Long.fromString(str.substring(1), radix).negate();
  132. } else if (str.indexOf('-') >= 0) {
  133. throw Error('number format error: interior "-" character: ' + str);
  134. }
  135. // Do several (8) digits each time through the loop, so as to
  136. // minimize the calls to the very expensive emulated div.
  137. var radixToPower = goog.math.Long.fromNumber(Math.pow(radix, 8));
  138. var result = goog.math.Long.ZERO;
  139. for (var i = 0; i < str.length; i += 8) {
  140. var size = Math.min(8, str.length - i);
  141. var value = parseInt(str.substring(i, i + size), radix);
  142. if (size < 8) {
  143. var power = goog.math.Long.fromNumber(Math.pow(radix, size));
  144. result = result.multiply(power).add(goog.math.Long.fromNumber(value));
  145. } else {
  146. result = result.multiply(radixToPower);
  147. result = result.add(goog.math.Long.fromNumber(value));
  148. }
  149. }
  150. return result;
  151. };
  152. // NOTE: the compiler should inline these constant values below and then remove
  153. // these variables, so there should be no runtime penalty for these.
  154. /**
  155. * Number used repeated below in calculations. This must appear before the
  156. * first call to any from* function below.
  157. * @type {number}
  158. * @private
  159. */
  160. goog.math.Long.TWO_PWR_16_DBL_ = 1 << 16;
  161. /**
  162. * @type {number}
  163. * @private
  164. */
  165. goog.math.Long.TWO_PWR_24_DBL_ = 1 << 24;
  166. /**
  167. * @type {number}
  168. * @private
  169. */
  170. goog.math.Long.TWO_PWR_32_DBL_ =
  171. goog.math.Long.TWO_PWR_16_DBL_ * goog.math.Long.TWO_PWR_16_DBL_;
  172. /**
  173. * @type {number}
  174. * @private
  175. */
  176. goog.math.Long.TWO_PWR_31_DBL_ =
  177. goog.math.Long.TWO_PWR_32_DBL_ / 2;
  178. /**
  179. * @type {number}
  180. * @private
  181. */
  182. goog.math.Long.TWO_PWR_48_DBL_ =
  183. goog.math.Long.TWO_PWR_32_DBL_ * goog.math.Long.TWO_PWR_16_DBL_;
  184. /**
  185. * @type {number}
  186. * @private
  187. */
  188. goog.math.Long.TWO_PWR_64_DBL_ =
  189. goog.math.Long.TWO_PWR_32_DBL_ * goog.math.Long.TWO_PWR_32_DBL_;
  190. /**
  191. * @type {number}
  192. * @private
  193. */
  194. goog.math.Long.TWO_PWR_63_DBL_ =
  195. goog.math.Long.TWO_PWR_64_DBL_ / 2;
  196. /** @type {!goog.math.Long} */
  197. goog.math.Long.ZERO = goog.math.Long.fromInt(0);
  198. /** @type {!goog.math.Long} */
  199. goog.math.Long.ONE = goog.math.Long.fromInt(1);
  200. /** @type {!goog.math.Long} */
  201. goog.math.Long.NEG_ONE = goog.math.Long.fromInt(-1);
  202. /** @type {!goog.math.Long} */
  203. goog.math.Long.MAX_VALUE =
  204. goog.math.Long.fromBits(0xFFFFFFFF | 0, 0x7FFFFFFF | 0);
  205. /** @type {!goog.math.Long} */
  206. goog.math.Long.MIN_VALUE = goog.math.Long.fromBits(0, 0x80000000 | 0);
  207. /**
  208. * @type {!goog.math.Long}
  209. * @private
  210. */
  211. goog.math.Long.TWO_PWR_24_ = goog.math.Long.fromInt(1 << 24);
  212. /** @return {number} The value, assuming it is a 32-bit integer. */
  213. goog.math.Long.prototype.toInt = function() {
  214. return this.low_;
  215. };
  216. /** @return {number} The closest floating-point representation to this value. */
  217. goog.math.Long.prototype.toNumber = function() {
  218. return this.high_ * goog.math.Long.TWO_PWR_32_DBL_ +
  219. this.getLowBitsUnsigned();
  220. };
  221. /**
  222. * @param {number=} opt_radix The radix in which the text should be written.
  223. * @return {string} The textual representation of this value.
  224. * @override
  225. */
  226. goog.math.Long.prototype.toString = function(opt_radix) {
  227. var radix = opt_radix || 10;
  228. if (radix < 2 || 36 < radix) {
  229. throw Error('radix out of range: ' + radix);
  230. }
  231. if (this.isZero()) {
  232. return '0';
  233. }
  234. if (this.isNegative()) {
  235. if (this.equals(goog.math.Long.MIN_VALUE)) {
  236. // We need to change the Long value before it can be negated, so we remove
  237. // the bottom-most digit in this base and then recurse to do the rest.
  238. var radixLong = goog.math.Long.fromNumber(radix);
  239. var div = this.div(radixLong);
  240. var rem = div.multiply(radixLong).subtract(this);
  241. return div.toString(radix) + rem.toInt().toString(radix);
  242. } else {
  243. return '-' + this.negate().toString(radix);
  244. }
  245. }
  246. // Do several (6) digits each time through the loop, so as to
  247. // minimize the calls to the very expensive emulated div.
  248. var radixToPower = goog.math.Long.fromNumber(Math.pow(radix, 6));
  249. var rem = this;
  250. var result = '';
  251. while (true) {
  252. var remDiv = rem.div(radixToPower);
  253. var intval = rem.subtract(remDiv.multiply(radixToPower)).toInt() >>> 0; // wraps around for base 36 (dcode)
  254. console.log(intval);
  255. var digits = intval.toString(radix);
  256. rem = remDiv;
  257. if (rem.isZero()) {
  258. return digits + result;
  259. } else {
  260. while (digits.length < 6) {
  261. digits = '0' + digits;
  262. }
  263. result = '' + digits + result;
  264. }
  265. }
  266. };
  267. /** @return {number} The high 32-bits as a signed value. */
  268. goog.math.Long.prototype.getHighBits = function() {
  269. return this.high_;
  270. };
  271. /** @return {number} The low 32-bits as a signed value. */
  272. goog.math.Long.prototype.getLowBits = function() {
  273. return this.low_;
  274. };
  275. /** @return {number} The low 32-bits as an unsigned value. */
  276. goog.math.Long.prototype.getLowBitsUnsigned = function() {
  277. return (this.low_ >= 0) ?
  278. this.low_ : goog.math.Long.TWO_PWR_32_DBL_ + this.low_;
  279. };
  280. /**
  281. * @return {number} Returns the number of bits needed to represent the absolute
  282. * value of this Long.
  283. */
  284. goog.math.Long.prototype.getNumBitsAbs = function() {
  285. if (this.isNegative()) {
  286. if (this.equals(goog.math.Long.MIN_VALUE)) {
  287. return 64;
  288. } else {
  289. return this.negate().getNumBitsAbs();
  290. }
  291. } else {
  292. var val = this.high_ != 0 ? this.high_ : this.low_;
  293. for (var bit = 31; bit > 0; bit--) {
  294. if ((val & (1 << bit)) != 0) {
  295. break;
  296. }
  297. }
  298. return this.high_ != 0 ? bit + 33 : bit + 1;
  299. }
  300. };
  301. /** @return {boolean} Whether this value is zero. */
  302. goog.math.Long.prototype.isZero = function() {
  303. return this.high_ == 0 && this.low_ == 0;
  304. };
  305. /** @return {boolean} Whether this value is negative. */
  306. goog.math.Long.prototype.isNegative = function() {
  307. return this.high_ < 0;
  308. };
  309. /** @return {boolean} Whether this value is odd. */
  310. goog.math.Long.prototype.isOdd = function() {
  311. return (this.low_ & 1) == 1;
  312. };
  313. /**
  314. * @param {goog.math.Long} other Long to compare against.
  315. * @return {boolean} Whether this Long equals the other.
  316. */
  317. goog.math.Long.prototype.equals = function(other) {
  318. return (this.high_ == other.high_) && (this.low_ == other.low_);
  319. };
  320. /**
  321. * @param {goog.math.Long} other Long to compare against.
  322. * @return {boolean} Whether this Long does not equal the other.
  323. */
  324. goog.math.Long.prototype.notEquals = function(other) {
  325. return (this.high_ != other.high_) || (this.low_ != other.low_);
  326. };
  327. /**
  328. * @param {goog.math.Long} other Long to compare against.
  329. * @return {boolean} Whether this Long is less than the other.
  330. */
  331. goog.math.Long.prototype.lessThan = function(other) {
  332. return this.compare(other) < 0;
  333. };
  334. /**
  335. * @param {goog.math.Long} other Long to compare against.
  336. * @return {boolean} Whether this Long is less than or equal to the other.
  337. */
  338. goog.math.Long.prototype.lessThanOrEqual = function(other) {
  339. return this.compare(other) <= 0;
  340. };
  341. /**
  342. * @param {goog.math.Long} other Long to compare against.
  343. * @return {boolean} Whether this Long is greater than the other.
  344. */
  345. goog.math.Long.prototype.greaterThan = function(other) {
  346. return this.compare(other) > 0;
  347. };
  348. /**
  349. * @param {goog.math.Long} other Long to compare against.
  350. * @return {boolean} Whether this Long is greater than or equal to the other.
  351. */
  352. goog.math.Long.prototype.greaterThanOrEqual = function(other) {
  353. return this.compare(other) >= 0;
  354. };
  355. /**
  356. * Compares this Long with the given one.
  357. * @param {goog.math.Long} other Long to compare against.
  358. * @return {number} 0 if they are the same, 1 if the this is greater, and -1
  359. * if the given one is greater.
  360. */
  361. goog.math.Long.prototype.compare = function(other) {
  362. if (this.equals(other)) {
  363. return 0;
  364. }
  365. var thisNeg = this.isNegative();
  366. var otherNeg = other.isNegative();
  367. if (thisNeg && !otherNeg) {
  368. return -1;
  369. }
  370. if (!thisNeg && otherNeg) {
  371. return 1;
  372. }
  373. // at this point, the signs are the same, so subtraction will not overflow
  374. if (this.subtract(other).isNegative()) {
  375. return -1;
  376. } else {
  377. return 1;
  378. }
  379. };
  380. /** @return {!goog.math.Long} The negation of this value. */
  381. goog.math.Long.prototype.negate = function() {
  382. if (this.equals(goog.math.Long.MIN_VALUE)) {
  383. return goog.math.Long.MIN_VALUE;
  384. } else {
  385. return this.not().add(goog.math.Long.ONE);
  386. }
  387. };
  388. /**
  389. * Returns the sum of this and the given Long.
  390. * @param {goog.math.Long} other Long to add to this one.
  391. * @return {!goog.math.Long} The sum of this and the given Long.
  392. */
  393. goog.math.Long.prototype.add = function(other) {
  394. // Divide each number into 4 chunks of 16 bits, and then sum the chunks.
  395. var a48 = this.high_ >>> 16;
  396. var a32 = this.high_ & 0xFFFF;
  397. var a16 = this.low_ >>> 16;
  398. var a00 = this.low_ & 0xFFFF;
  399. var b48 = other.high_ >>> 16;
  400. var b32 = other.high_ & 0xFFFF;
  401. var b16 = other.low_ >>> 16;
  402. var b00 = other.low_ & 0xFFFF;
  403. var c48 = 0, c32 = 0, c16 = 0, c00 = 0;
  404. c00 += a00 + b00;
  405. c16 += c00 >>> 16;
  406. c00 &= 0xFFFF;
  407. c16 += a16 + b16;
  408. c32 += c16 >>> 16;
  409. c16 &= 0xFFFF;
  410. c32 += a32 + b32;
  411. c48 += c32 >>> 16;
  412. c32 &= 0xFFFF;
  413. c48 += a48 + b48;
  414. c48 &= 0xFFFF;
  415. return goog.math.Long.fromBits((c16 << 16) | c00, (c48 << 16) | c32);
  416. };
  417. /**
  418. * Returns the difference of this and the given Long.
  419. * @param {goog.math.Long} other Long to subtract from this.
  420. * @return {!goog.math.Long} The difference of this and the given Long.
  421. */
  422. goog.math.Long.prototype.subtract = function(other) {
  423. return this.add(other.negate());
  424. };
  425. /**
  426. * Returns the product of this and the given long.
  427. * @param {goog.math.Long} other Long to multiply with this.
  428. * @return {!goog.math.Long} The product of this and the other.
  429. */
  430. goog.math.Long.prototype.multiply = function(other) {
  431. if (this.isZero()) {
  432. return goog.math.Long.ZERO;
  433. } else if (other.isZero()) {
  434. return goog.math.Long.ZERO;
  435. }
  436. if (this.equals(goog.math.Long.MIN_VALUE)) {
  437. return other.isOdd() ? goog.math.Long.MIN_VALUE : goog.math.Long.ZERO;
  438. } else if (other.equals(goog.math.Long.MIN_VALUE)) {
  439. return this.isOdd() ? goog.math.Long.MIN_VALUE : goog.math.Long.ZERO;
  440. }
  441. if (this.isNegative()) {
  442. if (other.isNegative()) {
  443. return this.negate().multiply(other.negate());
  444. } else {
  445. return this.negate().multiply(other).negate();
  446. }
  447. } else if (other.isNegative()) {
  448. return this.multiply(other.negate()).negate();
  449. }
  450. // If both longs are small, use float multiplication
  451. if (this.lessThan(goog.math.Long.TWO_PWR_24_) &&
  452. other.lessThan(goog.math.Long.TWO_PWR_24_)) {
  453. return goog.math.Long.fromNumber(this.toNumber() * other.toNumber());
  454. }
  455. // Divide each long into 4 chunks of 16 bits, and then add up 4x4 products.
  456. // We can skip products that would overflow.
  457. var a48 = this.high_ >>> 16;
  458. var a32 = this.high_ & 0xFFFF;
  459. var a16 = this.low_ >>> 16;
  460. var a00 = this.low_ & 0xFFFF;
  461. var b48 = other.high_ >>> 16;
  462. var b32 = other.high_ & 0xFFFF;
  463. var b16 = other.low_ >>> 16;
  464. var b00 = other.low_ & 0xFFFF;
  465. var c48 = 0, c32 = 0, c16 = 0, c00 = 0;
  466. c00 += a00 * b00;
  467. c16 += c00 >>> 16;
  468. c00 &= 0xFFFF;
  469. c16 += a16 * b00;
  470. c32 += c16 >>> 16;
  471. c16 &= 0xFFFF;
  472. c16 += a00 * b16;
  473. c32 += c16 >>> 16;
  474. c16 &= 0xFFFF;
  475. c32 += a32 * b00;
  476. c48 += c32 >>> 16;
  477. c32 &= 0xFFFF;
  478. c32 += a16 * b16;
  479. c48 += c32 >>> 16;
  480. c32 &= 0xFFFF;
  481. c32 += a00 * b32;
  482. c48 += c32 >>> 16;
  483. c32 &= 0xFFFF;
  484. c48 += a48 * b00 + a32 * b16 + a16 * b32 + a00 * b48;
  485. c48 &= 0xFFFF;
  486. return goog.math.Long.fromBits((c16 << 16) | c00, (c48 << 16) | c32);
  487. };
  488. /**
  489. * Returns this Long divided by the given one.
  490. * @param {goog.math.Long} other Long by which to divide.
  491. * @return {!goog.math.Long} This Long divided by the given one.
  492. */
  493. goog.math.Long.prototype.div = function(other) {
  494. if (other.isZero()) {
  495. throw Error('division by zero');
  496. } else if (this.isZero()) {
  497. return goog.math.Long.ZERO;
  498. }
  499. if (this.equals(goog.math.Long.MIN_VALUE)) {
  500. if (other.equals(goog.math.Long.ONE) ||
  501. other.equals(goog.math.Long.NEG_ONE)) {
  502. return goog.math.Long.MIN_VALUE; // recall that -MIN_VALUE == MIN_VALUE
  503. } else if (other.equals(goog.math.Long.MIN_VALUE)) {
  504. return goog.math.Long.ONE;
  505. } else {
  506. // At this point, we have |other| >= 2, so |this/other| < |MIN_VALUE|.
  507. var halfThis = this.shiftRight(1);
  508. var approx = halfThis.div(other).shiftLeft(1);
  509. if (approx.equals(goog.math.Long.ZERO)) {
  510. return other.isNegative() ? goog.math.Long.ONE : goog.math.Long.NEG_ONE;
  511. } else {
  512. var rem = this.subtract(other.multiply(approx));
  513. var result = approx.add(rem.div(other));
  514. return result;
  515. }
  516. }
  517. } else if (other.equals(goog.math.Long.MIN_VALUE)) {
  518. return goog.math.Long.ZERO;
  519. }
  520. if (this.isNegative()) {
  521. if (other.isNegative()) {
  522. return this.negate().div(other.negate());
  523. } else {
  524. return this.negate().div(other).negate();
  525. }
  526. } else if (other.isNegative()) {
  527. return this.div(other.negate()).negate();
  528. }
  529. // Repeat the following until the remainder is less than other: find a
  530. // floating-point that approximates remainder / other *from below*, add this
  531. // into the result, and subtract it from the remainder. It is critical that
  532. // the approximate value is less than or equal to the real value so that the
  533. // remainder never becomes negative.
  534. var res = goog.math.Long.ZERO;
  535. var rem = this;
  536. while (rem.greaterThanOrEqual(other)) {
  537. // Approximate the result of division. This may be a little greater or
  538. // smaller than the actual value.
  539. var approx = Math.max(1, Math.floor(rem.toNumber() / other.toNumber()));
  540. // We will tweak the approximate result by changing it in the 48-th digit or
  541. // the smallest non-fractional digit, whichever is larger.
  542. var log2 = Math.ceil(Math.log(approx) / Math.LN2);
  543. var delta = (log2 <= 48) ? 1 : Math.pow(2, log2 - 48);
  544. // Decrease the approximation until it is smaller than the remainder. Note
  545. // that if it is too large, the product overflows and is negative.
  546. var approxRes = goog.math.Long.fromNumber(approx);
  547. var approxRem = approxRes.multiply(other);
  548. while (approxRem.isNegative() || approxRem.greaterThan(rem)) {
  549. approx -= delta;
  550. approxRes = goog.math.Long.fromNumber(approx);
  551. approxRem = approxRes.multiply(other);
  552. }
  553. // We know the answer can't be zero... and actually, zero would cause
  554. // infinite recursion since we would make no progress.
  555. if (approxRes.isZero()) {
  556. approxRes = goog.math.Long.ONE;
  557. }
  558. res = res.add(approxRes);
  559. rem = rem.subtract(approxRem);
  560. }
  561. return res;
  562. };
  563. /**
  564. * Returns this Long modulo the given one.
  565. * @param {goog.math.Long} other Long by which to mod.
  566. * @return {!goog.math.Long} This Long modulo the given one.
  567. */
  568. goog.math.Long.prototype.modulo = function(other) {
  569. return this.subtract(this.div(other).multiply(other));
  570. };
  571. /** @return {!goog.math.Long} The bitwise-NOT of this value. */
  572. goog.math.Long.prototype.not = function() {
  573. return goog.math.Long.fromBits(~this.low_, ~this.high_);
  574. };
  575. /**
  576. * Returns the bitwise-AND of this Long and the given one.
  577. * @param {goog.math.Long} other The Long with which to AND.
  578. * @return {!goog.math.Long} The bitwise-AND of this and the other.
  579. */
  580. goog.math.Long.prototype.and = function(other) {
  581. return goog.math.Long.fromBits(this.low_ & other.low_,
  582. this.high_ & other.high_);
  583. };
  584. /**
  585. * Returns the bitwise-OR of this Long and the given one.
  586. * @param {goog.math.Long} other The Long with which to OR.
  587. * @return {!goog.math.Long} The bitwise-OR of this and the other.
  588. */
  589. goog.math.Long.prototype.or = function(other) {
  590. return goog.math.Long.fromBits(this.low_ | other.low_,
  591. this.high_ | other.high_);
  592. };
  593. /**
  594. * Returns the bitwise-XOR of this Long and the given one.
  595. * @param {goog.math.Long} other The Long with which to XOR.
  596. * @return {!goog.math.Long} The bitwise-XOR of this and the other.
  597. */
  598. goog.math.Long.prototype.xor = function(other) {
  599. return goog.math.Long.fromBits(this.low_ ^ other.low_,
  600. this.high_ ^ other.high_);
  601. };
  602. /**
  603. * Returns this Long with bits shifted to the left by the given amount.
  604. * @param {number} numBits The number of bits by which to shift.
  605. * @return {!goog.math.Long} This shifted to the left by the given amount.
  606. */
  607. goog.math.Long.prototype.shiftLeft = function(numBits) {
  608. numBits &= 63;
  609. if (numBits == 0) {
  610. return this;
  611. } else {
  612. var low = this.low_;
  613. if (numBits < 32) {
  614. var high = this.high_;
  615. return goog.math.Long.fromBits(
  616. low << numBits,
  617. (high << numBits) | (low >>> (32 - numBits)));
  618. } else {
  619. return goog.math.Long.fromBits(0, low << (numBits - 32));
  620. }
  621. }
  622. };
  623. /**
  624. * Returns this Long with bits shifted to the right by the given amount.
  625. * @param {number} numBits The number of bits by which to shift.
  626. * @return {!goog.math.Long} This shifted to the right by the given amount.
  627. */
  628. goog.math.Long.prototype.shiftRight = function(numBits) {
  629. numBits &= 63;
  630. if (numBits == 0) {
  631. return this;
  632. } else {
  633. var high = this.high_;
  634. if (numBits < 32) {
  635. var low = this.low_;
  636. return goog.math.Long.fromBits(
  637. (low >>> numBits) | (high << (32 - numBits)),
  638. high >> numBits);
  639. } else {
  640. return goog.math.Long.fromBits(
  641. high >> (numBits - 32),
  642. high >= 0 ? 0 : -1);
  643. }
  644. }
  645. };
  646. /**
  647. * Returns this Long with bits shifted to the right by the given amount, with
  648. * zeros placed into the new leading bits.
  649. * @param {number} numBits The number of bits by which to shift.
  650. * @return {!goog.math.Long} This shifted to the right by the given amount, with
  651. * zeros placed into the new leading bits.
  652. */
  653. goog.math.Long.prototype.shiftRightUnsigned = function(numBits) {
  654. numBits &= 63;
  655. if (numBits == 0) {
  656. return this;
  657. } else {
  658. var high = this.high_;
  659. if (numBits < 32) {
  660. var low = this.low_;
  661. return goog.math.Long.fromBits(
  662. (low >>> numBits) | (high << (32 - numBits)),
  663. high >>> numBits);
  664. } else if (numBits == 32) {
  665. return goog.math.Long.fromBits(high, 0);
  666. } else {
  667. return goog.math.Long.fromBits(high >>> (numBits - 32), 0);
  668. }
  669. }
  670. };
  671. module.exports = goog.math.Long;