BigInt wrong math

[neimanpinchas]

Hi and thanks for your book, that gave me the grip on haxe.

I've been troubleshooting an intresting math error, and to my greatest nightmare it turned out to be precision loss within the bigint library.

88413610693600194%1467214936022165

haxe

function main() {
    var a=BigInt.fromString("88413610693600194");
    var b=BigInt.fromString("1467214936022165");
    var c=a.modulo(b);
    trace(a,b,c);
    return;
}

Output

PS C:\Users\ps\Desktop\money_ledger> node .\bigint.js
Debugger attached.
Tested25519.hx:35: 88413610693600194, 1467214936022165, 380714532270288
Waiting for the debugger to disconnect...
PS C:\Users\ps\Desktop\money_ledger> node -v
v20.13.1
PS C:\Users\ps\Desktop\money_ledger> 

As my abacus is too small to prove or disprove the fact, I had to be rely on other tools, since it is working on same hardware we couldn't be sure, but I took it as a vote of 2 against 1.

node

In nodejs we can see that since a is above the int precision, c is already off, but if we use the new n suffix nonation, we get the correct answer.

> 88413610693600194%1467214936022165
380714532270292
> 88413610693600194n%1467214936022165n
380714532270294n

python

In python with BN support.

>>> 88413610693600194%1467214936022165
380714532270294

It seems like the bigint class is thinking that the number could already be small so it relies on js imprecious ints to early, I could verify that in interp it does work as expected.

haxe interp

Tested25519.hx:35: 88413610693600194, 1467214936022165, 380714532270288

I would like to know if the range could be modified, or where to check for the bug, Thanks

[neimanpinchas]

OK I found a fix, I am still not comfortable whether using divmodbig for smalls is OK, seems like toStringWithBase is now causing a callstack error.

If that is small and this is big it will treat both as smalls

  public function divMod(that : BigIntImpl) : { quotient : BigIntImpl, remainder : BigIntImpl } {
    if(that.isZero())
      throw new Error('division by zero');
    return that.isSmall ? divModSmall(cast that) : divModBig(cast that);
  }
  public function divMod(that : BigIntImpl) : { quotient : BigIntImpl, remainder : BigIntImpl } {
    if(that.isZero())
      throw new Error('division by zero');
    return that.isSmall && this.isSmall ? divModSmall(cast that) : divModBig(cast that);
  }

[neimanpinchas]

I've managed to fix the issue using

 public function divMod(that : BigIntImpl) : { quotient : BigIntImpl, remainder : BigIntImpl } {
    if(that.isZero())
      throw new Error('division by zero');
    return if (that.isSmall && this.isSmall){
      divModSmall(cast that);
    } else if (that.isSmall) {

      var upgraded=new Big([],that.sign);
      var added=upgraded.addSmall(cast that);
      divModBig(cast added);
    } else {
      divModBig(cast that);
    }
  }

DO you want me to go ahead and make a PR of it?

[neimanpinchas]

I see that the author like PRs more than issues, so I created a PR with the fix above

[fponticelli]

Thank you very much, PR merged!