[announce] Numerical tower in JavaScript
John Tobey
This is the first release of javascript-bignum, an ECMAScript implementation of the numerical tower and all associated base library functions defined by R6RS.
https://github.com/jtobey/javascript-bignum
Licensed under the MIT license, file LICENSE.
WHAT IT IS
The Scheme language supports "exact" arithmetic and mixing exact with
inexact numbers. Several basic operations, including add, subtract,
multiply, and divide, when given only exact arguments, must return an
exact, numerically correct result. They are allowed to fail due to
running out of memory, but they are not allowed to return
approximations the way ECMAScript operators may.
For example, adding exact 1/100 to exact 0 one hundred times produces
exactly 1, not 1.0000000000000007 as in JavaScript. Raising 2 to the
1024th power returns a 308-digit integer with complete precision, not
Infinity as in ECMAScript.
This implementation provides all functions listed in the R6RS [1]
Scheme specification, Section 11.7, along with "eqv?" from Section
11.5. ("eqv?" uses JavaScript's "===" to compare non-numbers.)
Known deviations:
* In the JavaScript tradition, most functions ignore extra
arguments. R6RS Section 6.2 requires an &assertion exception in
these cases.
Arcane features such as explicit mantissa widths or complex
transcendental functions, while believed complete, are unoptimized.
IMPLEMENTATION DETAILS
[See https://github.com/jtobey/javascript-bignum for more info.]
Enjoy!
-John
Vitaly Magerya
> Exact arithmetic in your browser!
You seem to use base 10 representation internally. Why not base 2^51?
There should be significant performance gains in that route.
John Tobey
I did not write the big integer library, and the performance meets my
current needs. See the biginteger author's design notes; he chose
base
10 because his application spent the most time in decimal input and
output.
By the way, javascript-bignum outperforms (my somewhat dated version
of)
plt-r6rs by a factor of three in its own test suite, probably due to
my
poor use of plt-r6rs.
Patches are welcome.
Thanks,
-John
Vitaly Magerya
> Patches are welcome.
Get the patch at [1]. With it you can choose any base for internal
representation of BigIntegers. The patch also includes a hack that
while restricting possible bigint bases to powers of 10 improves
performance of decimal input and output to what it was before the
patch.
I run a microbenchmark calculating factorial(2000), it shows 6x
performance improvement in Opera and 13x in Firefox with bigint
base set to 10^7 (with comparable serialization/parsing times).
I did not run the test suite, so caveat emptor.
Note that the patch removes exp10 function, as it makes little sense
now. It can be added back though.
John Tobey
> John Tobey wrote:
> > Patches are welcome.
>
> Get the patch at [1]. With it you can choose any base for internal
> representation of BigIntegers. The patch also includes a hack that
> while restricting possible bigint bases to powers of 10 improves
> performance of decimal input and output to what it was before the
> patch.
> [1]http://tx97.net/~magv/biginteger.js.diff
Terrific work! Do you mind me distributing your patch under the same
license as the original?
Two changes necessary for inclusion:
1. string->number relies on exp10 for parsing decimals with the exact
prefix. Example: "#e1e50". Can you please implement exp10 or find
another solution?
2. The log() method should work on values above Number.MAX_VALUE.
Example: SchemeNumber.fn.log(SchemeNumber.fn.expt("10","1000"))
returns 2302.585092994046, but with log() going through toJSValue
returns NaN.
Thanks,
John
Vitaly Magerya
> Terrific work! Do you mind me distributing your patch under the same
> license as the original?
I don't mind.
> Two changes necessary for inclusion:
>
> 1. string->number relies on exp10 for parsing decimals with the exact
> prefix. Example: "#e1e50". Can you please implement exp10 or find
> another solution?
>
> 2. The log() method should work on values above Number.MAX_VALUE.
> Example: SchemeNumber.fn.log(SchemeNumber.fn.expt("10","1000"))
> returns 2302.585092994046, but with log() going through toJSValue
> returns NaN.
Try [1], I added exp10 back and fixed log. Note that exp10 is slower
than it was before the patch: it requires an extra multiplication
(or division) when it's argument is not divisible by 7.
John Tobey
> John Tobey wrote:
> > Terrific work! Do you mind me distributing your patch under the same
> > license as the original?
>
> I don't mind.
Thank you.
> Try [1], I added exp10 back and fixed log. Note that exp10 is slower
> than it was before the patch: it requires an extra multiplication
> (or division) when it's argument is not divisible by 7.
I think the slowdown is more than offset by the speed gained
elsewhere.
> [1]http://tx97.net/~magv/biginteger.js-2.diff
A problem came up while running the test suite. Here is a small test
case:
BigInteger.divide(1e14-1, 2e7-1)
This takes a very long time to compute, because the following loop
runs millions(?) of times:
do {
var check = a.multiplySingleDigit(guess);
if (check.compareAbs(part) <= 0) {
break;
}
guess--;
} while (guess);
Any ideas?
Best,
-John
Vitaly Magerya
> A problem came up while running the test suite. Here is a small test
> case:
>
> BigInteger.divide(1e14-1, 2e7-1)
That is a very well spotted corner case.
The issue should be fixed in [1]. I feel that the offending loop
could be removed completely, but it would require putting in some
more thought. Currently it executes 1 or 2 cycles on average, so
it shouldn't be a big problem anyway.
John Tobey
> [1]http://tx97.net/~magv/biginteger.js-3.diff
Thanks! I measured 30% less time in the test suite than yesterday.
Besides your patch, I have updated the documentation to include a one-
line description of each Scheme function along with a link to its
specification in R6RS.
CHANGES
1.0.3 - 2011-02-10
* Faster big integer arithmetic, courtesy of Vitaly Magerya.
Approximately 20% test suite speedup.
1.0.2 - 2011-02-10
* Moved argument conversion from internal methods to public
functions. Approximately 10% test suite speedup.
1.0.1 - 2011-02-10
* Support ECMA standard formatting methods: toFixed,
toExponential, toPrecision.
Best regards,
-John