bignum.js
is a Javascript library for doing arbitrary-precision
arithmetic with naturals, integers, rationals, and computable reals.
The library gives an interface for Z
, Q
, and R
as a numeric stack, as
in Lisp. Numbers may be given as Javascript numbers, strings, or
instances of N
, Z
, Q
, and R
.
It is written as a node
module. Simply var bignum = require('./bignum.js');
. In addition to the numeric types, the
module also exposes the following functions:
num(o)
is used to construct a number from objecto
. This is generally unnecessary as the other library functions will construct numbers for you.num
convertsN
toZ
, parses strings, converts Javascript numbers, and returns integers, rationals, and reals as-is.sum(a,b)
anddiff(a,b)
respectively compute the sum and difference ofa
andb
.negate(a)
returns the negative ofa
.abs(a)
returns the absolute value ofa
.prod(a, b)
returns the product ofa
andb
.divMod(a, b)
returns an object with the quotient and remainder asdiv
andmod
, respectively. These satisfy the relationshipdiv * b + mod = a
, withdiv
beinga/b
rounded toward negative infinity. Botha
andb
must be integers.quot(a,b)
computes the quotient ofa
andb
. The result is a rational or real.recip(a)
returnsquot(1, a)
.gcd(a,b)
returns the GCD of integersa
andb
.ipow(a,b)
returnsa
raised to the power ofb
.b
must be a Javascript integer, anda
cannot (yet) be a real number.factorial(a)
returns the factorial ofa
.compare(a,b)
returnssign(a - b)
, withsign(0)=0
.
In this section we describe the implementation of each type.
Natural numbers (N
) are immutable objects wrapping a Uint16Array
.
Numbers are represented base-65536.
Products are right now calculated using the grade-school algorithm, but in the future we will have more efficient algorithms for very large numbers.
Division uses Algorithm D from 4.3.1 of Volume 2 of The Art of Computer Programming, by Knuth.
Methods:
n.toString(base)
returns a string representation of the natural number in a given base (defaults to base 10).
Functions:
N.choose(a, b)
computes the binomial coefficient of natural numbersa
andb
.
An integer (Z
) is an immutable object wrapping an N
and a sign (1
or -1; we use the convention that 0 is positive).
Methods:
z.toString(base)
returns a string representation of the integer in a given base (defaults to base 10).z.toPrecision(digs)
returns a scientific notation representation of the integer with the given number of digits (defaults to 16 digits).
A rational (Q
) is an immutable object wrapping a pair of integers,
the numerator and denominator. We keep the invariant that the
denominator is positive.
Rationals can be created directly from a floating-point number. We use a Farey sequence to obtain the rational with least denominator whose binary expansion matches every bit of the original floating-point number.
Methods:
q.toString(base)
returns a string representation of the rational number a given base (defaults to base 10).q.toPrecision(digs)
returns a scientific notation representation of the rational number with the given number of digits (defaults to 16 digits). The algorithm is base-10 long division.q.toFixed(digs)
is liketoPrecision
, but is given in as a fixed-point string representation.
Functions:
Q.ifrac(a)
returns the integer and fractional part ofa
as an object.ipart
is an integer andfpart
is a rational.Q.cfrac(a)
returns a continued fraction representation ofa
as a list of integers.Q.fromCfrac(cfrac)
returns the rational number represented by the continued fraction representationcfrac
.Q.choose(a, b)
computes the binomial coefficient fora
a rational andb
an integer.
A computable real (R
) is a function which takes a rational number
r
and produces a rational number q_r
such that for any rational
s > r
, |q_r - q_s| < r
. This is equivalent to a Cauchy sequence.
As an optimization, a computable real also memoizes its result, so that the most-accurate result obtained so far will be the one returned no matter the bound.
The algorithms for sums, products, quotients, and the rest are not particularly smart, but are generally direct implementations of textbook epsilon-delta proofs.
There is an algorithm for square roots given in test_bignum.js
, but
it is very naive.
Beware that computable real numbers cannot be compared, since such an operation is not computable. The problem is that, while you can check numbers digit-by-digit for equality, you have no idea how many digits you will have to inspect before the numbers diverge. You can ask whether two numbers are within some positive rational distance from each other, however.
Methods:
r.toFixed(digs)
returns a fixed-point representation of the real number evaluated to the given number of digits past the decimal point.r.toString()
callsr.toFixed(16)
.