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?
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: