Source of “adbabRational.js”.
285 lines, 8.7 KBytes.   Last modified 5:37 pm, 22nd November 2015 PST.
1 // Emacs settings: -*- mode: Fundamental; tab-width: 4; -*- 2 3 //////////////////////////////////////////////////////////////////////////// 4 // // 5 // Javascript exactly-calculated unbounded rationals // 6 // // 7 // Copyright (c) 2011-2013, Andrew Birrell // 8 // // 9 //////////////////////////////////////////////////////////////////////////// 10 11 // This library implements exactly-calculated rational arithmetic in 12 // Javascript, with no limits on the magnitude of the numerator or 13 // denominator. 14 // 15 // The library creates the global "adbab.Rational" class. It assumes the 16 // existence of the global "adbab.Bigint" class. 17 // 18 // Each rational is a pair of unlimited-magnitude integers; the value is 19 // their quotient. The denominator is always positive, and gcd(num, denom) 20 // is always 1. NaN values have a NaN numerator and denominator = 1. 21 // 22 // The public entry points are as follows. See the source for more detail. 23 // 24 // Constructor: 25 // new Rational(x) ... create a Rational object from a Number or String 26 // Properties of a Rational object "r" (read-only); 27 // r.num: ... the numerator, a Bigint 28 // r.denom: ... the denominator, a Bigint 29 // Methods of a Rational object "r": 30 // r.isInteger() ... true iff "r" is an integer (r.denom is 1) 31 // r.floor() ... the closest integer not greater than "r" 32 // r.round() ... the closest integer to "r" 33 // r.compare(x) ... (-1, 0, +1) if r is (lt, eq, gt) x 34 // r.negate() ... -r 35 // r.add(x) ... r + x 36 // r.sub(x) ... r - x 37 // r.mul(x) ... r * x 38 // r.div(x) ... r / x, exactly 39 // r.mod(x) ... r - x * floor(r/x); i.e., rounding to -infinity 40 // r.pow(x) ... r ^ x; requires x.isInteger() 41 // r.log10() ... floor(log base 10 of "r") 42 // Static properties of "Rational" (read-only): 43 // Rational.zero ... = new Rational(0) 44 // Rational.one ... = new Rational(1) 45 // Static methods of "Rational": 46 // Rational.pow10(n) ... 10^n, for ordinary integer n; uses a cache 47 48 "use strict"; 49 50 // "adbab" has already been declared, in "bigint.js" 51 52 adbab.Rational = (function() { // in-place call of an anonymous function 53 // 54 // This creates the Rational class and returns the its constructor 55 // function. The declarations are in a local scope: the global 56 // namespace is not altered. 57 58 var Bigint = adbab.Bigint; 59 60 function Rational(n) { 61 // Constructor for a Rational with given integral value, of any type 62 // (including integer or string). 63 // 64 // Numeric literals are decimal with optional decimal fraction, or 65 // hex (no fraction) if they contain [a-f], or hex if prefixed with 66 // "0x". Non-numeric strings produce NaN with the string as the NaN 67 // value, useful for propagating error messages. 68 // 69 if (typeof(n) == "string" && n.match(/^[0-9]*\.[0-9]*$/)) { 70 var intPart = n.replace(/\.[0-9]*/, ""); 71 var frPart = n.replace(/^[0-9]*\./, ""); 72 var factor = (new Bigint(10)).pow(new Bigint(frPart.length)); 73 this.num = (new Bigint(intPart)).mul(factor).add( 74 new Bigint(frPart)); 75 this.denom = factor; 76 this.normalize(); 77 } else { 78 this.num = new Bigint(n); 79 this.denom = Bigint.one; 80 } 81 } 82 83 Rational.zero = new Rational(0); 84 Rational.one = new Rational(1); 85 86 Rational.prototype.isInteger = function ratIsInteger() { 87 // Return true iff this.denom is 1 88 // 89 return (this.denom.absComp(Bigint.one) == 0); 90 }; 91 92 Rational.prototype.normalize = function ratNormalize() { 93 // Restore invariants, modifying "this" 94 // 95 if (this.num.NaN) { 96 this.denom = Bigint.one; 97 } else { 98 if (this.denom.neg) { 99 this.num.neg = !this.num.neg; 100 this.denom.neg = false; 101 } 102 var g = this.num.gcd(this.denom); 103 if (g.absComp(Bigint.one) != 0) { 104 this.num = this.num.div(g); 105 this.denom = this.denom.div(g); 106 } 107 } 108 }; 109 110 Rational.prototype.floor = function ratFloor() { 111 // Return this converted to an integer, rounding towards -infinity. 112 // 113 var res = new Rational(); 114 var divisor = (this.num.neg ? 115 this.num.sub(this.denom.sub(Bigint.one)) : this.num); 116 res.num = divisor.div(this.denom); // rounds towards zero 117 res.denom = Bigint.one; 118 return res; 119 }; 120 121 Rational.prototype.round = function ratRound() { 122 // Return this converted to an integer, rounding to closest. 123 // 124 var res = new Rational(); 125 var pad = this.denom.div(Bigint.two); 126 res.num = this.num.add( 127 this.num.neg ? pad.negate() : pad).div(this.denom); 128 res.denom = Bigint.one; 129 return res; 130 }; 131 132 Rational.prototype.compare = function ratCompare(x) { 133 // Return (-1, 0, +1) as this is (<, =, >) x. 134 // 135 if (this.num.neg == x.num.neg) { 136 return this.num.mul(x.denom).compare(x.num.mul(this.denom)); 137 } else { 138 if (this.num.NaN || x.num.NaN) return Number("a") // NaN 139 return (this.num.neg ? -1 : 1); 140 } 141 }; 142 143 Rational.prototype.negate = function ratNegate() { 144 // Return this negated 145 // 146 var res = new Rational(); 147 res.num = this.num.negate(); 148 res.denom = this.denom; 149 return res; 150 }; 151 152 Rational.prototype.add = function ratAdd(x) { 153 // Compute (a/b) + (c/d) 154 // = (ad/bd) + (bc/bd) 155 // = (ad + bc)/bd 156 // 157 var res = new Rational(); 158 res.num = this.num.mul(x.denom).add(x.num.mul(this.denom)); 159 res.denom = this.denom.mul(x.denom); 160 res.normalize(); 161 return res; 162 }; 163 164 Rational.prototype.sub = function ratSub(x) { 165 return this.add(x.negate()); 166 }; 167 168 Rational.prototype.mul = function ratMul(x) { 169 // Compute (a/b) * (c/d) 170 // = (ac/bd) 171 // 172 var res = new Rational(); 173 res.num = this.num.mul(x.num); 174 res.denom = this.denom.mul(x.denom); 175 res.normalize(); 176 return res; 177 }; 178 179 Rational.prototype.div = function ratDiv(x) { 180 // Compute (a/b) / (c/d) 181 // = (a/b) * (d/c) 182 // = (ad/bc) 183 // 184 var res = new Rational(); 185 res.num = this.num.mul(x.denom); 186 res.denom = this.denom.mul(x.num); 187 if (res.denom.absComp(Bigint.zero) == 0) { 188 return new Rational("divide by zero"); 189 } 190 res.normalize(); 191 return res; 192 }; 193 194 Rational.prototype.mod = function ratMod(x) { 195 // Compute (a/b) mod (c/d) 196 // = (ad mod bc)/bd 197 // 198 // The result is non-negative, as appropriate for modular 199 // arithmetic. This is unlike the underlying Bigint, whose division 200 // rounds toward zero, producing negative remainders for negative 201 // quotients. 202 // 203 var res = new Rational(); 204 var bc = this.denom.mul(x.num); 205 res.num = this.num.mul(x.denom, bc); 206 if (res.num.neg) res.num = res.num.add(bc); 207 res.denom = this.denom.mul(x.denom); 208 res.normalize(); 209 return res; 210 }; 211 212 Rational.prototype.pow = function ratPow(x) { 213 // Compute this^x, for integral x 214 // 215 if (!x.isInteger()) return new Rational( 216 "exponent must be an integer"); 217 var res = new Rational(); 218 var negate = x.num.neg; 219 var exp = (negate ? x.num.negate() : x.num); 220 var a = this.num.pow(exp); 221 var b = this.denom.pow(exp); 222 res.num = (negate ? b : a); 223 res.denom = (negate ? a : b); 224 res.normalize(); 225 return res; 226 }; 227 228 var ratTenPowers = new Array(); // INTERNAL: cache of powers of ten 229 230 Rational.pow10 = function ratPow10(n) { 231 // Return 10^n, efficiently, as a Rational (for any integer n). 232 // 233 if (n < 0) return Rational.one.div(Rational.pow10(-n)); 234 if (!ratTenPowers[0]) ratTenPowers[0] = Rational.one; 235 if (!ratTenPowers[1]) ratTenPowers[1] = new Rational(10); 236 if (!ratTenPowers[n]) { 237 var half = Math.floor(n/2); 238 ratTenPowers[n] = 239 Rational.pow10(half).mul(Rational.pow10(n - half)); 240 } 241 return ratTenPowers[n]; 242 }; 243 244 Rational.prototype.log10 = function ratLog10() { 245 // Return floor(log10(this)) as an integer. 246 // 247 // Requires that "this" is not NaN and is > 0 (caller should check). 248 // 249 // If "this" is about 10^(2^n), each loop has O(n) iterations. 250 // 251 if (this.num.NaN || this.compare(Rational.zero) <= 0) { 252 alert("Illegal argument for \"log10\""); 253 return 0; 254 } 255 var up = (this.compare(Rational.one) >= 0); 256 var delta = (up ? 1 : -1); 257 var exp = delta; 258 259 // First, find a bound by aggressive exploration 260 // 261 while (up ? this.compare(Rational.pow10(exp)) >= 0 : 262 this.compare(Rational.pow10(exp)) < 0) { 263 exp *= 2; 264 } 265 if (exp != delta) { 266 // Then, refine by binary chop. Note that exp is even. 267 // 268 var upb = exp; 269 var lwb = exp/2; 270 while (upb != lwb) { 271 var j = (up ? Math.floor : Math.ceil)((upb + lwb) / 2); 272 if (up ? this.compare(Rational.pow10(j)) >= 0 : 273 this.compare(Rational.pow10(j)) < 0) { 274 lwb = j + delta; 275 } else { 276 upb = j; 277 } 278 } 279 exp = lwb; 280 } 281 return (up ? exp - 1 : exp); 282 }; 283 284 return Rational; 285 })(); // End of the class creation
End of listing