fraction.js (20692B)
1 /** 2 * @license Fraction.js v4.2.0 05/03/2022 3 * https://www.xarg.org/2014/03/rational-numbers-in-javascript/ 4 * 5 * Copyright (c) 2021, Robert Eisele (robert@xarg.org) 6 * Dual licensed under the MIT or GPL Version 2 licenses. 7 **/ 8 9 10 /** 11 * 12 * This class offers the possibility to calculate fractions. 13 * You can pass a fraction in different formats. Either as array, as double, as string or as an integer. 14 * 15 * Array/Object form 16 * [ 0 => <nominator>, 1 => <denominator> ] 17 * [ n => <nominator>, d => <denominator> ] 18 * 19 * Integer form 20 * - Single integer value 21 * 22 * Double form 23 * - Single double value 24 * 25 * String form 26 * 123.456 - a simple double 27 * 123/456 - a string fraction 28 * 123.'456' - a double with repeating decimal places 29 * 123.(456) - synonym 30 * 123.45'6' - a double with repeating last place 31 * 123.45(6) - synonym 32 * 33 * Example: 34 * 35 * var f = new Fraction("9.4'31'"); 36 * f.mul([-4, 3]).div(4.9); 37 * 38 */ 39 40 (function(root) { 41 42 "use strict"; 43 44 // Maximum search depth for cyclic rational numbers. 2000 should be more than enough. 45 // Example: 1/7 = 0.(142857) has 6 repeating decimal places. 46 // If MAX_CYCLE_LEN gets reduced, long cycles will not be detected and toString() only gets the first 10 digits 47 var MAX_CYCLE_LEN = 2000; 48 49 // Parsed data to avoid calling "new" all the time 50 var P = { 51 "s": 1, 52 "n": 0, 53 "d": 1 54 }; 55 56 function assign(n, s) { 57 58 if (isNaN(n = parseInt(n, 10))) { 59 throw Fraction['InvalidParameter']; 60 } 61 return n * s; 62 } 63 64 // Creates a new Fraction internally without the need of the bulky constructor 65 function newFraction(n, d) { 66 67 if (d === 0) { 68 throw Fraction['DivisionByZero']; 69 } 70 71 var f = Object.create(Fraction.prototype); 72 f["s"] = n < 0 ? -1 : 1; 73 74 n = n < 0 ? -n : n; 75 76 var a = gcd(n, d); 77 78 f["n"] = n / a; 79 f["d"] = d / a; 80 return f; 81 } 82 83 function factorize(num) { 84 85 var factors = {}; 86 87 var n = num; 88 var i = 2; 89 var s = 4; 90 91 while (s <= n) { 92 93 while (n % i === 0) { 94 n/= i; 95 factors[i] = (factors[i] || 0) + 1; 96 } 97 s+= 1 + 2 * i++; 98 } 99 100 if (n !== num) { 101 if (n > 1) 102 factors[n] = (factors[n] || 0) + 1; 103 } else { 104 factors[num] = (factors[num] || 0) + 1; 105 } 106 return factors; 107 } 108 109 var parse = function(p1, p2) { 110 111 var n = 0, d = 1, s = 1; 112 var v = 0, w = 0, x = 0, y = 1, z = 1; 113 114 var A = 0, B = 1; 115 var C = 1, D = 1; 116 117 var N = 10000000; 118 var M; 119 120 if (p1 === undefined || p1 === null) { 121 /* void */ 122 } else if (p2 !== undefined) { 123 n = p1; 124 d = p2; 125 s = n * d; 126 127 if (n % 1 !== 0 || d % 1 !== 0) { 128 throw Fraction['NonIntegerParameter']; 129 } 130 131 } else 132 switch (typeof p1) { 133 134 case "object": 135 { 136 if ("d" in p1 && "n" in p1) { 137 n = p1["n"]; 138 d = p1["d"]; 139 if ("s" in p1) 140 n*= p1["s"]; 141 } else if (0 in p1) { 142 n = p1[0]; 143 if (1 in p1) 144 d = p1[1]; 145 } else { 146 throw Fraction['InvalidParameter']; 147 } 148 s = n * d; 149 break; 150 } 151 case "number": 152 { 153 if (p1 < 0) { 154 s = p1; 155 p1 = -p1; 156 } 157 158 if (p1 % 1 === 0) { 159 n = p1; 160 } else if (p1 > 0) { // check for != 0, scale would become NaN (log(0)), which converges really slow 161 162 if (p1 >= 1) { 163 z = Math.pow(10, Math.floor(1 + Math.log(p1) / Math.LN10)); 164 p1/= z; 165 } 166 167 // Using Farey Sequences 168 // http://www.johndcook.com/blog/2010/10/20/best-rational-approximation/ 169 170 while (B <= N && D <= N) { 171 M = (A + C) / (B + D); 172 173 if (p1 === M) { 174 if (B + D <= N) { 175 n = A + C; 176 d = B + D; 177 } else if (D > B) { 178 n = C; 179 d = D; 180 } else { 181 n = A; 182 d = B; 183 } 184 break; 185 186 } else { 187 188 if (p1 > M) { 189 A+= C; 190 B+= D; 191 } else { 192 C+= A; 193 D+= B; 194 } 195 196 if (B > N) { 197 n = C; 198 d = D; 199 } else { 200 n = A; 201 d = B; 202 } 203 } 204 } 205 n*= z; 206 } else if (isNaN(p1) || isNaN(p2)) { 207 d = n = NaN; 208 } 209 break; 210 } 211 case "string": 212 { 213 B = p1.match(/\d+|./g); 214 215 if (B === null) 216 throw Fraction['InvalidParameter']; 217 218 if (B[A] === '-') {// Check for minus sign at the beginning 219 s = -1; 220 A++; 221 } else if (B[A] === '+') {// Check for plus sign at the beginning 222 A++; 223 } 224 225 if (B.length === A + 1) { // Check if it's just a simple number "1234" 226 w = assign(B[A++], s); 227 } else if (B[A + 1] === '.' || B[A] === '.') { // Check if it's a decimal number 228 229 if (B[A] !== '.') { // Handle 0.5 and .5 230 v = assign(B[A++], s); 231 } 232 A++; 233 234 // Check for decimal places 235 if (A + 1 === B.length || B[A + 1] === '(' && B[A + 3] === ')' || B[A + 1] === "'" && B[A + 3] === "'") { 236 w = assign(B[A], s); 237 y = Math.pow(10, B[A].length); 238 A++; 239 } 240 241 // Check for repeating places 242 if (B[A] === '(' && B[A + 2] === ')' || B[A] === "'" && B[A + 2] === "'") { 243 x = assign(B[A + 1], s); 244 z = Math.pow(10, B[A + 1].length) - 1; 245 A+= 3; 246 } 247 248 } else if (B[A + 1] === '/' || B[A + 1] === ':') { // Check for a simple fraction "123/456" or "123:456" 249 w = assign(B[A], s); 250 y = assign(B[A + 2], 1); 251 A+= 3; 252 } else if (B[A + 3] === '/' && B[A + 1] === ' ') { // Check for a complex fraction "123 1/2" 253 v = assign(B[A], s); 254 w = assign(B[A + 2], s); 255 y = assign(B[A + 4], 1); 256 A+= 5; 257 } 258 259 if (B.length <= A) { // Check for more tokens on the stack 260 d = y * z; 261 s = /* void */ 262 n = x + d * v + z * w; 263 break; 264 } 265 266 /* Fall through on error */ 267 } 268 default: 269 throw Fraction['InvalidParameter']; 270 } 271 272 if (d === 0) { 273 throw Fraction['DivisionByZero']; 274 } 275 276 P["s"] = s < 0 ? -1 : 1; 277 P["n"] = Math.abs(n); 278 P["d"] = Math.abs(d); 279 }; 280 281 function modpow(b, e, m) { 282 283 var r = 1; 284 for (; e > 0; b = (b * b) % m, e >>= 1) { 285 286 if (e & 1) { 287 r = (r * b) % m; 288 } 289 } 290 return r; 291 } 292 293 294 function cycleLen(n, d) { 295 296 for (; d % 2 === 0; 297 d/= 2) { 298 } 299 300 for (; d % 5 === 0; 301 d/= 5) { 302 } 303 304 if (d === 1) // Catch non-cyclic numbers 305 return 0; 306 307 // If we would like to compute really large numbers quicker, we could make use of Fermat's little theorem: 308 // 10^(d-1) % d == 1 309 // However, we don't need such large numbers and MAX_CYCLE_LEN should be the capstone, 310 // as we want to translate the numbers to strings. 311 312 var rem = 10 % d; 313 var t = 1; 314 315 for (; rem !== 1; t++) { 316 rem = rem * 10 % d; 317 318 if (t > MAX_CYCLE_LEN) 319 return 0; // Returning 0 here means that we don't print it as a cyclic number. It's likely that the answer is `d-1` 320 } 321 return t; 322 } 323 324 325 function cycleStart(n, d, len) { 326 327 var rem1 = 1; 328 var rem2 = modpow(10, len, d); 329 330 for (var t = 0; t < 300; t++) { // s < ~log10(Number.MAX_VALUE) 331 // Solve 10^s == 10^(s+t) (mod d) 332 333 if (rem1 === rem2) 334 return t; 335 336 rem1 = rem1 * 10 % d; 337 rem2 = rem2 * 10 % d; 338 } 339 return 0; 340 } 341 342 function gcd(a, b) { 343 344 if (!a) 345 return b; 346 if (!b) 347 return a; 348 349 while (1) { 350 a%= b; 351 if (!a) 352 return b; 353 b%= a; 354 if (!b) 355 return a; 356 } 357 }; 358 359 /** 360 * Module constructor 361 * 362 * @constructor 363 * @param {number|Fraction=} a 364 * @param {number=} b 365 */ 366 function Fraction(a, b) { 367 368 parse(a, b); 369 370 if (this instanceof Fraction) { 371 a = gcd(P["d"], P["n"]); // Abuse variable a 372 this["s"] = P["s"]; 373 this["n"] = P["n"] / a; 374 this["d"] = P["d"] / a; 375 } else { 376 return newFraction(P['s'] * P['n'], P['d']); 377 } 378 } 379 380 Fraction['DivisionByZero'] = new Error("Division by Zero"); 381 Fraction['InvalidParameter'] = new Error("Invalid argument"); 382 Fraction['NonIntegerParameter'] = new Error("Parameters must be integer"); 383 384 Fraction.prototype = { 385 386 "s": 1, 387 "n": 0, 388 "d": 1, 389 390 /** 391 * Calculates the absolute value 392 * 393 * Ex: new Fraction(-4).abs() => 4 394 **/ 395 "abs": function() { 396 397 return newFraction(this["n"], this["d"]); 398 }, 399 400 /** 401 * Inverts the sign of the current fraction 402 * 403 * Ex: new Fraction(-4).neg() => 4 404 **/ 405 "neg": function() { 406 407 return newFraction(-this["s"] * this["n"], this["d"]); 408 }, 409 410 /** 411 * Adds two rational numbers 412 * 413 * Ex: new Fraction({n: 2, d: 3}).add("14.9") => 467 / 30 414 **/ 415 "add": function(a, b) { 416 417 parse(a, b); 418 return newFraction( 419 this["s"] * this["n"] * P["d"] + P["s"] * this["d"] * P["n"], 420 this["d"] * P["d"] 421 ); 422 }, 423 424 /** 425 * Subtracts two rational numbers 426 * 427 * Ex: new Fraction({n: 2, d: 3}).add("14.9") => -427 / 30 428 **/ 429 "sub": function(a, b) { 430 431 parse(a, b); 432 return newFraction( 433 this["s"] * this["n"] * P["d"] - P["s"] * this["d"] * P["n"], 434 this["d"] * P["d"] 435 ); 436 }, 437 438 /** 439 * Multiplies two rational numbers 440 * 441 * Ex: new Fraction("-17.(345)").mul(3) => 5776 / 111 442 **/ 443 "mul": function(a, b) { 444 445 parse(a, b); 446 return newFraction( 447 this["s"] * P["s"] * this["n"] * P["n"], 448 this["d"] * P["d"] 449 ); 450 }, 451 452 /** 453 * Divides two rational numbers 454 * 455 * Ex: new Fraction("-17.(345)").inverse().div(3) 456 **/ 457 "div": function(a, b) { 458 459 parse(a, b); 460 return newFraction( 461 this["s"] * P["s"] * this["n"] * P["d"], 462 this["d"] * P["n"] 463 ); 464 }, 465 466 /** 467 * Clones the actual object 468 * 469 * Ex: new Fraction("-17.(345)").clone() 470 **/ 471 "clone": function() { 472 return newFraction(this['s'] * this['n'], this['d']); 473 }, 474 475 /** 476 * Calculates the modulo of two rational numbers - a more precise fmod 477 * 478 * Ex: new Fraction('4.(3)').mod([7, 8]) => (13/3) % (7/8) = (5/6) 479 **/ 480 "mod": function(a, b) { 481 482 if (isNaN(this['n']) || isNaN(this['d'])) { 483 return new Fraction(NaN); 484 } 485 486 if (a === undefined) { 487 return newFraction(this["s"] * this["n"] % this["d"], 1); 488 } 489 490 parse(a, b); 491 if (0 === P["n"] && 0 === this["d"]) { 492 throw Fraction['DivisionByZero']; 493 } 494 495 /* 496 * First silly attempt, kinda slow 497 * 498 return that["sub"]({ 499 "n": num["n"] * Math.floor((this.n / this.d) / (num.n / num.d)), 500 "d": num["d"], 501 "s": this["s"] 502 });*/ 503 504 /* 505 * New attempt: a1 / b1 = a2 / b2 * q + r 506 * => b2 * a1 = a2 * b1 * q + b1 * b2 * r 507 * => (b2 * a1 % a2 * b1) / (b1 * b2) 508 */ 509 return newFraction( 510 this["s"] * (P["d"] * this["n"]) % (P["n"] * this["d"]), 511 P["d"] * this["d"] 512 ); 513 }, 514 515 /** 516 * Calculates the fractional gcd of two rational numbers 517 * 518 * Ex: new Fraction(5,8).gcd(3,7) => 1/56 519 */ 520 "gcd": function(a, b) { 521 522 parse(a, b); 523 524 // gcd(a / b, c / d) = gcd(a, c) / lcm(b, d) 525 526 return newFraction(gcd(P["n"], this["n"]) * gcd(P["d"], this["d"]), P["d"] * this["d"]); 527 }, 528 529 /** 530 * Calculates the fractional lcm of two rational numbers 531 * 532 * Ex: new Fraction(5,8).lcm(3,7) => 15 533 */ 534 "lcm": function(a, b) { 535 536 parse(a, b); 537 538 // lcm(a / b, c / d) = lcm(a, c) / gcd(b, d) 539 540 if (P["n"] === 0 && this["n"] === 0) { 541 return newFraction(0, 1); 542 } 543 return newFraction(P["n"] * this["n"], gcd(P["n"], this["n"]) * gcd(P["d"], this["d"])); 544 }, 545 546 /** 547 * Calculates the ceil of a rational number 548 * 549 * Ex: new Fraction('4.(3)').ceil() => (5 / 1) 550 **/ 551 "ceil": function(places) { 552 553 places = Math.pow(10, places || 0); 554 555 if (isNaN(this["n"]) || isNaN(this["d"])) { 556 return new Fraction(NaN); 557 } 558 return newFraction(Math.ceil(places * this["s"] * this["n"] / this["d"]), places); 559 }, 560 561 /** 562 * Calculates the floor of a rational number 563 * 564 * Ex: new Fraction('4.(3)').floor() => (4 / 1) 565 **/ 566 "floor": function(places) { 567 568 places = Math.pow(10, places || 0); 569 570 if (isNaN(this["n"]) || isNaN(this["d"])) { 571 return new Fraction(NaN); 572 } 573 return newFraction(Math.floor(places * this["s"] * this["n"] / this["d"]), places); 574 }, 575 576 /** 577 * Rounds a rational numbers 578 * 579 * Ex: new Fraction('4.(3)').round() => (4 / 1) 580 **/ 581 "round": function(places) { 582 583 places = Math.pow(10, places || 0); 584 585 if (isNaN(this["n"]) || isNaN(this["d"])) { 586 return new Fraction(NaN); 587 } 588 return newFraction(Math.round(places * this["s"] * this["n"] / this["d"]), places); 589 }, 590 591 /** 592 * Gets the inverse of the fraction, means numerator and denominator are exchanged 593 * 594 * Ex: new Fraction([-3, 4]).inverse() => -4 / 3 595 **/ 596 "inverse": function() { 597 598 return newFraction(this["s"] * this["d"], this["n"]); 599 }, 600 601 /** 602 * Calculates the fraction to some rational exponent, if possible 603 * 604 * Ex: new Fraction(-1,2).pow(-3) => -8 605 */ 606 "pow": function(a, b) { 607 608 parse(a, b); 609 610 // Trivial case when exp is an integer 611 612 if (P['d'] === 1) { 613 614 if (P['s'] < 0) { 615 return newFraction(Math.pow(this['s'] * this["d"], P['n']), Math.pow(this["n"], P['n'])); 616 } else { 617 return newFraction(Math.pow(this['s'] * this["n"], P['n']), Math.pow(this["d"], P['n'])); 618 } 619 } 620 621 // Negative roots become complex 622 // (-a/b)^(c/d) = x 623 // <=> (-1)^(c/d) * (a/b)^(c/d) = x 624 // <=> (cos(pi) + i*sin(pi))^(c/d) * (a/b)^(c/d) = x # rotate 1 by 180° 625 // <=> (cos(c*pi/d) + i*sin(c*pi/d)) * (a/b)^(c/d) = x # DeMoivre's formula in Q ( https://proofwiki.org/wiki/De_Moivre%27s_Formula/Rational_Index ) 626 // From which follows that only for c=0 the root is non-complex. c/d is a reduced fraction, so that sin(c/dpi)=0 occurs for d=1, which is handled by our trivial case. 627 if (this['s'] < 0) return null; 628 629 // Now prime factor n and d 630 var N = factorize(this['n']); 631 var D = factorize(this['d']); 632 633 // Exponentiate and take root for n and d individually 634 var n = 1; 635 var d = 1; 636 for (var k in N) { 637 if (k === '1') continue; 638 if (k === '0') { 639 n = 0; 640 break; 641 } 642 N[k]*= P['n']; 643 644 if (N[k] % P['d'] === 0) { 645 N[k]/= P['d']; 646 } else return null; 647 n*= Math.pow(k, N[k]); 648 } 649 650 for (var k in D) { 651 if (k === '1') continue; 652 D[k]*= P['n']; 653 654 if (D[k] % P['d'] === 0) { 655 D[k]/= P['d']; 656 } else return null; 657 d*= Math.pow(k, D[k]); 658 } 659 660 if (P['s'] < 0) { 661 return newFraction(d, n); 662 } 663 return newFraction(n, d); 664 }, 665 666 /** 667 * Check if two rational numbers are the same 668 * 669 * Ex: new Fraction(19.6).equals([98, 5]); 670 **/ 671 "equals": function(a, b) { 672 673 parse(a, b); 674 return this["s"] * this["n"] * P["d"] === P["s"] * P["n"] * this["d"]; // Same as compare() === 0 675 }, 676 677 /** 678 * Check if two rational numbers are the same 679 * 680 * Ex: new Fraction(19.6).equals([98, 5]); 681 **/ 682 "compare": function(a, b) { 683 684 parse(a, b); 685 var t = (this["s"] * this["n"] * P["d"] - P["s"] * P["n"] * this["d"]); 686 return (0 < t) - (t < 0); 687 }, 688 689 "simplify": function(eps) { 690 691 if (isNaN(this['n']) || isNaN(this['d'])) { 692 return this; 693 } 694 695 eps = eps || 0.001; 696 697 var thisABS = this['abs'](); 698 var cont = thisABS['toContinued'](); 699 700 for (var i = 1; i < cont.length; i++) { 701 702 var s = newFraction(cont[i - 1], 1); 703 for (var k = i - 2; k >= 0; k--) { 704 s = s['inverse']()['add'](cont[k]); 705 } 706 707 if (s['sub'](thisABS)['abs']().valueOf() < eps) { 708 return s['mul'](this['s']); 709 } 710 } 711 return this; 712 }, 713 714 /** 715 * Check if two rational numbers are divisible 716 * 717 * Ex: new Fraction(19.6).divisible(1.5); 718 */ 719 "divisible": function(a, b) { 720 721 parse(a, b); 722 return !(!(P["n"] * this["d"]) || ((this["n"] * P["d"]) % (P["n"] * this["d"]))); 723 }, 724 725 /** 726 * Returns a decimal representation of the fraction 727 * 728 * Ex: new Fraction("100.'91823'").valueOf() => 100.91823918239183 729 **/ 730 'valueOf': function() { 731 732 return this["s"] * this["n"] / this["d"]; 733 }, 734 735 /** 736 * Returns a string-fraction representation of a Fraction object 737 * 738 * Ex: new Fraction("1.'3'").toFraction(true) => "4 1/3" 739 **/ 740 'toFraction': function(excludeWhole) { 741 742 var whole, str = ""; 743 var n = this["n"]; 744 var d = this["d"]; 745 if (this["s"] < 0) { 746 str+= '-'; 747 } 748 749 if (d === 1) { 750 str+= n; 751 } else { 752 753 if (excludeWhole && (whole = Math.floor(n / d)) > 0) { 754 str+= whole; 755 str+= " "; 756 n%= d; 757 } 758 759 str+= n; 760 str+= '/'; 761 str+= d; 762 } 763 return str; 764 }, 765 766 /** 767 * Returns a latex representation of a Fraction object 768 * 769 * Ex: new Fraction("1.'3'").toLatex() => "\frac{4}{3}" 770 **/ 771 'toLatex': function(excludeWhole) { 772 773 var whole, str = ""; 774 var n = this["n"]; 775 var d = this["d"]; 776 if (this["s"] < 0) { 777 str+= '-'; 778 } 779 780 if (d === 1) { 781 str+= n; 782 } else { 783 784 if (excludeWhole && (whole = Math.floor(n / d)) > 0) { 785 str+= whole; 786 n%= d; 787 } 788 789 str+= "\\frac{"; 790 str+= n; 791 str+= '}{'; 792 str+= d; 793 str+= '}'; 794 } 795 return str; 796 }, 797 798 /** 799 * Returns an array of continued fraction elements 800 * 801 * Ex: new Fraction("7/8").toContinued() => [0,1,7] 802 */ 803 'toContinued': function() { 804 805 var t; 806 var a = this['n']; 807 var b = this['d']; 808 var res = []; 809 810 if (isNaN(a) || isNaN(b)) { 811 return res; 812 } 813 814 do { 815 res.push(Math.floor(a / b)); 816 t = a % b; 817 a = b; 818 b = t; 819 } while (a !== 1); 820 821 return res; 822 }, 823 824 /** 825 * Creates a string representation of a fraction with all digits 826 * 827 * Ex: new Fraction("100.'91823'").toString() => "100.(91823)" 828 **/ 829 'toString': function(dec) { 830 831 var N = this["n"]; 832 var D = this["d"]; 833 834 if (isNaN(N) || isNaN(D)) { 835 return "NaN"; 836 } 837 838 dec = dec || 15; // 15 = decimal places when no repetation 839 840 var cycLen = cycleLen(N, D); // Cycle length 841 var cycOff = cycleStart(N, D, cycLen); // Cycle start 842 843 var str = this['s'] < 0 ? "-" : ""; 844 845 str+= N / D | 0; 846 847 N%= D; 848 N*= 10; 849 850 if (N) 851 str+= "."; 852 853 if (cycLen) { 854 855 for (var i = cycOff; i--;) { 856 str+= N / D | 0; 857 N%= D; 858 N*= 10; 859 } 860 str+= "("; 861 for (var i = cycLen; i--;) { 862 str+= N / D | 0; 863 N%= D; 864 N*= 10; 865 } 866 str+= ")"; 867 } else { 868 for (var i = dec; N && i--;) { 869 str+= N / D | 0; 870 N%= D; 871 N*= 10; 872 } 873 } 874 return str; 875 } 876 }; 877 878 if (typeof define === "function" && define["amd"]) { 879 define([], function() { 880 return Fraction; 881 }); 882 } else if (typeof exports === "object") { 883 Object.defineProperty(Fraction, "__esModule", { 'value': true }); 884 Fraction['default'] = Fraction; 885 Fraction['Fraction'] = Fraction; 886 module['exports'] = Fraction; 887 } else { 888 root['Fraction'] = Fraction; 889 } 890 891 })(this);