Apply BigNumber config to functions too (currently it only applies to eval)

[adamazing]

Hello there,
I was attacking Project Euler, problem 26:

"Find the value of d <1000 for which 1/d contains the longest recurring cycle in its decimal fraction part."

I was trying to find the length of the repetend for each 1/d by calculating the smallest k for which 10ᵏ mod d == 1 but was getting weird/wrong results, e.g.

var mathjs = require('mathjs');
mathjs.config({
  number: 'BigNumber',
  precision: 4096
});

var p = mathjs.chain(10)
                  .pow(58)
                  .mod(531)
                  .done();
console.log(mathjs.format(p));
/*
Expected answer: 1 
Actual answer:  0
*/

The expected answer is 1, per https://www.wolframalpha.com/input/?i=10%5E58+mod+531 but it's returning 0?

Reproduction with a more obviously wrong result:

 (...)
var p = mathjs.chain(10)
                  .pow(16)
                  .mod(3)
                  .done();
console.log(mathjs.format(p));
/*
Expected answer: 1 
Actual answer:  0
*/

The greatest power of 10 for which mod(3) gives the correct answer is 15.

Is there something I'm doing wrong here?

[josdejong]

Whilst you configure to use BigNumbers, in chain you use regular numbers (which have a precision in the order of 16 bits which can explain this limit of 10^16).

The following works as expected, the expression parser will create BigNumbers:

mathjs.config({
  number: 'BigNumber'
});

console.log(mathjs.format(mathjs.eval('(10^58) mod 531'))); // 1

or:

mathjs.config({
  number: 'BigNumber'
});

var p = mathjs.chain(math.bignumber(10))
                  .pow(math.bignumber(58))
                  .mod(math.bignumber(531))
                  .done();
console.log(mathjs.format(p)); // 1

The bignumber configuration is confusing, it's quite logical to expect that numbers are always turned into BigNumbers which is not the case. This has bitten other people as well. Maybe we should rethink this behavior and automatically turn all numbers into BigNumbers (or Fractions) when configured like that.

[adamazing]

Thanks for your quick answer Jos.
You're right, the current behaviour seems counterintuitive to me.

[ericman314]

I'm jumping in late in the discussion, but I agree that regular numbers should be converted to BigNumbers automatically. Is this something typed-function can do?

[josdejong]

I don't have a clear idea how we could best tackle this challenge, but I indeed think that this may be something we can solve by extending typed-function with capability to do preprocessing of inputs depending on dynamic configuration.

[josdejong]

I think it is still relevant, and not as a question but as an idea. I'll reopen it and turn it into a discussion topic.

[gwhitney]

Another point specific to the particular function that the original poster was interested in is that the value of 10^58 mod 531 should absolutely not be computed by raising 10 to the 58th power and then taking the remainder mod 531; the power should be computed by some squarings and multiplications, taking the remainder mod 531 each time. In other words, take 10^2 mod 531 (that's 100) and multiply it by 10 to get 10^3 and take the remainder mod 531 (that's 469), then square that (to get 10^6 mod 531) and take the remainder mod 531, then multiply that remainder by 10 (to get 10^7 mod 531) and take the remainder mod 531, then square that twice taking the remainder each time (to get 10^28 mod 531) and then multiply that by 10 (to get 10^29 mod 531) and take the remainder mod 531 and finally square that (to get 10^58) and taking the remainder mod 531. The repeated taking of remainders keeps the whole computation well within the range of ordinary JavaScript number, and using the square-and-multiply trick greatly reduces the total amount of multiplication.

Number theorists routinely use a "powmod" function when they want to get the remainder of a power of a number. Moreover, mathjs could just automatically when it is compiling expressions convert mod(pow(a,b), n) into a call to powmod(a,b,n).

[gwhitney]

This came up again recently in #1485. It seems as though it would be possible (with some enhancements to typed-function) when config.number is 'BigNumber' to reprioritize number->bignumber conversion over accepting a number argument as is, if that's the desired behavior.

[gwhitney]

And it came up yet again in #3374 (comment). Jos there contemplates a config.output setting that would control the behavior of, say, math.divide(1, 3) to get the BigNumber precision when desired. However, it seems to me that this particular issue is much more one of input rather than output; if (due to some configuration) mathjs decides to interpret the 1 and 3 arguments, which are of course natively JavaScript number entities, as BigNumbers (by converting them), then the computation goes just fine with mathjs's existing configuration on how to compute and output things.

So some options:

1. re-imagine config.number to have the semantics of: when mathjs sees a JavaScript number argument (in any context whatever), what type should it automatically convert that argument to? This is a reasonably significant change, but eminently doable. It would mean that config.number wouldn't be about parsing at all. I fact, with this change, "123" would always parse to a JavaScript number, but when evaluated it would automatically convert to the config.number type. However, there is one significant hitch for typing: if we want to continue to support config.number = bigint (and I for one, do), then we may still need/want config.numberFallback to mean "in instances when the conversion of a number input to the type specified by config.number fails, what type should we then try to convert it to ? -- one to which the conversion can't fail." So faced with resolving math.invert on a number argument, when config.number = bigint and convert.numberFallback = BigNumber, you couldn't say whether the result would be a Fraction (if the input were an integer) or a BigNumber (otherwise). And that would disrupt the whole chained method selection from which nanomath/pocomath gets its performance boost. So there are suboptions:

