README.md (19903B)
1 # BigInteger.js [![Build Status][travis-img]][travis-url] [![Coverage Status][coveralls-img]][coveralls-url] [![Monthly Downloads][downloads-img]][downloads-url] 2 3 [travis-url]: https://travis-ci.org/peterolson/BigInteger.js 4 [travis-img]: https://travis-ci.org/peterolson/BigInteger.js.svg?branch=master 5 [coveralls-url]: https://coveralls.io/github/peterolson/BigInteger.js?branch=master 6 [coveralls-img]: https://coveralls.io/repos/peterolson/BigInteger.js/badge.svg?branch=master&service=github 7 [downloads-url]: https://www.npmjs.com/package/big-integer 8 [downloads-img]: https://img.shields.io/npm/dm/big-integer.svg 9 10 **BigInteger.js** is an arbitrary-length integer library for Javascript, allowing arithmetic operations on integers of unlimited size, notwithstanding memory and time limitations. 11 12 **Update (December 2, 2018):** [`BigInt` is being added as a native feature of JavaScript](https://tc39.github.io/proposal-bigint/). This library now works as a polyfill: if the environment supports the native `BigInt`, this library acts as a thin wrapper over the native implementation. 13 14 ## Installation 15 16 If you are using a browser, you can download [BigInteger.js from GitHub](http://peterolson.github.com/BigInteger.js/BigInteger.min.js) or just hotlink to it: 17 18 <script src="https://peterolson.github.io/BigInteger.js/BigInteger.min.js"></script> 19 20 If you are using node, you can install BigInteger with [npm](https://npmjs.org/). 21 22 npm install big-integer 23 24 Then you can include it in your code: 25 26 var bigInt = require("big-integer"); 27 28 29 ## Usage 30 ### `bigInt(number, [base], [alphabet], [caseSensitive])` 31 32 You can create a bigInt by calling the `bigInt` function. You can pass in 33 34 - a string, which it will parse as an bigInt and throw an `"Invalid integer"` error if the parsing fails. 35 - a Javascript number, which it will parse as an bigInt and throw an `"Invalid integer"` error if the parsing fails. 36 - another bigInt. 37 - nothing, and it will return `bigInt.zero`. 38 39 If you provide a second parameter, then it will parse `number` as a number in base `base`. Note that `base` can be any bigInt (even negative or zero). The letters "a-z" and "A-Z" will be interpreted as the numbers 10 to 35. Higher digits can be specified in angle brackets (`<` and `>`). The default `base` is `10`. 40 41 You can specify a custom alphabet for base conversion with the third parameter. The default `alphabet` is `"0123456789abcdefghijklmnopqrstuvwxyz"`. 42 43 The fourth parameter specifies whether or not the number string should be case-sensitive, i.e. whether `a` and `A` should be treated as different digits. By default `caseSensitive` is `false`. 44 45 Examples: 46 47 var zero = bigInt(); 48 var ninetyThree = bigInt(93); 49 var largeNumber = bigInt("75643564363473453456342378564387956906736546456235345"); 50 var googol = bigInt("1e100"); 51 var bigNumber = bigInt(largeNumber); 52 53 var maximumByte = bigInt("FF", 16); 54 var fiftyFiveGoogol = bigInt("<55>0", googol); 55 56 Note that Javascript numbers larger than `9007199254740992` and smaller than `-9007199254740992` are not precisely represented numbers and will not produce exact results. If you are dealing with numbers outside that range, it is better to pass in strings. 57 58 ### Method Chaining 59 60 Note that bigInt operations return bigInts, which allows you to chain methods, for example: 61 62 var salary = bigInt(dollarsPerHour).times(hoursWorked).plus(randomBonuses) 63 64 ### Constants 65 66 There are three named constants already stored that you do not have to construct with the `bigInt` function yourself: 67 68 - `bigInt.one`, equivalent to `bigInt(1)` 69 - `bigInt.zero`, equivalent to `bigInt(0)` 70 - `bigInt.minusOne`, equivalent to `bigInt(-1)` 71 72 The numbers from -999 to 999 are also already prestored and can be accessed using `bigInt[index]`, for example: 73 74 - `bigInt[-999]`, equivalent to `bigInt(-999)` 75 - `bigInt[256]`, equivalent to `bigInt(256)` 76 77 ### Methods 78 79 #### `abs()` 80 81 Returns the absolute value of a bigInt. 82 83 - `bigInt(-45).abs()` => `45` 84 - `bigInt(45).abs()` => `45` 85 86 #### `add(number)` 87 88 Performs addition. 89 90 - `bigInt(5).add(7)` => `12` 91 92 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Addition) 93 94 #### `and(number)` 95 96 Performs the bitwise AND operation. The operands are treated as if they were represented using [two's complement representation](http://en.wikipedia.org/wiki/Two%27s_complement). 97 98 - `bigInt(6).and(3)` => `2` 99 - `bigInt(6).and(-3)` => `4` 100 101 #### `bitLength()` 102 103 Returns the number of digits required to represent a bigInt in binary. 104 105 - `bigInt(5)` => `3` (since 5 is `101` in binary, which is three digits long) 106 107 #### `compare(number)` 108 109 Performs a comparison between two numbers. If the numbers are equal, it returns `0`. If the first number is greater, it returns `1`. If the first number is lesser, it returns `-1`. 110 111 - `bigInt(5).compare(5)` => `0` 112 - `bigInt(5).compare(4)` => `1` 113 - `bigInt(4).compare(5)` => `-1` 114 115 #### `compareAbs(number)` 116 117 Performs a comparison between the absolute value of two numbers. 118 119 - `bigInt(5).compareAbs(-5)` => `0` 120 - `bigInt(5).compareAbs(4)` => `1` 121 - `bigInt(4).compareAbs(-5)` => `-1` 122 123 #### `compareTo(number)` 124 125 Alias for the `compare` method. 126 127 #### `divide(number)` 128 129 Performs integer division, disregarding the remainder. 130 131 - `bigInt(59).divide(5)` => `11` 132 133 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Division) 134 135 #### `divmod(number)` 136 137 Performs division and returns an object with two properties: `quotient` and `remainder`. The sign of the remainder will match the sign of the dividend. 138 139 - `bigInt(59).divmod(5)` => `{quotient: bigInt(11), remainder: bigInt(4) }` 140 - `bigInt(-5).divmod(2)` => `{quotient: bigInt(-2), remainder: bigInt(-1) }` 141 142 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Division) 143 144 #### `eq(number)` 145 146 Alias for the `equals` method. 147 148 #### `equals(number)` 149 150 Checks if two numbers are equal. 151 152 - `bigInt(5).equals(5)` => `true` 153 - `bigInt(4).equals(7)` => `false` 154 155 #### `geq(number)` 156 157 Alias for the `greaterOrEquals` method. 158 159 160 #### `greater(number)` 161 162 Checks if the first number is greater than the second. 163 164 - `bigInt(5).greater(6)` => `false` 165 - `bigInt(5).greater(5)` => `false` 166 - `bigInt(5).greater(4)` => `true` 167 168 #### `greaterOrEquals(number)` 169 170 Checks if the first number is greater than or equal to the second. 171 172 - `bigInt(5).greaterOrEquals(6)` => `false` 173 - `bigInt(5).greaterOrEquals(5)` => `true` 174 - `bigInt(5).greaterOrEquals(4)` => `true` 175 176 #### `gt(number)` 177 178 Alias for the `greater` method. 179 180 #### `isDivisibleBy(number)` 181 182 Returns `true` if the first number is divisible by the second number, `false` otherwise. 183 184 - `bigInt(999).isDivisibleBy(333)` => `true` 185 - `bigInt(99).isDivisibleBy(5)` => `false` 186 187 #### `isEven()` 188 189 Returns `true` if the number is even, `false` otherwise. 190 191 - `bigInt(6).isEven()` => `true` 192 - `bigInt(3).isEven()` => `false` 193 194 #### `isNegative()` 195 196 Returns `true` if the number is negative, `false` otherwise. 197 Returns `false` for `0` and `-0`. 198 199 - `bigInt(-23).isNegative()` => `true` 200 - `bigInt(50).isNegative()` => `false` 201 202 #### `isOdd()` 203 204 Returns `true` if the number is odd, `false` otherwise. 205 206 - `bigInt(13).isOdd()` => `true` 207 - `bigInt(40).isOdd()` => `false` 208 209 #### `isPositive()` 210 211 Return `true` if the number is positive, `false` otherwise. 212 Returns `false` for `0` and `-0`. 213 214 - `bigInt(54).isPositive()` => `true` 215 - `bigInt(-1).isPositive()` => `false` 216 217 #### `isPrime(strict?)` 218 219 Returns `true` if the number is prime, `false` otherwise. 220 Set "strict" boolean to true to force GRH-supported lower bound of 2*log(N)^2. 221 222 - `bigInt(5).isPrime()` => `true` 223 - `bigInt(6).isPrime()` => `false` 224 225 #### `isProbablePrime([iterations], [rng])` 226 227 Returns `true` if the number is very likely to be prime, `false` otherwise. 228 Supplying `iterations` is optional - it determines the number of iterations of the test (default: `5`). The more iterations, the lower chance of getting a false positive. 229 This uses the [Miller Rabin test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test). 230 231 - `bigInt(5).isProbablePrime()` => `true` 232 - `bigInt(49).isProbablePrime()` => `false` 233 - `bigInt(1729).isProbablePrime()` => `false` 234 235 Note that this function is not deterministic, since it relies on random sampling of factors, so the result for some numbers is not always the same - unless you pass a predictable random number generator as `rng`. The behavior and requirements are the same as with `randBetween`. 236 237 - `bigInt(1729).isProbablePrime(1, () => 0.1)` => `false` 238 - `bigInt(1729).isProbablePrime(1, () => 0.2)` => `true` 239 240 If the number is composite then the Miller–Rabin primality test declares the number probably prime with a probability at most `4` to the power `−iterations`. 241 If the number is prime, this function always returns `true`. 242 243 #### `isUnit()` 244 245 Returns `true` if the number is `1` or `-1`, `false` otherwise. 246 247 - `bigInt.one.isUnit()` => `true` 248 - `bigInt.minusOne.isUnit()` => `true` 249 - `bigInt(5).isUnit()` => `false` 250 251 #### `isZero()` 252 253 Return `true` if the number is `0` or `-0`, `false` otherwise. 254 255 - `bigInt.zero.isZero()` => `true` 256 - `bigInt("-0").isZero()` => `true` 257 - `bigInt(50).isZero()` => `false` 258 259 #### `leq(number)` 260 261 Alias for the `lesserOrEquals` method. 262 263 #### `lesser(number)` 264 265 Checks if the first number is lesser than the second. 266 267 - `bigInt(5).lesser(6)` => `true` 268 - `bigInt(5).lesser(5)` => `false` 269 - `bigInt(5).lesser(4)` => `false` 270 271 #### `lesserOrEquals(number)` 272 273 Checks if the first number is less than or equal to the second. 274 275 - `bigInt(5).lesserOrEquals(6)` => `true` 276 - `bigInt(5).lesserOrEquals(5)` => `true` 277 - `bigInt(5).lesserOrEquals(4)` => `false` 278 279 #### `lt(number)` 280 281 Alias for the `lesser` method. 282 283 #### `minus(number)` 284 285 Alias for the `subtract` method. 286 287 - `bigInt(3).minus(5)` => `-2` 288 289 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Subtraction) 290 291 #### `mod(number)` 292 293 Performs division and returns the remainder, disregarding the quotient. The sign of the remainder will match the sign of the dividend. 294 295 - `bigInt(59).mod(5)` => `4` 296 - `bigInt(-5).mod(2)` => `-1` 297 298 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Division) 299 300 #### `modInv(mod)` 301 302 Finds the [multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) of the number modulo `mod`. 303 304 - `bigInt(3).modInv(11)` => `4` 305 - `bigInt(42).modInv(2017)` => `1969` 306 307 #### `modPow(exp, mod)` 308 309 Takes the number to the power `exp` modulo `mod`. 310 311 - `bigInt(10).modPow(3, 30)` => `10` 312 313 #### `multiply(number)` 314 315 Performs multiplication. 316 317 - `bigInt(111).multiply(111)` => `12321` 318 319 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Multiplication) 320 321 #### `neq(number)` 322 323 Alias for the `notEquals` method. 324 325 #### `next()` 326 327 Adds one to the number. 328 329 - `bigInt(6).next()` => `7` 330 331 #### `not()` 332 333 Performs the bitwise NOT operation. The operands are treated as if they were represented using [two's complement representation](http://en.wikipedia.org/wiki/Two%27s_complement). 334 335 - `bigInt(10).not()` => `-11` 336 - `bigInt(0).not()` => `-1` 337 338 #### `notEquals(number)` 339 340 Checks if two numbers are not equal. 341 342 - `bigInt(5).notEquals(5)` => `false` 343 - `bigInt(4).notEquals(7)` => `true` 344 345 #### `or(number)` 346 347 Performs the bitwise OR operation. The operands are treated as if they were represented using [two's complement representation](http://en.wikipedia.org/wiki/Two%27s_complement). 348 349 - `bigInt(13).or(10)` => `15` 350 - `bigInt(13).or(-8)` => `-3` 351 352 #### `over(number)` 353 354 Alias for the `divide` method. 355 356 - `bigInt(59).over(5)` => `11` 357 358 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Division) 359 360 #### `plus(number)` 361 362 Alias for the `add` method. 363 364 - `bigInt(5).plus(7)` => `12` 365 366 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Addition) 367 368 #### `pow(number)` 369 370 Performs exponentiation. If the exponent is less than `0`, `pow` returns `0`. `bigInt.zero.pow(0)` returns `1`. 371 372 - `bigInt(16).pow(16)` => `18446744073709551616` 373 374 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Exponentiation) 375 376 #### `prev(number)` 377 378 Subtracts one from the number. 379 380 - `bigInt(6).prev()` => `5` 381 382 #### `remainder(number)` 383 384 Alias for the `mod` method. 385 386 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Division) 387 388 #### `shiftLeft(n)` 389 390 Shifts the number left by `n` places in its binary representation. If a negative number is provided, it will shift right. Throws an error if `n` is outside of the range `[-9007199254740992, 9007199254740992]`. 391 392 - `bigInt(8).shiftLeft(2)` => `32` 393 - `bigInt(8).shiftLeft(-2)` => `2` 394 395 #### `shiftRight(n)` 396 397 Shifts the number right by `n` places in its binary representation. If a negative number is provided, it will shift left. Throws an error if `n` is outside of the range `[-9007199254740992, 9007199254740992]`. 398 399 - `bigInt(8).shiftRight(2)` => `2` 400 - `bigInt(8).shiftRight(-2)` => `32` 401 402 #### `square()` 403 404 Squares the number 405 406 - `bigInt(3).square()` => `9` 407 408 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Squaring) 409 410 #### `subtract(number)` 411 412 Performs subtraction. 413 414 - `bigInt(3).subtract(5)` => `-2` 415 416 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Subtraction) 417 418 #### `times(number)` 419 420 Alias for the `multiply` method. 421 422 - `bigInt(111).times(111)` => `12321` 423 424 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#Multiplication) 425 426 #### `toArray(radix)` 427 428 Converts a bigInt into an object with the properties "value" and "isNegative." "Value" is an array of integers modulo the given radix. "isNegative" is a boolean that represents the sign of the result. 429 430 - `bigInt("1e9").toArray(10)` => { 431 value: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 432 isNegative: false 433 } 434 - `bigInt("1e9").toArray(16)` => { 435 value: [3, 11, 9, 10, 12, 10, 0, 0], 436 isNegative: false 437 } 438 - `bigInt(567890).toArray(100)` => { 439 value: [56, 78, 90], 440 isNegative: false 441 } 442 443 Negative bases are supported. 444 445 - `bigInt(12345).toArray(-10)` => { 446 value: [2, 8, 4, 6, 5], 447 isNegative: false 448 } 449 450 Base 1 and base -1 are also supported. 451 452 - `bigInt(-15).toArray(1)` => { 453 value: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 454 isNegative: true 455 } 456 - `bigInt(-15).toArray(-1)` => { 457 value: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 458 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0], 459 isNegative: false 460 } 461 462 Base 0 is only allowed for the number zero. 463 464 - `bigInt(0).toArray(0)` => { 465 value: [0], 466 isNegative: false 467 } 468 - `bigInt(1).toArray(0)` => `Error: Cannot convert nonzero numbers to base 0.` 469 470 #### `toJSNumber()` 471 472 Converts a bigInt into a native Javascript number. Loses precision for numbers outside the range `[-9007199254740992, 9007199254740992]`. 473 474 - `bigInt("18446744073709551616").toJSNumber()` => `18446744073709552000` 475 476 #### `xor(number)` 477 478 Performs the bitwise XOR operation. The operands are treated as if they were represented using [two's complement representation](http://en.wikipedia.org/wiki/Two%27s_complement). 479 480 - `bigInt(12).xor(5)` => `9` 481 - `bigInt(12).xor(-5)` => `-9` 482 483 ### Static Methods 484 485 #### `fromArray(digits, base = 10, isNegative?)` 486 487 Constructs a bigInt from an array of digits in base `base`. The optional `isNegative` flag will make the number negative. 488 489 - `bigInt.fromArray([1, 2, 3, 4, 5], 10)` => `12345` 490 - `bigInt.fromArray([1, 0, 0], 2, true)` => `-4` 491 492 #### `gcd(a, b)` 493 494 Finds the greatest common denominator of `a` and `b`. 495 496 - `bigInt.gcd(42,56)` => `14` 497 498 #### `isInstance(x)` 499 500 Returns `true` if `x` is a BigInteger, `false` otherwise. 501 502 - `bigInt.isInstance(bigInt(14))` => `true` 503 - `bigInt.isInstance(14)` => `false` 504 505 #### `lcm(a,b)` 506 507 Finds the least common multiple of `a` and `b`. 508 509 - `bigInt.lcm(21, 6)` => `42` 510 511 #### `max(a,b)` 512 513 Returns the largest of `a` and `b`. 514 515 - `bigInt.max(77, 432)` => `432` 516 517 #### `min(a,b)` 518 519 Returns the smallest of `a` and `b`. 520 521 - `bigInt.min(77, 432)` => `77` 522 523 #### `randBetween(min, max, [rng])` 524 525 Returns a random number between `min` and `max`, optionally using `rng` to generate randomness. 526 527 - `bigInt.randBetween("-1e100", "1e100")` => (for example) `8494907165436643479673097939554427056789510374838494147955756275846226209006506706784609314471378745` 528 529 `rng` should take no arguments and return a `number` between 0 and 1. It defaults to `Math.random`. 530 531 - `bigInt.randBetween("-1e100", "1e100", () => 0.5)` => (always) `50000005000000500000050000005000000500000050000005000000500000050000005000000500000050000005000000` 532 533 534 ### Override Methods 535 536 #### `toString(radix = 10, [alphabet])` 537 538 Converts a bigInt to a string. There is an optional radix parameter (which defaults to 10) that converts the number to the given radix. Digits in the range `10-35` will use the letters `a-z`. 539 540 - `bigInt("1e9").toString()` => `"1000000000"` 541 - `bigInt("1e9").toString(16)` => `"3b9aca00"` 542 543 You can use a custom base alphabet with the second parameter. The default `alphabet` is `"0123456789abcdefghijklmnopqrstuvwxyz"`. 544 545 - `bigInt("5").toString(2, "aA")` => `"AaA"` 546 547 **Note that arithmetical operators will trigger the `valueOf` function rather than the `toString` function.** When converting a bigInteger to a string, you should use the `toString` method or the `String` function instead of adding the empty string. 548 549 - `bigInt("999999999999999999").toString()` => `"999999999999999999"` 550 - `String(bigInt("999999999999999999"))` => `"999999999999999999"` 551 - `bigInt("999999999999999999") + ""` => `1000000000000000000` 552 553 Bases larger than 36 are supported. If a digit is greater than or equal to 36, it will be enclosed in angle brackets. 554 555 - `bigInt(567890).toString(100)` => `"<56><78><90>"` 556 557 Negative bases are also supported. 558 559 - `bigInt(12345).toString(-10)` => `"28465"` 560 561 Base 1 and base -1 are also supported. 562 563 - `bigInt(-15).toString(1)` => `"-111111111111111"` 564 - `bigInt(-15).toString(-1)` => `"101010101010101010101010101010"` 565 566 Base 0 is only allowed for the number zero. 567 568 - `bigInt(0).toString(0)` => `0` 569 - `bigInt(1).toString(0)` => `Error: Cannot convert nonzero numbers to base 0.` 570 571 [View benchmarks for this method](http://peterolson.github.io/BigInteger.js/benchmark/#toString) 572 573 #### `valueOf()` 574 575 Converts a bigInt to a native Javascript number. This override allows you to use native arithmetic operators without explicit conversion: 576 577 - `bigInt("100") + bigInt("200") === 300; //true` 578 579 ## Contributors 580 581 To contribute, just fork the project, make some changes, and submit a pull request. Please verify that the unit tests pass before submitting. 582 583 The unit tests are contained in the `spec/spec.js` file. You can run them locally by opening the `spec/SpecRunner.html` or file or running `npm test`. You can also [run the tests online from GitHub](http://peterolson.github.io/BigInteger.js/spec/SpecRunner.html). 584 585 There are performance benchmarks that can be viewed from the `benchmarks/index.html` page. You can [run them online from GitHub](http://peterolson.github.io/BigInteger.js/benchmark/). 586 587 ## License 588 589 This project is public domain. For more details, read about the [Unlicense](http://unlicense.org/).