Fails with big modular expressions

[fcnjd]

First, thank you for creating this great library, it helps me a lot in my software I'm currently building and is very easy to use. I don't want to be annoying here, but came across some results which might be misleading here.
Describe the bug
MathJS produces wrong results when using modular expressions with big numbers in the base or exponent.

To Reproduce
Evaluate for example the following expression (I tried in my own code, as well as the online demo on mathjs.org):

(7^46)%47

As a result, 0 is shown. However, Because of Fermat's little theorem, this is supposed to be 1.
With smaller exponents, e.g. (7^10)%11 the result 1 is correctly calculated however.
Occasionally it can also output negative numbers, which aren't part of that group:

(7^23)%47

returns -4096, which is obviously not part of the group of numbers modulo 47.
Can you please look at that? Thanks in advance for your help.

[gwhitney]

What's going on here is that these exponential expressions with even medium-sized exponents are producing very large intermediate values that exceed the range in which JavaScript's built-in number type (IEEE 64-bit floating point numbers) can precisely represent each distinct integer. Hence, the result of e.g. 7^46 is a floating point number approximately equal (with 53 bits of accuracy in the mantissa) to seven raised to the 46th power, but considering that representation as a specific integer (which is not really appropriate), it is a different integer which does not have the correct residue mod 47.

There are various possible solutions/workarounds that one can use to address this:

• You can configure the mathjs expression parser to default to interpreting numeric input as the JavaScript bigint type, e.g.:

import {create, all} from 'mathjs'
const math = create(all, {number: 'bigint'})
const one = math.evaluate('(7^46)%47')

The JavaScript bigint type implements arbitrary-precision integer arithmetic, so the precise value of 7^46 will be computed here and divided by 47, leaving the proper remainder.

• The above is still quite wasteful of computing effort, however. We can see from the expression that we are only interested in the result mod 47, so it is quite more efficient to simply compute in the ring (actually a field, but that's just because 47 is prime) of integers mod 47. You can define and import a function for the specific purpose of computing the power of a number modulo another number. For example, the npm package bigint-mod-arith has one called modPow. You can import it so that it will be usable in mathjs formulas like so:

import {create, all} from 'mathjs'
import {modPow} from 'bigint-mod-arith'
const math = create(all, {number: 'bigint'})
math.import({modPow})
const one = math.evaluate('modPow(7, 46, 47)')

• Currently we are doing something much like the above in the Numberscope project which uses mathjs. When that code settles down, we will be proposing either to add a new collection of number-theoretic functions to mathjs, or a add-on package that would extend mathjs with number-theoretic functions. A reason to do the former (incorporate them natively) is that we could enhance the expression parser to parse (a^b)%c as a synonym for modPow(a, b, c), so that these things would no longer cause mathjs difficulty and your original code would have worked. But that all is a ways off, unfortunately.

Finally, I will move this to a discussion, since it is not an "issue" with mathjs per se at the moment. (It is the expected behavior given the default use of JavaScript number type.)

[fcnjd]

Hi @gwhitney ,
thank you very much for your quick and detailed answer. That totally explained the matter to me - and thanks to you I now got my software to work with such expressions too. Awesome.