(A) drop TypeScript compatibility and go back to the Pocomath typing system that had a NumInt type (inhabited by JavaScript number entities that happen to be integers) as well as a number type (of all JavaScript numbers), possibly adding a NumDecimal type of just non-integer numbers, with both NumInt and NumDecimal subtypes of number. Then config.numIntTo = bigint and config.numDecimalTo = BigNumber would narrowly type all inputs. However, the TypeScript typing of mathjs methods would become problematic, as TypeScript cannot express the type of "numbers that happen to be integers". You would I suppose still be able to automatically generate typescript typings like number => (Fraction | BigNumber) for invert, but with some complication to the Typescript declaration generator code.

(B) drop numberFallback -- when config.number is bigint, it either becomes an error to supply a bare argument of 123.7 to any mathjs function, or it silently gets converted to 123n or 124n, I suppose depending on the implicit conversion settings.

(C) Beef up method resolution to handle choice types like Either(Fraction, bigint), generating custom wrappers that test just between the two possibilities and call the correct implementation, rather than do full type resolution. Sounds like a lot of work, and it will give back a some fraction of the pocomath speedup, perhaps most of it.

(D) I can't at the moment think of other possibilities, but am certainly open to them.

Since I don't personally care much about Typescript, I am open to (A) but I would understand a desire to keep TypeScript typings narrow -- although there's only so much one can do: If we allow settings under which math.invert(2) returns a Fraction but math.invert(0.159155) produces a BigNumber, the TypeScript typing of math.invert for an instance with those settings going to have to be something along the lines of number => (Fraction | BigNumber), since for typescript 2 and 0.159155 will always both be of the same type number.

2. Provide a function that simply drops all implementations with number arguments, where there is an alternative with the desired numeric type in place. Then method resolution with automatic conversion should do the desired thing. This feels a little "brute force" -- the worry might be there are implementations of the same method whose signatures differ only in number vs another numeric type but that have truly different semantics, so deleting the apparent number version would silently alter the semantics... This also doesn't handle the bigint with fallback to BigNumber case well -- I don't think there is an automatic conversion from number to bigint in place, and even if there were, there's currently no provision to try one automatic conversion on a specific input and if it fails, try some other conversion.

3. Provide enough control over the method resolution process so that it would be relatively easy to set up an instance that prefers number->bignumber conversion when available, over using a method that directly takes a number. This option also feels doable, although even nanomath in its current state (of manual implementation ordering) does not provide such control, as it is hard-coded to try every signature without conversions before trying any signature with conversions. There is also trouble with the bigint falling back to BigNumber in this option; if it tries number->bigint conversion first, it will resolve all calls to math.invert() to call the bigint version that returns a Fraction, and then fail at evaluation time if the actual argument were 0.159155, for example.

In the end, I think it may just be that having settings under which lots of mathjs methods (not just sqrt, for example) return different types depending on the value of the input (and not just its type) is the underlying reason why nothing much has happened on this issue. But if you want to pick some means of dealing with all this now and finally nail it down once and for all, either in v15 or in a nanomath-based overhaul, I am game. I'm just not the right person to pick, since I have no issues with a NumInt type even though TypeScript can't capture it.

[josdejong]

Thanks for thinking this through Glen. It would be a huge breaking change, and there are a lot of cases that we would have to think through. It is an interesting idea to alter the available function signatures and available conversions based on the configured math.number, though I guess that may be complex to work and indeed comes with tricky edge cases and unpredictable cases.

Another idea: we can leave all existing behavior as it is, and introduce a new config option like config.input, which, if configured, will convert input types into one desired input type (it will also need a fallback in case the conversion is not possible).

[gwhitney]

If there's a desire for one of these sorts of input conversion controls, I think there are two main decisions here:

I) What configuration options will there be to control the conversions, and how exactly will they work, and

II) What should be done about the TypeScript typings of the functions in light of these controls? For example, with (say) config.input set to BigNumber, one signature of math.add becomes (number, number) => BigNumber, unlike under the default setting. But as far as I know, TypeScript has no provision to change the types of methods dynamically. So would we:

A) Have multiple TypeScript declaration files, one for each setting of config.input, reflecting the behavior for each?

B) Or just have a single declaration file, with sufficiently coarse typing that it won't be wrong no matter what the setting of config.input is?

In the latter case, I fear that pretty much every function will just have a signature like (MathType, MathType) => MathType because there will be so many possibilities depending on the configuration settings...

[josdejong]

The TypeScript typings are indeed a complex case. I'm not sure how to solve that.

At this point I'm not sure if there is a broad need for this, so let's not (yet) put effort into this.