APIC (Arbitrary Precision Integer Calculator) version: 0.9, 2007-04-10 *** AUTHOR Marcus Uneson 2007 Any reports on problems due to inferior browser implementations from Microsoft will be silently ignored; however, other feedback is very welcome. Reach me at earcus.uneson@ling.lu.sm (exchange first and last letter) *** LICENSE ################################################################################ ### Copyright (c) 2007 Marcus Uneson, marcus.uneson@ling.lu.se ### ### This program is free software; you can redistribute it and/or modify ### it under the terms of the GNU General Public License as published by ### the Free Software Foundation; either version 2 of the License, or ### (at your option) any later version. ### ### This program is distributed in the hope that it will be useful, ### but WITHOUT ANY WARRANTY; without even the implied warranty of ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ### GNU General Public License for more details. ################################################################################ *** ABSTRACT APIC, short for Arbitrary Precision Integer Calculator, is (as if you wouldn't have guessed) a calculator where the limits of your calculations are (mostly, but see "Limitations" below) set by your available RAM, CPU cycles, and patience. In practice, of course, none of those three is really arbitrary, especially considering that APIC is written in JavaScript (which isn't primarily intended for mathematics; among other things, it is interpreted, it lacks real arrays, and it only has one undifferentiated 'number' type). On the other hand, there are advantages to the language as well -- for instance, "installation" couldn't be easier; there are no network delays; and the program consumes client cpu cycles only. (As an aside, let me state that JavaScript is a surprisingly cool language, once you get a bit into it. It happily mixes very interesting design features (such as higher-order functions and a truly original prototype-based OO model) with rather unfortunate ones (for instance regarding scoping rules and operator overloading, and an unnecessarily large influence from Java in syntax and keywords). I recommend Douglas Crockford's JavaScript pages at http://www.crockford.com/javascript/.) All in all, calculations involving a few thousand of decimal digits are mostly fine, and the number theoretic functions can at least serve as demos. APIC currently does not employ any parsing of expressions and has no stack: all manipulations and operations are activated via buttons and performed on integer numerals specified in the input windows. The original idea (but no code) for this program was borrowed from a similar program by E Martin III (http://www.petting-zoo.org/Calculator.html). In contrast to Martin's program, APIC handles integers only, but is several orders of magnitude faster, in constants as well as asymptotically (exponential vs quadratic, in some cases). *** TOOL TIPS If your browser shows the "title" attribute as a tool tip, you will see it when hovering over a button. Some functions have fast access keys (also shown in tool tips). You could move keyboard focus to the m, n, r windows with [alt+m], [alt+n], [alt+r]. (These three should really show up in some tool tip as well -- haven't decided on which *** PERFORMANCE As an extremely rough comparison, the following calculations will take on the order of 5-15 seconds on a 1GB/1GHz Wintel laptop with Firefox 1.5.0. expression no.digits factorial(2400) 7073 square(R(5000)) ~10000 combination(10000, 3000) 2651 permutation(5000, 1000) 3653 fibonacci(35000) 7315 power(R(3), 3000) ~9000 power(R(100), 100) ~10000 multiplication (R(25000), R(1000) ~26000 floorSqrt(R(2200)) 1284 where R(n) is some random integer with n digits. On my machine, Opera and IE are considerably faster (a factor 2-3). Addition and subtraction can handle numbers of half a million digits or more; for these operations, I/O dominates calculation time. *** LIMITATIONS There are also some arbitrary limits on input size. As of version 0.9, they are (with n_max = 10^BIGINT_BASE): factorization, prime number testing: factors higher than n_max will not be tried; if a number hasn't been completely factorized at that point, an error message is shown. factorial (n!), fibonacci (fib(n)): n < n_max primes <= n: n < n_max None of those limitations should affect any practical computations (that is: if they were removed, some computations that now raise an error message, either immediately or after some time, would instead be runnable, but with little hope of being finished in the lifetime of your computer, or yourself). *** IMPLEMENTATION NOTES The implementations of the basic operations are simple, though not naive (i.e., exponential). Basically, they're the well-known schoolhouse algorithms (digit-by-digit multiplication, long division) or CS standard methods (exponentiating by squaring, and a variant of it used for fibonacci). FloorSqrt uses Newton-Raphson iteration. For several operations, there are faster algorithms known, for instance, there is Karatsuba's O(n^1.59) divide-and-conquer algorithm for multiplication (compared to the current schoolbook O(n^2). In the case of multiplication, the benefits would furthermore be inherited by many other operations. However, although I might give it a go one day, the severe limitations of the platform make the additional effort somewhat less appetizing. For specific tasks, you would anyway go to Matematica, Matlab, Octave or similar; for embedded applications, you would use some good library (if you need really fast arbitrary-precision arithmetic, you should have a look at GNU multiple precision arithmetic library, http://gmplib.org/.) Arbitrarily large integers will use arbitrarily large representations. The logical way to do this is to use arrays to represent the numbers in some base with array elements for individual digits. The base should be chosen as large as possible while still guaranteeing exact arithmetic for the elementary operations (in particular multiplication). The current program tries to gauge this optimal base by comparing the (stringified) results of calculations of successively incremented squares with the correct answers represented as strings -- ugly, but it seems to work (as for the JavaScript implementations available on 32-bit WinXP in 2007, the optimal base is 10^7 for the implementations I've tested). If it doesn't work, you could set BIGINT_BASE manually instead -- start with 1 and calculate some big number, perhaps 1000!, then repeatedly increment the base until you see signs of overflow in forms of changes in the result.. JavaScript uses hash tables to emulate arrays. While lookup still is O(1), this is much slower (and more memory-expensive) than 'real' arrays. On the other hand, the hash representation does away with the need of putting arbitrary limits in advance, and for simple purposes, it may be fast enough. *** TODO too much shared code in factorize and primality testing -- both could be expressed in smallestFactorLargerThanI(n,i) access keys should be mentioned in tool tips Stirling(m, n) of first and second kind? *** REVISION HISTORY 2007-04-10 published first version (0.9) on www.ling.lu.se/persons/Marcusu/math/bigintcalculator.html reworked isPrime as smallestFactor, which will return the smallest factor of n less than n itself (and thus can be used for primality testing, too) 2007-04-08 tried object inheritance for overriding bigint helper methods (l.) in lsmall objects (lsmall.). This is useful for transparent changes in representation for numbers which do and do not fit in base * base, and seems to be an idiomatic way to solve several transparency-related problems. (But it is difficult to find good examples of JavaScript's prototype-based object orientation -- most js in existence is very poor, and even the better written programs seem to hang on unnecessarily close to traditional class-based OO.) 2007-04-07 architecture of "memory" functions improved representation now allows factorization on arbitrary large numbers experimented with special case factorization for numbers which fit in the base but decided it isn't worth the effort for the moment. More functional style? added floorSqrt with Newton-Raphson iteration added isSquare 2007-04-06 added memories for m and n persistent bug in factorization -- added representation check on top-level (i.e., exported) functions; most top-level functions are now wrappers for checking of range, sign, special cases etc, and the actual calculation is performed by helper functions, not exported but available to other functions as well 2007-04-05 added button r = m x n to repeat the string in the m window n times, mostly useful for constructing big test numbers added tool tips facility when hovering mouse over button added elapsed wallclock time in status window added element count for lists in status window implemented fibonacci(n) 2007-04-04 implemented divMod -- surprisingly tricky; this is a critical operation for many others implemented gcd/lcm (trivial, given divMod) implemented sieve of Eratosthenes for prime listing up to n; currently n must be within base 2007-04-03 added isprime, slow and naive (built on primes < n) but at least something to work on did some tests on list.unshift vs list.push (unshift is linear in list.length and slow at that; push is constant) and concat vs push + flatten_once (the latter is much faster); rewrote accordingly. Unshift > 1 time should probably always be avoided (push + reverse)? can't get keyboard shortcuts to transfer control to I/O fields (m, n, r); it works with the ugly hardcoding