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);
        ret = ret.addInt(digit);
    }
    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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s