Multiple Precision in JavaScript: Rational Arithmetic II

Elementary Functions

While trying to implement even the most basic elementary functions, like square root, nth-root and the exponential function I had to admit that the Bigrational library is just too slow. Square and nth-root work ok, but the exponential function is of not much use with that low speed it needs floating point arithmetic. Yes, I am working at it.

But all of that is no reason to drop the whole mess completely as you might have seen if you took a look at the Bigrational library.

The root finding functions are quite obvious (I hope đŸ˜‰ ), no tricks involved: they just take the integer roots of numerator and denominator respectively and find the fractional part with some rounds of Newton-Raphson.

Armed with the nth-root we can do the power function with the help of

${\displaystyle{ \left(\frac{a}{b}\right)^\frac{x}{y} = \left( \left(\frac{a}{b}\right)^x\right) ^ \frac{1}{y} = \left(\left(\frac{a}{b}\right)^\frac{1}{y}\right) ^ x }}$

It is a good question when to use which form; if you exponentiate first you will have larger numbers but that means you will also have some meat to get the nth-root from if the denominator of the exponent $y$ is large. Because of that open question the implementation of a full power function for the Bigrational is not done yet.

Exponential Function $e^\frac{a}{b}$

It seems as if I already dumped what I had. It was just way too slow. I might try it again one day but I doubt it.
One alternative is to exponentiate $e$. You can compute $e$ as a constant to some medium large precision (quite fast up to about 1000 decimal digits) with the following program:

function expoone(digs) {
var n = digs;
var a = new Array(n);
var digit = 0;
var pow = 7;
var base = Math.pow(10, pow);
var limit = n - (Math.ceil(n / pow));
var ret = new Bigint();
a[0] = 0;
var b = []
while (--n){
a[n] = 1;
}
// first digit
a[1] = 2;
if (digs < 40) {
limit -= 1;
} else if (digs < 30) {
// 2718281828459045235360287471352 has 31 correct decimal digits
ret.dp = [59311638, 3122883, 39162420, 1690117, 47500213, 19];
ret.used = ret.dp.length;
return ret;
}
while (digs > limit) {
digs--;
n = digs;
while (--n) {
a[n] = digit % n;
digit = base * a[n - 1] + Math.floor(digit / n);
}
ret = ret.mulInt(base);
}
return ret;
}


(Idea shamlessly stolen from Xavier Gourdon, who wrote a very small (117 bytes!) C-program using this algorithm.)
We can build a rational from this constant by adding the denominator $10^{n-1}$. But beware: the above function returns more digits than it got asked for, at least one, so count the digits before the calculation of the numerator.

// returns 1 (one) if *this* is zero
Bigint.prototype.digits = function() {
var log102 = Math.log(10) / Math.log(2);
var log2 = this.highBit();
return Math.floor(log2 / log102) + 1;
};


Well…

…sorry, but this is just the end of the arithmetic with rational numbers, I have to work on my implementation of Bigfloats now.

The basics are implemented, it is just the I/O that gives trouble, but that was expected.