Source of “ratcalc.js”.
631 lines, 19.6 KBytes.   Last modified 10:22 pm, 17th September 2016 PDT.
1 // Emacs settings: -*- mode: Fundamental; tab-width: 4; -*- 2 3 //////////////////////////////////////////////////////////////////////////// 4 // // 5 // Arbitrary Precision Rational Calculator // 6 // // 7 // Copyright (c) 2011-2013, Andrew Birrell // 8 // // 9 //////////////////////////////////////////////////////////////////////////// 10 11 // Requires the classes "adbab.Bigint" and "adbab.Rational" 12 13 var Bigint = adbab.Bigint; 14 var Rational = adbab.Rational; 15 16 17 // 18 // Evaluating an expression 19 // 20 21 var state = {p:0, q:0, r:0, s:0, t:0, v:0, w:0, x:0, y:0, z:0}; 22 // The values of the variables, indexed by variable name. 23 // Initial values are irrelevant, because "compute" will replace them 24 // with false. In normal running, false means the variable's current 25 // expression hasn't yet been calculated; otherwise the value is a 26 // Rational. The existence of an index in this object defines the 27 // existence of a variable (which should also exist in the HTML). 28 var dependsOn = new Object(); 29 // Dependencies, indexed by variable name. Values are strings with 30 // the concatenation of the (single-character) names of the variables 31 // on which this variable depends. 32 var inProgress = new Rational(); 33 // Flag in "state" to detect cyclic dependencies during "evaluate". 34 var recursive = new Rational("cyclic dependency in expressions"); 35 // Error NaN to propagate detected cyclic dependencies. 36 var emptyExpression = new Rational("empty expression"); 37 // Distinguished error NaN for the empty expression 38 39 var prio = { // operator priorities for the evaluator; constant 40 "(": 0, "BOF": 0, 41 ",": 1, 42 "+": 2, "-": 2, 43 "*": 3, "/": 3, "%": 3, 44 "^": 4, 45 "e": 5, "E": 5, 46 ")": 6, 47 "unary": 7 48 }; 49 50 function squish(vStack, opStack, opPrio, min, m) { 51 // Evaluate stacked operator(s) with priority >= "min". 52 // 53 // The right operand (if any) of the top operator is currently at the 54 // top of the value stack. Calls "squish" recursively to evaluate the 55 // left operand (if any). Leaves the result on the top of the value 56 // stack. Close parenthesis behaves like an operator with only a left 57 // operand, and with a required preceding open parenthesis operator. 58 // 59 // If "m", there's an opportunity to use modular arithmetic. 60 // 61 while (opPrio[opPrio.length-1] >= min) { 62 var op = opStack.pop(); 63 var thisPrio = opPrio.pop(); 64 if (op == ")") { 65 squish(vStack, opStack, opPrio, 1); 66 if (opStack.pop() != "(") alert("missing \"(\""); 67 opPrio.pop(); 68 } else if (thisPrio == prio["unary"]) { 69 var right = vStack.pop(); 70 if (right.isPair) { 71 if (op == "gcd") { 72 if (!right.a.isInteger() || !right.b.isInteger()) { 73 vStack.push(new Rational( 74 "gcd requires integer operands")); 75 } else { 76 var res = new Rational(); 77 res.num = right.a.num.gcd(right.b.num); 78 vStack.push(res); 79 } 80 } else if (op == "inverse") { 81 if (!right.a.isInteger() || !right.b.isInteger()) { 82 vStack.push(new Rational( 83 "inverse requires integer operands")); 84 } else { 85 var res = new Rational(); 86 res.num = right.a.num.inverse(right.b.num); 87 vStack.push(res); 88 } 89 } else { 90 vStack.push(new Rational("unexpected \",\"")); 91 } 92 } else if (right.num.NaN) { 93 vStack.push(right); 94 } else if (op == "gcd" || op == "inverse") { 95 vStack.push(new Rational(op + " requires two operands")); 96 } else if (op == "+") { 97 vStack.push(right); 98 } else if (op == "-") { 99 vStack.push(right.negate()); 100 } else if (op == "sign") { 101 vStack.push(new Rational(right.compare(Rational.zero))); 102 } else if (op == "abs") { 103 vStack.push(right.num.neg ? right.negate() : right); 104 } else if (op == "floor") { 105 vStack.push(right.floor()); 106 } else if (op == "round") { 107 vStack.push(right.round()); 108 } else if (op == "log10") { 109 vStack.push(new Rational(right.compare(Rational.zero) <= 0 ? 110 "log10 of 0 or negative" : 111 right.log10())); 112 } else if (op == "random") { 113 if (!right.isInteger() || right.num.neg) { 114 vStack.push(new Rational( 115 "random requires a positive integer operand")); 116 } else { 117 var res = new Rational(); 118 res.num = right.num.randomLT(); 119 vStack.push(res); 120 } 121 } else if (op == "prime") { 122 if (!right.isInteger() || right.num.neg) { 123 vStack.push(new Rational( 124 "prime requires a positive integer operand")); 125 } else if (right.num.compare(new Bigint(2048)) > 0) { 126 vStack.push(new Rational( 127 "too many bits requested for prime")); 128 } else if (right.num.compare(new Bigint(2)) < 0) { 129 vStack.push(new Rational( 130 "too few bits requested for prime")); 131 } else { 132 var n = Number(right.num.toString()); 133 var res = new Rational(); 134 res.num = Bigint.prime(n); 135 vStack.push(res); 136 } 137 } else { 138 vStack.push(new Rational( 139 "unknown unary operator \"" + op + "\"")); 140 } 141 } else { // binary operator 142 var right = vStack.pop(); 143 var nextM = (op == "%" && right.isInteger() ? right.num : 144 (op == "*" ? m : false)); 145 squish(vStack, opStack, opPrio, thisPrio, nextM); 146 var left = vStack.pop(); 147 if (left.isPair || right.isPair) { 148 vStack.push(new Rational("unexpected \",\"")); 149 } else if (left.num.NaN) { 150 vStack.push(left); 151 } else if (right.num.NaN) { 152 vStack.push(right); 153 } else if (op == ",") { 154 vStack.push({a: left, b: right, isPair: true}); 155 } else if (op == "+") { 156 vStack.push(left.add(right)); 157 } else if (op == "-") { 158 vStack.push(left.sub(right)); 159 } else if (op == "*") { 160 vStack.push(left.mul(right)); 161 } else if (op == "/") { 162 vStack.push(left.div(right)); 163 } else if (op == "%") { 164 vStack.push(left.mod(right)); 165 } else if (op == "^") { 166 var prevOp = opStack[opStack.length-1]; 167 if (m && prevOp != "/" && prevOp != "%" && 168 left.isInteger() && right.isInteger()) { 169 var res = new Rational(); 170 res.num = left.num.pow(right.num, m); 171 vStack.push(res); 172 } else { 173 vStack.push(left.pow(right)); 174 } 175 } else if (op == "e" || op == "E") { 176 vStack.push(left.mul((new Rational(10)).pow(right))); 177 } else { 178 vStack.push(new Rational( 179 "unknown binary operator \"" + op + "\"")); 180 } 181 } 182 } 183 } 184 185 function evaluate(exprID, expr) { 186 // Evaluate given expression and return the value, or an error string, 187 // or the distinguished value "recursive", using standard expression 188 // syntax. Supports built-in functions, treated as unary operators. 189 // 190 // Also sets the expression's dependencies. 191 // 192 // This operates in two phases. First it performs lexical analysis and 193 // syntax checking, leaving its results on a trio of stacks. This first 194 // phase replaces variable references with the variable's computed value 195 // (detecting cyclic dependencies). The syntax is very basic, with no 196 // operator priorities (priorities are recorded, but not acted upon). 197 // The second phase takes the resulting stacks and applies "squish" to 198 // do the actual computations. 199 // 200 // This separation enables some complexities, like optimizing a*b^c%d 201 // into modular arithmetic during "squish". It also avoids performing 202 // any computation if there's a syntax error, or if any of the variable 203 // references evaluates to NaN. The complete dependencies are 204 // accumulated even when a referenced variable is NaN. 205 // 206 // expression ::= value | value binOp expression 207 // value ::= ( expression ) | unaryOp value | operand 208 // operand ::= number | variable 209 // "number" is as defined by "new Rational"; "variable" is [g-z] 210 // "binOp" includes "," and "e"; "unaryOp" includes built-in functions 211 // 212 dependsOn[exprID] = ""; 213 var foundNaN = false; // record if any operands are NaN 214 var vStack = new Array(); 215 var opStack = new Array(); 216 var opPrio = new Array(); 217 var expectValue = true; 218 var nesting = 0; 219 opStack.push("BOF"); 220 opPrio.push(prio["BOF"]); 221 expr = expr.toLowerCase(); 222 expr = expr.replace(/\/\/[^\n]*/g, ""); 223 expr = expr.replace(/\s/g, ""); 224 if (expr == "") return emptyExpression; 225 while (true) { 226 var matches; 227 if (expectValue) { 228 // Require possibly empty sequence of "(" or unary operators, 229 // followed by a number or a variable reference. 230 // 231 while (matches = expr.match( 232 /^([-+(]|sign|abs|floor|round|log10|gcd|inverse|random|prime)/i)) { 233 // unary operator or function 234 var unary = matches[0]; 235 expr = expr.substr(unary.length); 236 if (unary == "(") nesting++; 237 opStack.push(unary); 238 opPrio.push(prio[unary == "(" ? "(" : "unary"]); 239 } 240 var operand; 241 if (matches = expr.match(/^[g-z]/i)) { 242 // variable reference 243 var id = matches[0]; 244 expr = expr.substr(id.length); 245 operand = state[id]; 246 if (operand == inProgress) { 247 dependsOn[exprID] += id; 248 return recursive; 249 } else if (operand === false) { 250 computeVariable(id); 251 operand = state[id]; 252 } else if (!operand) { 253 return new Rational( 254 "variable \"" + id + "\" does not exist"); 255 } 256 dependsOn[exprID] += id + dependsOn[id]; 257 if (operand == recursive) return operand; 258 if (operand.num.NaN) foundNaN = id; 259 } else if (matches = expr.match( 260 /^0x[0-9a-f]+|^[0-9]*\.[0-9]*|^[0-9a-f]+/i)) { 261 // constant 262 var numStr = matches[0]; 263 expr = expr.substr(numStr.length); 264 operand = new Rational(numStr); 265 } else if (expr == "") { 266 return new Rational("unexpected end of expression"); 267 } else { 268 return new Rational( 269 "number or name expected before \"" + expr + "\""); 270 } 271 vStack.push(operand); 272 expectValue = false; 273 } else { 274 // Require EOF, or binary operator, or ")" 275 // 276 if (expr == "") { // EOF 277 break; 278 } else if (matches = expr.match(/^([-+*/%^e,)]|mod)/i)) { 279 // binary operator 280 var binary = matches[0]; 281 expr = expr.substr(binary.length); 282 if (binary == "mod") binary = "%"; 283 if (binary == ")") { 284 if (nesting == 0) return new Rational("excess \")\""); 285 nesting--; 286 } 287 opStack.push(binary); 288 opPrio.push(prio[binary]); 289 expectValue = (binary != ")"); 290 } else { // implicit multiplication 291 opStack.push("*"); 292 opPrio.push(prio["*"]); 293 expectValue = true; 294 } 295 } 296 } 297 if (nesting != 0) return new Rational("missing \")\""); 298 299 // Perform the computations, now that there are no syntax errors. 300 // 301 if (foundNaN) return new Rational("referenced variable \"" + foundNaN + 302 "\" is NaN"); 303 var start = (new Date()).getTime(); 304 squish(vStack, opStack, opPrio, 1); 305 var elapsed = (new Date()).getTime() - start; 306 if (opStack.pop() != "BOF") alert("mangled opStack"); 307 if (vStack.length != 1) alert("mangled vStack"); 308 var res = vStack.pop(); 309 if (res.isPair) res = new Rational("unexpected \",\"") 310 res.elapsed = elapsed; 311 return res; 312 } 313 314 315 // 316 // GUI 317 // 318 319 var evaluated = new Object(); 320 var displayFormat; 321 var displayDigits; 322 323 function toFixed(neg, posX, float) { 324 // Internal function for setValue: convert to string as fixed point. 325 // 326 var factor = Rational.pow10(displayDigits).num; 327 var denom = posX.denom; 328 var scaled = posX.num.mul(factor).add(denom.div(Bigint.two)).div(denom); 329 var intPart = scaled.div(factor).toString(); 330 if (float && intPart.length > 1) return false; // float rounds to 10 331 var frPart = scaled.mod(factor).add(factor).toString().substr(1); 332 return (neg ? "-" : "") + 333 intPart + 334 (displayDigits > 0 ? "." : "") + 335 frPart; 336 } 337 338 function setValue(id, x, value, checkPrime) { 339 // Set the number (or false) and current text value for "id" and 340 // update the display. Optionally do primality check too. 341 // 342 var elt = document.getElementById("value" + id.toUpperCase()); 343 state[id] = x; 344 elt.title = ""; 345 document.getElementById("expr" + id.toUpperCase() + "time" 346 ).innerHTML = ((x && typeof(x.elapsed) == "number" ? x.elapsed : 347 0)/1000).toFixed(3) + "s"; 348 if (value === false) { 349 // This is really Rational.prototype.toString 350 // 351 var posX = x; 352 var neg = posX.num.neg; 353 if (neg) posX = posX.negate(); 354 if (x == emptyExpression) { 355 value = ""; 356 } else if (x.num.NaN) { 357 value = x.num.toString(); 358 } else if (displayFormat == "fixed") { 359 value = toFixed(neg, posX, false); 360 elt.title = "" + ( 361 (neg ? -1 : 0) + 362 (displayDigits == 0 ? 0 : -1) + 363 value.length) + 364 " digits"; 365 } else if (displayFormat == "scientific") { 366 var exponent = (posX.compare(Rational.zero) == 0 ? 0 : 367 posX.log10()); 368 var digits; 369 for (var i = 0; i < 2; i++) { 370 digits = 371 toFixed(neg, posX.div(Rational.pow10(exponent)), true); 372 if (digits) break; // else correct for rounding to 10 373 exponent++; 374 } 375 value = digits + "e" + exponent; 376 } else if (displayFormat == "magnitude") { 377 // The distinctive goal of this format is rendering speed 378 if (posX.compare(Rational.zero) == 0) { 379 value = id + " = 0"; 380 } else { 381 var mag = posX.log10(); 382 value = "10^" + mag + " <= |" + id + "| < 10^" + (mag+1); 383 } 384 } else { 385 var hex = (displayFormat == "hex"); 386 var nPart = posX.num.toString(hex); 387 var dPart = posX.denom.toString(hex); 388 if (dPart == "1") dPart = ""; 389 value = (neg ? "-" : "") + 390 (hex ? "0x" : "") + nPart + 391 (dPart ? "/" + (hex ? "0x" : "") + dPart : ""); 392 elt.title = "" + (nPart.length + dPart.length) + " digits"; 393 if (hex) { 394 var hexValue = {0:0, 1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7, 395 8:8, 9:9, a:10, b:11, c:12, d:13, e:14, f:15}; 396 var ms = hexValue[nPart.charAt(0)]; 397 var msBits = (ms >= 8 ? 4 : ms >= 4 ? 3 : ms >= 2 ? 2 : 1); 398 elt.title += ", " + (msBits + 4*(nPart.length-1)) + 399 (x.isInteger() ? " bits" : "-bit numerator"); 400 } 401 } 402 } 403 var primality = (checkPrime ? 404 (x.num.isPrime() ? "[prime]\n" : "[not a prime]\n") : ""); 405 elt.value = primality + value; 406 } 407 408 function displayMode() { 409 // Update the display mode state 410 // 411 var elt = document.getElementById("digitsLine"); 412 displayFormat = document.getElementById("display").value; 413 if (displayFormat == "rational" || displayFormat == "magnitude" || 414 displayFormat == "hex") { 415 elt.style.visibility = "hidden"; 416 } else { 417 elt.style.visibility = "visible"; 418 var eltD = document.getElementById("digits"); 419 eltD.focus(); 420 displayDigits = Number(eltD.value); 421 if (displayDigits === 0 || displayDigits > 0) { 422 } else { 423 alert("The number of digits to display isn't " + 424 "a positive integer. Using 3 instead"); 425 displayDigits = 3; 426 } 427 } 428 for (var id in state) { 429 var value = state[id]; 430 if (value && value != inProgress) setValue(id, value, false); 431 } 432 return true; 433 } 434 435 function checkPrimesAsync() { 436 // Called asynchronously, to allow a screen repaint. 437 // 438 for (var id in state) { 439 var value = state[id]; 440 if (value && value != inProgress) { 441 if (!value.num.NaN && value.isInteger() && !value.num.neg) { 442 setValue(id, value, false, true); 443 } 444 } 445 } 446 } 447 448 function checkPrimes() { 449 // Update the display with primality checks 450 // 451 for (var id in state) { 452 var value = state[id]; 453 if (value && value != inProgress) { 454 if (!value.num.NaN && value.isInteger() && !value.num.neg) { 455 setValue(id, value, "Testing"); 456 } 457 } 458 } 459 setTimeout(checkPrimesAsync, 50); 460 return false; 461 } 462 463 function computeVariable(id) { 464 // Read expression for "id", evaluate it, and update its cached value. 465 // 466 var expr = document.getElementById("expr" + id.toUpperCase()).value; 467 evaluated[id] = expr; 468 setValue(id, inProgress, ""); 469 var num = evaluate(id, expr); 470 setValue(id, num, false); 471 } 472 473 function computeAsync() { 474 // Do the computations we've decided are needed. 475 // Called asynchronously, to allow a screen repaint. 476 // 477 for (var id in state) { 478 if (!state[id]) computeVariable(id); 479 } 480 } 481 482 function compute() { 483 // Fix up values to match expressions that have changed; also recomputes 484 // values dependent on recomputed values. Tries to avoid repeating 485 // computations. 486 // 487 for (var id in state) { 488 var elt = document.getElementById("expr" + id.toUpperCase()); 489 if (elt.value !== evaluated[id]) { 490 for (var d in dependsOn) { 491 if (dependsOn[d].indexOf(id) >= 0) { 492 setValue(d, false, "Computing"); 493 } 494 } 495 setValue(id, false, "Computing"); 496 } 497 } 498 setTimeout(computeAsync, 50); 499 return false; 500 } 501 502 function recomputeOne(id) { 503 // Recompute one expression. Pointless unless the expression is 504 // non-deterministic 505 // 506 evaluated[id] = false; 507 compute(); 508 return false; 509 } 510 511 function recomputeAll() { 512 // Recompute everything from scratch. Pointless unless at least one 513 // expression is non-deterministic. 514 // 515 evaluated = new Object(); 516 compute(); 517 } 518 519 function setExpr(id, expr) { 520 // Set the UI for one expression, but don't recompute yet. 521 // 522 document.getElementById("expr" + id.toUpperCase()).value = expr; 523 evaluated[id] = false; 524 } 525 526 function eraseAll() { 527 // Set the UI for all expressions empty, but don't recompute yet. 528 // 529 for (var id in state) setExpr(id, ""); 530 } 531 532 function eraseAndRecomputeAll() { 533 // Set all expressions empty and recompute 534 // 535 eraseAll(); 536 compute(); 537 return false; 538 } 539 540 function zp() { 541 // Set up a demo of using the calculator for arithmetic mod p 542 // 543 eraseAll(); 544 setExpr("p", "prime(256)"); 545 setExpr("q", "random(p)"); 546 setExpr("r", "random(p)"); 547 setExpr("s", "(q + r) mod p"); 548 setExpr("t", "(s - r) mod p - q"); 549 setExpr("v", "q * r mod p"); 550 setExpr("w", "v * inverse(r,p) mod p - q"); 551 setExpr("x", "q^p mod p - q\n" + 552 "// Fermat's little theorem"); 553 setExpr("y", "26084932307537183566978409438381212" + 554 "0359260783810157225730623388382401\n" + 555 "// a Carmichael number (as is 561)"); 556 setExpr("z", "p^y mod y - p mod y"); 557 compute(); 558 return false; 559 } 560 561 function rsa() { 562 // Set up a demo of using the calculator for RSA 563 // 564 eraseAll(); 565 setExpr("p", "prime(1024)"); 566 setExpr("q", "prime(1024)"); 567 setExpr("r", "pq\n" + 568 "// modulus"); 569 setExpr("s", "inverse(t,(p-1)(q-1)/gcd(p-1,q-1))\n" + 570 "// secret exponent"); 571 setExpr("t", "65537\n" + 572 "// public exponent"); 573 setExpr("v", "random(r)\n" + 574 "// plain text"); 575 setExpr("w", "v^t mod r\n" + 576 "// cipher text"); 577 setExpr("x", "w ^ (s mod (p-1)) mod p\n" + 578 "// ingredient of Chinese remainder theorem"); 579 setExpr("y", "w ^ (s mod (q-1)) mod q\n" + 580 "// ingredient of Chinese remainder theorem"); 581 setExpr("z", "y + q * (inverse(q,p) * (x - y) mod p)\n" + 582 "// decrypted cipher text; faster than w^s mod r"); 583 compute(); 584 return false; 585 } 586 587 function sosp() { 588 // Set up a demo of using the calculator to evaluate a polynomial 589 // 590 eraseAll(); 591 setExpr("p", 592 "// p(x) = number of papers at xth SOSP =\n" + 593 "-(83821 x^22)/28820531481477120000\n" + 594 "+(320809 x^21)/417068915687424000\n" + 595 "-(66475823 x^20)/695114859479040000\n" + 596 "+(4338435337 x^19)/583896481962393600\n" + 597 "-(1849904461 x^18)/4573124075520000\n" + 598 "+(420030824483 x^17)/25609494822912000\n" + 599 "-(27091495095317 x^16)/52725430517760000\n" + 600 "+(11511333943019 x^15)/903864523161600\n" + 601 "-(347405792013773 x^14)/1369491701760000\n" + 602 "+(37072271924991337 x^13)/9038645231616000\n" + 603 "-(98606450169909287 x^12)/1820972482560000\n" + 604 "+(27128883118544321 x^11)/46352026828800\n" + 605 "-(20995623275634019511 x^10)/4055802347520000\n" + 606 "+(527419324858148273 x^9)/14122883174400\n" + 607 "-(205573061982300533887 x^8)/941525544960000\n" + 608 "+(115732590383211642707 x^7)/112983065395200\n" + 609 "-(4345760444244765781579 x^6)/1143281018880000\n" + 610 "+(1458110911193252552053 x^5)/133382785536000\n" + 611 "-(31803508532623224012523 x^4)/1343932611840000\n" + 612 "+(8122865748074690897 x^3)/219988969200\n" + 613 "-(50019460551210279341 x^2)/1290601952640\n" + 614 "+(5621606296239911 x)/232792560\n" + 615 "-6620660"); 616 setExpr("x", "23\n// 2011, Cascais"); 617 compute(); 618 return false; 619 } 620 621 622 // 623 // Initialization 624 // 625 626 function init() { 627 displayFormat = document.getElementById("display").value 628 displayDigits = Number(document.getElementById("digits").value); 629 compute(); 630 document.getElementById("exprP").focus(); 631 }
End of listing