search

peterolson / BigInteger.js

An arbitrary length integer library for Javascript
The Unlicense
1.12k stars 187 forks source link

gcd giving problems from version 1.6.26 onwards? #150

Closed davidedc closed 6 years ago

davidedc commented 6 years ago

I'm using Algebrite. Doing the trace(hilbertmatrix(50)) ( which in Algebrite is written contract(hilbert(50)) ) one gets the system to calculate 1 + 1/3 + 1/5 + 1/7 + ... + 1/99

So, fraction addition is exercised, in particular the gcd function of bigInt.

Until version 1.6.25 I get the correct result (3200355699626285671281379375916142064964/1089380862964257455695840764614254743075), while in subsequent versions I get wrong results.

Unfortunately, I don't quite understand why but I get wrong results depending on other tests I run in advance (which would only be explained if BigInteger used some internal caches of some kind?)

In particular, I think I narrowed it down to problems in gcd, where for example I wouldn't get the correct result for gcd(8668767785502825,702170190625728800) (which is 25).

Now, it's very possible that this is not a problem in BigInt, but I wanted to submit this in case you might have comments (such as "no, look, we don't use caches or dynamic programming, so the results are stateless and they are either correct or incorrect all the times").

peterolson commented 6 years ago

It's possible that something could be wrong with bigInt, so I don't want to rule that out entirely, but as you suggested the results should be stateless and not vary from one call to the other. (At least I can't think of any reasons why they would -- again I don't want to overconfidently say that there is no sort of mutation bug)

For what it's worth, running

+bigInt.gcd(8668767785502825, 702170190625728800)

gives me 25.

davidedc commented 6 years ago

thanks. OK I'll close until I investigate this further. I can step into that gcd call and see if the mistery is in there or not.