Implement huge number exponentiation/factorial

[bloc97]

Currently doing 50000^100000 or 30000! will cause the CAS to hang, but if exponentiation approximation by logarithms and Stirling's factorial approximation are implemented, the CAS should be able to handle those big numbers.

x^y ~= 10^(y * log10(x))

if y * log10(x) is a non-integer number, we can approximate the number by

10^(fractional part) 10^floor(ylog10(x))

The exponential part can then be expressed symbolically. eg. 50000^70000 could then be displayed as ~= 7.9488357 * 10^328927

[davidedc]

Sounds good. I wonder whether this approximation should only happen with float() (or when a float appears in the expression, which triggers numeric evaluation too). Once that happens though, since floats are "toxic", all results would be numeric from then on, we'd need a way to promote a float into a non-float in case one wants to use the result in non-numeric ways. There is a routine I'm working on to guess a symbolic form for a float, could use that.

[murkle]

@davidedc do you know of the PSLQ Algorithm? That is very powerful way to "guess" the float -> exact conversion eg (sqrt(2)+1)/2, pi^2+1 http://mathworld.wolfram.com/PSLQAlgorithm.html

[davidedc]

yes eventually that's the ambition. For step 1, there is a surprising lot that can be guessed with quick and un-elegant trial and error routines. If anyone wants to take on PSLQ though...

[davidedc]

in fact approxratio(7.9488357 * 10^328927) already works (gives 24236/3049*10^328927). Works in zeno branch, I don't think it works in master yet. (In fact I think Michael @murkle gave me pointers to approxratio routine).

[bloc97]

This does not need to be a float, since 10^(fractional part) eg. 10^(0.8542786512636754831467...) can be done very fast, even as a bignumber. Does Algebrite currently support choosing the precision for logs and exponentiation?

[bloc97]

Something like this works for me right now...

const Algebrite = require("Algebrite");

const exp = "90000000^8000000";
let result = "";

if (exp.search(/\^\d\d\d\d\d/) > -1) { //if the exponent is bigger than 9999.
                                                           //matches any string that contains ^nnnnn
    console.log("Infinite precision arithmethic would take too long, falling back to approximation.")

    const base = exp.slice(0, exp.indexOf("^"));
    const exponent = exp.slice(exp.indexOf("^")+1, exp.length);

    const exponentb10 = Math.log10(base) * exponent;

    const significand = Math.pow(10, exponentb10%1); //This part can allow choosing precision by using bignumber
    const base10 = Math.floor(exponentb10);

    result = significand + "e" + base10;

} else {
    result = Algebrite.run(exp).toString();
}
console.log(result); //Outputs 1.1899113297459072e63633940

[davidedc]

@bloc97 nice, I'll use this under MIT and credit if it's OK.

Yes sorry by float I mean: Algebrite goes into "numeric" mode (using JS Numbers) only when the expression contains a float() call or contains a number with a decimal point plus a few other cases such as when using nroots. Otherwise, it returns symbolic results (which are expression trees containing rationals as long-integer num/denom pairs, constants such as PI and E and all the operations such as SQRT etc.).

So I'm thinking this approximation should probably only kick-in when doing something like float(90000000^8000000) or 90000000.0^8000000.0 or analogous, and left as-is (unevalled) otherwise.

No there is no arbitrary precision in numerical calculations (yet), floats are just JS Numbers at the moment (i.e. the 64 bits floats sometimes called doubles).

[bloc97]

Sure, but the regex was hacked in and not really robust, if someone typed in 500 ^ 60000 it wouldn't work, and it would also break if someone did 500^500^500000, so it would be best to parse the input and simplify it as one single operation before doing regex. Perhaps you already have a solution to this within Algebrite itself?

[davidedc]

ah yes sure. I think that a check when evalling the exponential operator should be enough, I'll try something.

[Qix-]

Try this:

/\^\s*((?:\d{5,}(?:\.\d*)?)|(?:\d{5,}?(?:\.\d*)))/g

Test it here.

[davidedc]

just to give a heads up: while the regex solution works great for the routine above that lives "outside" of the Algebrite core, the solution from "within" the Algebrite core will just check the size of the two numbers with the available bigint comparison operators (or the existing rational number comparison operators)

[Qix-]

Even better :)