Cannot scale a BigInt by a real number

[kentcb]

• Dart SDK 2.12.0-133.7.beta
• Windows

It does not seem possible to multiply a BigInt by a real number factor. For example, if I have:

final bigInt = BigInt.from(...);
final factor = 1.5;

final multiplied = bigInt * factor;

The final line does not compile because the * operator is only able to multiply one BigInt by another. Converting factor to a BigInt will fix the compilation error but break the intent, since it will truncate factor to the nearest integral value. I need the truncation to occur after the multiplication of the underlying value by the factor.

Unless I'm missing something, there is no way to scale the BigInt value by some non-integral factor.

[lrhn]

Dart doesn't have overloading, so since BigInt has a BigInt operator*(BigInt), it can't also accept an int or double as argument.
Also, the result of multiplying an integer with a double is not necessarily an integer, so the semantics of scaling by a double aren't entirely clear.

You can scale a bigint, b, by any rational number, p/q, by doing b * p ~/ q.
For scaling by 1.5, I'd probably just do b += b >> 1;.

[kentcb]

@lrhn Thanks. To address your points:

• I wasn't really asking for an overload but for a separate method. e.g. scale or multiply
• Truncation is totally understood and expected
• 1.5 was very much just a stand-in for the reality, which is that factor could be any real number

Your solution is useful in a fixed scenario but non-trivial in the general case. I'll have a play around with it, but my original point still stands: this should be built in to BigInt.

[kentcb]

This is my implementation, fwiw:

extension BigIntExtensions on BigInt {
  BigInt scale(double scale) {
    final decimalPlacesInScale = _getDecimalPlacesIn(scale);
    final scaleDenominator = math.pow(10, decimalPlacesInScale);
    final scaleNumerator = scale * scaleDenominator;
    final result = this * BigInt.from(scaleNumerator) ~/ BigInt.from(scaleDenominator);
    return result;
  }

  static int _getDecimalPlacesIn(double value) {
    value = value.abs();
    value -= value.toInt();
    var result = 0;

    while (value != 0) {
      value *= 10;
      value -= value.toInt();
      ++result;
    }

    return result;
  }
}

I've tested this fairly well, but am quite sure it will have some edge cases wrt larger inputs and scales. It also kinda sux in terms of performance, given the way _getDecimalPlacesIn has to iterate.

[lrhn]

The idea is sound, there are some edge cases.

You're effectively converting the double to a rational of two integers. That's not safe, you should be using BigInts for the denominator if you want to be precise. Or if you use binary instead of decimal multiplications, you an also just use the double directly. Something like:

BigInt scale(double scale) {
  if (!scale.isFinite) throw ArgumentError.value(scale, "scale", "Must be a finite value");
  var value = this;
  if (scale.isNegative) {
    scale = -scale;
    value = -value;
  }
  var exponent = 0;
  while (scale < 0x10000000000000 /*2^52*/) {
    // Potential fractional part.
    scale *= 0x100000000;
    exponent += 32;
  }
  return (value * BigInt.from(scale)) >> exponent;
}

That is, find exponent such that scale * pow(2, exponent) has no fractional part and then do value * BigInt.from(scale * pow(2, exponent)) >> exponent. This ensures a precise computation.
I use steps of 32 bits because that's the size of the internal blocks of the VM's BigInt implementation, so the shift at the end becomes cheaper (just drop the last exponent >> 5 blocks).

It's probably possible to be more efficient by reading bits directly from the double - create a double with the same mantissa, but an exponent putting all significant bits above 0.5, and the inverse exponent needed to do the reverse division.
Both can be computed from the bits of the double directly (with proper treatment of denormals).

[rakudrama]

There is the question of whether one should scale a BigInt by a double.

double values can represent only a peculiar subset of the rational numbers. In practice, many values are not exact and have a small error. The number 1.5 can be represented exactly, but 1.6 cannot. The literal 1.6 is converted into the nearest double value which is 'off' after about 16 decimal digits.

Scaling a BigInt by a double is cooking this small error into to the BigInt result, giving meaningless digits:

extension BigIntExtensions on BigInt {
  BigInt scale(double scale) {
    if (!scale.isFinite) throw ArgumentError.value(scale, "scale", "Must be a finite value");
    var value = this;
    if (scale.isNegative) {
      scale = -scale;
      value = -value;
    }
    var exponent = 0;
    while (scale < 0x10000000000000 /*2^52*/) {
      // Potential fractional part.
      scale *= 0x100000000;
      exponent += 32;
    }
    return (value * BigInt.from(scale)) >> exponent;
  }
}

main() {
  final n = BigInt.parse('1' + '0' * 50);
  print(n);
  print(n.scale(1.5));
  print(n.scale(1.6));
  print(n.scale(1.7));
}

100000000000000000000000000000000000000000000000000
150000000000000000000000000000000000000000000000000
160000000000000008881784197001252323389053344726562
169999999999999995559107901499373838305473327636718

Whether this matters to depends on why BigInt is being used.

If BigInt is used for increased precision (number of 'correct' digits), then scaling by a double is not a good idea, and scaling should be done by rational arithmetic - multiply and divide as first suggested. The implication is that the scale factor needs to be constructed with care to avoid approximation errors due to floating-point arithmetic. The rational package might be useful for this.