search

numberscope / frontscope

Numberscope's front end and user interface: responsible for specifying sequences and defining and displaying visualizers
MIT License
7 stars 15 forks source link

sequence by formula fails on catalan numbers #168

Open katestange opened 2 years ago

katestange commented 2 years ago

I know I just put a bunch of issues in on sequence by formula, but I think (?) this one is not the same bug as any of the other ones. This is a formula that should be valid (return an integer). The following formula for the n+1-st Catalan number fails: factorial(2*(n+1))/factorial(n+2)/factorial(n+1). I've put n+1 so that the factorials are all defined even at n=0. It fails one some big numbers somewhere, where it says they aren't integers, e.g. Uncaught RangeError: The number 477638699.99999994 cannot be converted to a BigInt because it is not an integer

gwhitney commented 2 years ago

Yeah, straight-up dividing factorials is generally a problematic computation strategy: not helpful to generate a huge numerator and a huge denominator and then rely on lots and lots of cancellation. (You might have gotten away with this if bigints were already incorporated in mathjs, but you would still be making your computer work much harder than need be.) Much better to stick with (2n choose n)/(n+1) where the implementation can do all the canceling termwise inside the binomial coefficient, so that the intermediate results don't get anywhere near so big. Then you can get much farther without overflow. In mathjs and hence in our formulas this is combinations(2n, n)/(n+1) (maybe we should link to the mathjs documentation from the frontscope documentation?). But even easier is catalan(n) ;-) (which is already implemented in mathjs, as it happens)

gwhitney commented 2 years ago

I'll leave this up as a bug until we at least get a try-catch in the right place.

gwhitney commented 2 months ago

Should be moot once #343 is addressed.