CODEWITHSUNDEEP
dartsumoverflowinteger-overflow
John
John

Reputation: 53

Dart - Overflow Safe Summation of List

In Dart, is there a simple way to check whether the sum of a list will produce a 'real' value (a value that doesn't overflow or underflow)?

Examples:

overflowSafeSum([0,1,2]) //3
overflowSafeSum([1,9223372036854775807]) //Over
overflowSafeSum([-1,-9223372036854775808]) //Under

Upvotes: 0

Views: 148

Answers (2)

jamesdlin
jamesdlin

Reputation: 90125

(To be pedantic: "underflow" is not negative overflow. Overflow occurs when the magnitude of a number is too large to be represented, regardless of sign. Underflow is an issue with floating-point operations where the magnitude of a number is too small (too close to 0) to be represented.)

You can't generally detect overflow with Dart ints since Dart for the web is transpiled to JavaScript, where ints are backed by JavaScript numbers (IEEE-754 double-precision floating-point values). If you instead use Int32 or Int64 from package:fixnum (or if you restrict yourself to the Dart VM), then you could make a helper function like:

class OverflowException implements Exception {
  OverflowException({this.positive = true});

  bool positive;
}

Int64 checkedAdd(Int64 a, Int64 b) {
  var sum = a + b;
  if (a > 0 && b > 0 && sum < 0) {
    throw OverflowException(positive: true);
  }
  if (a < 0 && b < 0 && sum > 0) {
    throw OverflowException(positive: false);
  }
  return sum;
}

From there, you could trivially add a function that calls it in a loop:

Int64 overflowSafeSum(Iterable<int> numbers) {
  var sum = Int64(0);
  for (var number in numbers) {
    sum = checkedAdd(sum, Int32(number));
  }
  return sum;
}

or if you prefer using Iterable.fold:

Int64 overflowSafeSum(Iterable<int> numbers) =>
    numbers.fold<Int64>(Int64(0), (sum, i) => checkedAdd(sum, Int64(i)));

Upvotes: 0

John
John

Reputation: 53

I'm new to dart, this is the best I got right now:

import 'dart:math' show pow;

enum Overflow {
  over,
  under,
}

void main() {
//idea: Iterate through the elements of a list and add them, 
//each time the sum overflows: increase overflowCounter by 1
//each time the sum underflows: decrease overflowCounter by 1
//if all the elements have been added and the overflowCounter == 0, the sum must be real

  overflowSafeSum(List<int> userList) {
    var sum = 0, overflowCounter = 0;
    for (int index = 0, nextTerm;
        index < userList.length;
        index++, sum += nextTerm) {
      nextTerm = userList[index];
      if (sum.sign != nextTerm.sign) {
        continue; //adding a postive and negative can't overflow or underflow
      } else if (sum >= 0 && nextTerm >= 0) {
        if ((sum + nextTerm) < 0) overflowCounter++;
      } else {
        if ((sum + nextTerm) >= 0) overflowCounter--;
      }
    }
    if (overflowCounter == 0) {
      return sum;
    } else if (overflowCounter > 0) {
      return Overflow.over;
    } else {
      return Overflow.under;
    }
  }
  var myList = [1,0,(pow(2,63)-1).toInt()];
  print(overflowSafeSum(myList)); //Overflow.over
}

Upvotes: 1

Related Questions