Nice TWiki > Dev > CheckedIntegerArithmetic (r1.6) TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Dev . { Changes | Index | Search | Go }
The current behaviour of numeric type is to silently overflow. In some cases this is what is needed, and in some cases you don't really care, because it is guaranteed no overflow will occur. However, there are also situations in which you would like a runtime exception to be thrown when overflows/underflows occur (hello, Isaac!).

The JVM does not directly support this arithmetic mode. However, at least for non-long types, it is possible to perform operations on a larger JVM type than the declared type, and then check for overflows. This has of course a small performance hit, but much less than using objects (BigInteger? for instance). So it might be possible to add new types that have overflow detection semantic and good performance. I'll focus on int, but this should be doable for shorter types too. What cases are useful in practice?

Since we want to retain the current semantics for int, we should add a new type, with the meaning "a 32 bit signed integer not modulo 2**32" (that is, which throws an exception when an overflow occurs). I'm not sure what the best name for it would be. integer is a possibility, but I was also considering it for infinite length integers (that is an alias for BigDecimal?). Other ideas: checkedInt (not pretty), checked-int (better, but a new convention for type names), cint (cryptic). Let's use cint in this document, it's short :-) how about checked as a modifier, as in "checked int"?

Regarding typing, int should be a subtype of cint, because you gain "safety" by considering an int as a cint. On the other hand, going from cint to int would later allow overflows to occur, so it should not be automatic. I would also think that cint should be a subtype of long, does that make sense?

Regarding implementation, one possibility is to represent cint as long in the JVM, and to check the result of each operation. Another possibility is to represent cint values as int, but operations on cint values would be performed on long, and the result checked before conversion back to int. The former might be more efficient (less conversions), while the later is more economous in space, which is especially interesting if you have an array of cint. Alternatively, is it possible to detect all/most overflows by working on int only (for instance, for addition, if both numbers are positive, there is overflow if the number is negative)?

-- DanielBonniot - 21 Dec 2003

Overflow detection is possible with int for addition and substraction by sign check. For multiplication, i am not quite shure if even long would be enough. -- TWIkiGuest?

The multiplication of two 32 bit numbers fits on 64 bits without overflow (because log(a*b) = log(a)+log(b)). So it seems we could use int to represent cint, and use temporarily a long for multiplication.

Could somebody actually write the operations as Nice methods (using int as the type)? So a int checkedAddition(int,int) method, ... -- DanielBonniot


I don't think that overflow checking should a part of primitive types because it's not clear when the check should happen(when the result is assigned to a cint or one or both of the operands are cint). Whether to do checking is a property of operators so checked methods or code blocks make more sense.

I have doubts about the usefulness of this proposal and this is VM issue and not a language thing. -- ArjanB - 22 Dec 2003

One way to look at it is that there are three kinds of integer types: modulo integers (higher bits are discarded), limited length (checked) integers and inifite length integers (BigInteger?). Mathematically, the first one makes sense (computing a hash value for instance), and of course the last one too. Checked integers would be useful when modulo is clearly incorrect, but you expect that 32 (or 64) bits will be enough. Using BigInteger? would incur a significant performance penalty, but modulo integers would hide errors if they occur.

So from a language point of view, all three types make sense. Therefore it is not a bug that the JVM does modulo arithmetic, it's useful. If we can use it to provide checked arithmetics too, then all the better.

Rgarding when checks happen, it's simple: they should happen when operations are performed on checked integers. So if you do an operation on two int it will not be checked, if one is int and the other cint, then the type system will decide to call the checked operator, and so there will be a check. With overloading on the result type (which is not available at the moment), we could also say that using the result of a int,int operation as a cint should be a checked operation.

-- DanielBonniot

Topic CheckedIntegerArithmetic . { Edit | Attach | Ref-By | Printable | Diffs | r1.12 | > | r1.11 | > | r1.10 | More }
Revision r1.6 - 23 Dec 2003 - 08:14 GMT - DanielBonniot Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.