Search code examples
dartbigintegerarithmetic-expressionsbigint

How to do BigInt arithmetic in Dart 2.x, specifically division?


Dart documentation says that BigInt division returns a value of type 'double'. This is a problem. To illustrate, here are two implementations of an algorithm involving division. The first is in Kotlin, the second is in Dart. The Dart version runs accurately for small numbers but loses precision for larger numbers.

Kotlin

import java.math.BigInteger

fun height(n: BigInteger, m: BigInteger): BigInteger {
  var m1  = m
  var s   = BigInteger("1")
  var b   = BigInteger("1")
  var ans = BigInteger("0")
  var i   = 0
  while (i < n.toInt()) {
    s *= m1--
    s /= b++
    ans += s
    i++
  }
  return ans
}

Dart

BigInt height(int n, int m) {
  var m1  = m;   // new BigInt.from(m);
  var s   = 1.0; // new BigInt.from(1);
  var b   = 1.0; // new BigInt.from(1);
  var ans = new BigInt.from(0);
  var i   = 0;
  while (i < n) {
    s *= m1--;
    s /= b++;
    ans += BigInt.from(s);
    i++;
  }
  return ans;
}

As you can see from the commented out Dart code, I have tried various ways to use BigInt.

Here is an example input with answer. The erroneous Dart answer is given below.

height(13, 550), 
          equals(BigInt.parse('60113767426276772744951355')));

The erroneous Dart answer is --> 60113767426276764034189615

Can someone show me the best way to do the job in Dart v2.x?


Solution

  • The following code works.

    BigInt height(int n, int m) {
      var m1  = new BigInt.from(m);
      var s   = new BigInt.from(1);
      var b   = new BigInt.from(1);
      var ans = new BigInt.from(0);
      var i   = 0;
      while (i < n) {
        s *= m1;
        m1 -= new BigInt.from(1);
        s = s ~/ b;
        b += new BigInt.from(1);
        ans += s;
        i++;
      }
      return ans;
    }
    

    Changes:

    • x++ and x-- are equivalent to x = x + 1 and x = x - 1 but BigInt.+ and BigInt.- only accept BigInt values... so there's a compiler error.
    • BigInt./ returns a double and this is not what you want here. You need to use the BigInt.~/ operator instead.