3 ms·
While the article discusses possible solutions to an important problem and it may have some good ideas, I strongly dislike the choice of words of the author, be
by adrian_b 5y ago
While the article discusses possible solutions to an important problem and it may have some good ideas, I strongly dislike the choice of words of the author, because such inappropriate terminology is one of the main causes why there are problems with handling integers.
When using a bit string with N bits, e.g. a 64-bit bit string, it is possible to implement 3 distinct integer types.
Two types are subtypes of the integer numbers in the mathematical sense, i.e. interval types a.k.a. range types, which can be either signed, e.g. with values in the interval [-2^63, 2^63-1], or unsigned, e.g. with values in the interval [0,2^64-1].
The third type are modular numbers, e.g. numbers modulo 2^64.
Unfortunately I am not aware of any programming language that either allows the use of all 3 kinds of types or at least uses appropriate names for the available types.
For example, the types named "unsigned" in C and C++ are not unsigned numbers, but modular numbers. They should never be used for a variable that is intended to belong to an interval of integer numbers, unless there is certainty that during any computations with that value it is impossible for reductions by the modulus to appear.
The wrapping behavior of modular numbers is not an "implicit overflow", it is their normal behavior according to their definition. There is no overflow of modular numbers.
On the other hand, for the interval numbers (e.g. C/C++ "int" or "long") a decent programming language should define what happens on integer overflow.
The fact that many modern programming languages have chosen to specify that the behavior on integer overflow is undefined is extremely annoying and this is the root cause of all bugs caused by overflows.
There are 2 acceptable behaviors, the same as for floating point numbers, either integer saturation, where the interval limits are considered infinities, which are the result of overflows and then they are preserved by all subsequent operations until they are tested later, or an integer overflow exception signaled immediately.
Most ancient computers and programming languages always generated exceptions on integer overflow.
Ignoring integer overflow is a modern method of cost reduction which moves the burden from CPU designers & manufacturers to the programmers who must now either be able to predict correctly whether integer overflows will ever happen or compile with options for overflow checking.
Due to the poor support for integer overflow checking in most modern CPUs, this option causes a much greater performance penalty than really necessary.
Fortunately the existence of the IEEE 754 standard has prevented such cost reduction measures for floating-point operations, but for integer operations there is no standard to force the CPU makers to do the right thing.
- adrian_b 5y agoI want to add that what the author of the article has correctly noticed, but this was not expressed clearly, is that between any 2 modular number types with distinct moduli there cannot be a subtype relationship. That means that in languages with modular number types, e.g. C/C++, there should not exist any implicit conversions between modular numbers of different sizes or between a modular integer type and an interval integer type. That means that all promotions between a smaller unsigned type and a larger unsigned type or between a signed integer type and an unsigned integer type, which exist in C/C++, are wrong and they should be deprecated. On the other hand the implicit conversions between an interval type and another interval type including it are correct. So only the implicit integer promotions signed char => short => int => long => long long are right in C/C++, all the other implicit integer conversions are wrong.
- gpderetta 5y agoWhile uint32_t is not an uint64_t in the is-a sense, I don't see why any specific value of uint32_t can't be converted to an uint64_t. What kind of error would be prevented by disallowing this conversion?
- Someone 5y agoI think what’s meant is this: if you do uint32_t foo = 42 you’re effectively saying foo = 42 (mod 2³²) So, foo stands for the equivalence set {…, 42-2³², 42, 42+2³², …} If you say uint64_t bar = 42 you’re making the different statement that bar = 42 (mod 2⁶⁴) You can’t say that foo and bar are the same number, because (for example) foo * 2³² ≠ bar * 2³²
- adrian_b 5y agoFor example, if you have an uint8_t with the value 200, that denotes either the number 200 or the number 456 or the number 712 and so on. If you have an uint16_t with the value 200, that denotes either the number 200 or the number 65736 or the number 131272 and so on. So it is obvious that the two "200" do not mean the same thing. If you do a longer sequence of operations with uint8_t or uint16_t, inserting an implicit integer promotion in the middle of the chain of operations will change the end result, depending on the place where it is inserted. (E.g. 200*200 will be either 144 or 40000, depending on whether the promotion is done before or after the multiplication) Of course most programmers do not actually use the "unsigned" numbers as modular numbers but as a surrogate for the lack of proper "unsigned" interval numbers and they attempt to avoid any operations which will cause modular reduction. If the programmer knows that no modular reduction has occurred, he/she can write an explicit type conversion from a smaller "unsigned" type to a larger type. The compiler cannot know which was the intention of the programmer. Because the "unsigned" numbers are defined as modular numbers, not as interval numbers, any implicit conversion can be erroneous. If the conversions are actually correct, the programmer should write them explicitly.