Managing integer overflow
Hi there! I'm looking at options for fixed-point math, and none of the existing Python modules (https://github.com/smlgit/fpbinary, https://github.com/francof2a/fxpmath, etc.) seem to check the right boxes, so I'm thinking about creating my own, and maybe contributing it to numpy. Are there any facilities in numpy to manage integer overflow in addition/subtraction/multiplication of values with identical dtypes? The default behavior with integer types like np.uint8 appears to be twos-complement wrapping syntax with an optional warning (or exception or whatever via np.seterr), and that's well-designed, but not as helpful as what I'd like to see in some cases where I'm willing to sacrifice some speed to provide feedback. Ideally if there is an overflow in an array operation I'd like to produce an "overflow array" that's the same size as the result array, but with the values +1 if it's a positive overflow or -1 if it's a negative overflow. That way I can either raise an exception or saturate the output. If there are not such facilities already --- and again, I don't want to burden the default operations with this kind of behavior, but would like to see some way of facilitating this behavior through some mechanism --- let me know and I will open up a feature request. --Jason
Ideally if there is an overflow in an array operation I'd like to produce an "overflow array" that's the same size as the result array, but with the values +1 if it's a positive overflow or -1 if it's a negative overflow.
Alternatively, if boolean arrays are a much more compact memory footprint, then return two overflow arrays, one positive and one negative. Use case: X = ... something ... Y = ... something else ... Z, ovpos, ovneg = multiply_check_ov(X,Y) if ovpos.any(): np.iinfo(Z.dtype).max if ovneg.any(): # uh oh, something we didn't expect, so raise an error
Two boolean arrays are not more compact than one signed `int8` array. But since you'd have to make bool masks from such an array anyways to do anything useful, you might as well pass the bool masks. I think this example shows that you don't need any special infrastructure from numpy. I don't think there is going to be much appetite to expand our API in this direction. On Thu, Apr 27, 2023 at 9:13 AM <jmsachs@gmail.com> wrote:
-- Robert Kern
But I do! I'm looking for something that implements the multiply_check_ov(X,Y) and similar functionality for addition and subtraction, for large arrays; I don't know how to do that efficiently. (Or even correctly for 64-bit operands --- for 8/16/32 I suppose as a baseline I could do the math in 64-bit arithmetic and if the answer doesn't match, then use the sign bit of the 64-bit result for determining overflow.)
On Mon, 2023-05-01 at 17:50 +0000, jmsachs@gmail.com wrote:
There are two things I could imagine. First, improving the warnings and maybe making some overflow errors (or optional). This never happened since it should come with performance impact and that should be low. Second, there could be a `BigInt` dtype that has full precision like Python integers, but I would prefer such development to start outside of NumPy first. But, neither is even what you want probably. So I agree, NumPy is probably not in a position to help you. You can implement the functions that you described yourself (i.e. with overflow return indication). And they will be fully compatible with NumPy (see for example https://github.com/WarrenWeckesser/ufunclab or maybe via jitters like numba). - Sebastian
On Tue, May 2, 2023 at 8:03 AM <jmsachs@gmail.com> wrote:
Some C compilers provide some builtin functions that do this for you, and some cross-platform headers around that show how to do this. https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://github.com/pytorch/pytorch/blob/main/c10/util/safe_numerics.h https://github.com/dcleblanc/SafeInt -- Robert Kern
Ideally if there is an overflow in an array operation I'd like to produce an "overflow array" that's the same size as the result array, but with the values +1 if it's a positive overflow or -1 if it's a negative overflow.
Alternatively, if boolean arrays are a much more compact memory footprint, then return two overflow arrays, one positive and one negative. Use case: X = ... something ... Y = ... something else ... Z, ovpos, ovneg = multiply_check_ov(X,Y) if ovpos.any(): np.iinfo(Z.dtype).max if ovneg.any(): # uh oh, something we didn't expect, so raise an error
Two boolean arrays are not more compact than one signed `int8` array. But since you'd have to make bool masks from such an array anyways to do anything useful, you might as well pass the bool masks. I think this example shows that you don't need any special infrastructure from numpy. I don't think there is going to be much appetite to expand our API in this direction. On Thu, Apr 27, 2023 at 9:13 AM <jmsachs@gmail.com> wrote:
-- Robert Kern
But I do! I'm looking for something that implements the multiply_check_ov(X,Y) and similar functionality for addition and subtraction, for large arrays; I don't know how to do that efficiently. (Or even correctly for 64-bit operands --- for 8/16/32 I suppose as a baseline I could do the math in 64-bit arithmetic and if the answer doesn't match, then use the sign bit of the 64-bit result for determining overflow.)
On Mon, 2023-05-01 at 17:50 +0000, jmsachs@gmail.com wrote:
There are two things I could imagine. First, improving the warnings and maybe making some overflow errors (or optional). This never happened since it should come with performance impact and that should be low. Second, there could be a `BigInt` dtype that has full precision like Python integers, but I would prefer such development to start outside of NumPy first. But, neither is even what you want probably. So I agree, NumPy is probably not in a position to help you. You can implement the functions that you described yourself (i.e. with overflow return indication). And they will be fully compatible with NumPy (see for example https://github.com/WarrenWeckesser/ufunclab or maybe via jitters like numba). - Sebastian
On Tue, May 2, 2023 at 8:03 AM <jmsachs@gmail.com> wrote:
Some C compilers provide some builtin functions that do this for you, and some cross-platform headers around that show how to do this. https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://github.com/pytorch/pytorch/blob/main/c10/util/safe_numerics.h https://github.com/dcleblanc/SafeInt -- Robert Kern
participants (3)
-
jmsachs＠gmail.com -
Robert Kern -
Sebastian Berg