# Catch overflow in integer multiplication

**URL:** <https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827>\
**Category:** Support: How do I do ...?\
**Created:** [March 14, 2023, 12:58am UTC](https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827 "2023-03-14T00:58:21Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![patrick](https://avatars.discourse-cdn.com/v4/letter/p/b2d939/32.png) [@patrick](https://numba.discourse.group/u/patrick)\
**Post date:** [March 14, 2023, 12:58am UTC](https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827/1 "2023-03-14T00:58:21Z")

</div>

I am using numba and I would like to know if an overflow has occurred when I multiply two integers. Say the integers are positive for simplicity.

I have written the following function to try and achieve this:

```auto
from numba import njit
import numpy as np

@njit
def safe_mul(a, b):
    c = a * b

    print('a: ', a)
    print('b: ', b)
    print('c: ', c)
    
    print('c//a: ', c//a)
    print('0//a: ', 0//a)

    if c // a != b or c // b != a:
        # do something else or raise error
        raise ValueError()
    return c

@njit
def safe_mul_2(a, b):
    if (np.log2(np.abs(a)) + np.log2(np.abs(b))) >= 63:
        # do something else or raise error
        raise ValueError()
        
    return a * b

print(safe_mul(2 **21, 2** 51))

```

The code prints:

```auto
a: 2097152
b: 2251799813685248
c: 0
c//a: 2251799813685248
0//a: 0
0

```

`safe_mul` does not catch the overflow when `2 **21` and `2** 51` are passed in. Perhaps numba is compiling out the integer division since it knows `c` has just been multiplied by what it is being divided by? I am not sure about this since when you enter something where the arguments are not both powers of 2 then the error is caught.

`safe_mul_2` does catch the error, and is surprisingly not much slower than `safe_mul` (when the prints are removed). I would like to know what is happening in `safe_mul` and if something that is faster than `safe_mul_2` can be written.

---

<div class="post-metadata">

**Author:** ![sschaer](https://avatars.discourse-cdn.com/v4/letter/s/5daacb/32.png) [@sschaer](https://numba.discourse.group/u/sschaer)\
**Post date:** [March 14, 2023, 1:20pm UTC](https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827/2 "2023-03-14T13:20:54Z")

</div>

Dear @patrick

Numba does not remove the operation. You can check this by inspecting the generated intermediate representation:

```auto
safe_mul.inspect_llvm()

```

However, an optimization is performed that results in instructions that do not show the overflow. You can get your example to work by forcing Numba to generate the intendet intermediate representation:

```auto
@intrinsic
def compare(typingctx, a, b):
    def codegen(context, builder, signature, args):
        a, b = args
        prod = builder.mul(a, b)
        quot = builder.sdiv(prod, a)
        ret = builder.icmp_signed("!=", quot, b)
        return ret
    return nb.boolean(a, b), codegen

```

Call it as follows:

```auto
@njit
def safe_mul(a, b):
    if compare(a, b) or compare(b, a):
        raise ValueError()
    ...

```

It’s probably no longer faster to do it this way.  
Regarding your second function, are you sure it’s correct? E.g. `safe_mul2(1, np.iinfo(np.int64).max)` should not raise the error but does.

I hope this clears things up a bit. If you’re not familiar with some of the things shown, let me know.

Edit:  
I had another look at your problem and it turns out LLVM has special support for your needs. For example, it provides signed integer multiplication with overflow checking: `llvm.smul.with.overflow.i64`. In a function this would look like this:

```auto
from llvmlite import ir
from numba import njit, types
from numba.extending import intrinsic

@intrinsic
def mul_with_overflow_check(typingctx, a, b):
    def codegen(context, builder, signature, args):
        int_t = ir.IntType(64)
        bool_t = ir.IntType(1)
        result_t = ir.LiteralStructType([int_t, bool_t])
        fnty = ir.FunctionType(result_t, [int_t, int_t])
        fn = ir.Function(builder.module, fnty, name='llvm.smul.with.overflow.i64')
        
        prod_and_overflowed = builder.call(fn, args)
        prod = builder.extract_value(prod_and_overflowed, 0)
        overflowed = builder.extract_value(prod_and_overflowed, 1)
        with builder.if_then(overflowed):
            context.call_conv.return_user_exc(builder, OverflowError, ("Multiplication overflowed",))   
        return prod

    return types.int64(a, b), codegen

@njit
def foo(a, b):
    return mul_with_overflow_check(a, b)

```

Note that this applies to signed 64-bit integers. Other cases can be implemented equivalently. Also, it is probably the fastest you can get.

---

<div class="post-metadata">

**Author:** ![patrick](https://avatars.discourse-cdn.com/v4/letter/p/b2d939/32.png) [@patrick](https://numba.discourse.group/u/patrick)\
**Post date:** [March 14, 2023, 11:16pm UTC](https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827/3 "2023-03-14T23:16:22Z")

</div>

Thanks so much @sschaer, this is very helpful!

Something I am hoping to do is to be able to follow another branch if an overflow occurs. A branch that is not simply raising an error in the example as you have given. E.g. if `mul_with_overflow_check` could return `(prod, overflowed)` so I could easily condition on the `overflowed` variable downstream. I have tried to modify the code you have written to achieve this but to no avail.

Can your code be modified to achieve this?

With respect to your comment:

> [@sschaer](#):
>
> Regarding your second function, are you sure it’s correct? E.g. `safe_mul2(1, np.iinfo(np.int64).max)` should not raise the error but does.

Indeed, I did not write it very carefully and it was just supposed to be an example of something that would raise an error every time an overflow occurred (so it is safe in some sense) not necessarily that it would only raise an error when an overflow occurred. I should perhaps have mentioned this in the original post.

---

<div class="post-metadata">

**Author:** ![sschaer](https://avatars.discourse-cdn.com/v4/letter/s/5daacb/32.png) [@sschaer](https://numba.discourse.group/u/sschaer)\
**Post date:** [March 15, 2023, 6:53am UTC](https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827/4 "2023-03-15T06:53:51Z")

</div>

Hi @patrick

Of course, this is possible:

```auto
from llvmlite import ir
from numba import njit, types
from numba.extending import intrinsic

@intrinsic
def mul_with_overflow_check(typingctx, a, b):
    def codegen(context, builder, signature, args):
        int_t = ir.IntType(64)
        bool_t = ir.IntType(1)
        result_t = ir.LiteralStructType([int_t, bool_t])
        fnty = ir.FunctionType(result_t, [int_t, int_t])
        fn = ir.Function(builder.module, fnty, name='llvm.smul.with.overflow.i64')
        
        prod_and_overflowed = builder.call(fn, args)
        return prod_and_overflowed

    return types.Tuple([types.int64, types.boolean])(a, b), codegen

@njit
def foo(a, b):
    prod, flag = mul_with_overflow_check(a, b)

```

This returns a tuple of the product of `a` and `b` and a flag that is `True` if the multiplication results in an overflow or `False` otherwise.

---

<div class="post-metadata">

**Author:** ![patrick](https://avatars.discourse-cdn.com/v4/letter/p/b2d939/32.png) [@patrick](https://numba.discourse.group/u/patrick)\
**Post date:** [March 15, 2023, 5:36pm UTC](https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827/5 "2023-03-15T17:36:24Z")

</div>

Thanks so much @sschaer!

A couple of final things:

1. Where did you find the function name `"llvm.smul.with.overflow.i64"` and others like it? (I can infer the names which act on other types).
2. I asked the same question on stack overflow: [here](https://stackoverflow.com/questions/75728233/catch-overflow-error-in-numba-integer-multiplication/75744321#75744321) if you answer it there I can accept it and others are more likely to find it I think.

No worries if you don’t get back to this, it’s already been very helpful and illuminating.

---

<div class="post-metadata">

**Author:** ![sschaer](https://avatars.discourse-cdn.com/v4/letter/s/5daacb/32.png) [@sschaer](https://numba.discourse.group/u/sschaer)\
**Post date:** [March 15, 2023, 6:00pm UTC](https://numba.discourse.group/t/catch-overflow-in-integer-multiplication/1827/6 "2023-03-15T18:00:16Z")

</div>

Hi @patrick

1. you can find all LLVM instrinsics [here](https://llvm.org/docs/LangRef.html). But I should have better checked the [llvmlite documentation](https://buildmedia.readthedocs.org/media/pdf/llvmlite/latest/llvmlite.pdf) first, because they already support the `llvm.smul.with.overflow.i64`, which simplifies the implementation.
2. i am not active on stack overflow. But feel free to copy the solution and link to this thread. You can post the implementation below. It works with any integer types and directly uses the method from `llvmlite`.

```auto
import numpy as np
from llvmlite import ir
from numba import njit, types
from numba import TypingError
from numba.extending import intrinsic

@intrinsic
def mul_with_overflow(typingctx, a, b):
    if not (isinstance(a, types.Integer) and isinstance(b, types.Integer)):
        raise TypingError("both arguments must be integers")
    if a.signed != b.signed:
        raise TypingError("can only multiply integers of equal signedness")
    
    if a.signed:
        ext = lambda builder, a, b: builder.sext(a, b)
        mul = lambda builder, a, b: builder.smul_with_overflow(a, b)
    else:
        ext = lambda builder, a, b: builder.zext(a, b)
        mul = lambda builder, a, b: builder.umul_with_overflow(a, b)

    retint_ty = max(a, b, key=lambda ty: ty.bitwidth)
    sig = types.Tuple([retint_ty, types.boolean])(a, b)
    
    def codegen(context, builder, signature, args):
        int_ty = context.get_value_type(retint_ty)
        a = ext(builder, args[0], int_ty)
        b = ext(builder, args[1], int_ty)
        prod_and_flag = mul(builder, a, b)
        return prod_and_flag
    
    return sig, codegen

@njit
def foo(a, b):
    return mul_with_overflow(a, b)

foo(np.int8(1), np.int32(-2)) # returns int32
foo(np.uint8(1), np.uint16(2)) # returns uint16
foo(np.int32(2), np.int64(np.iinfo(np.int64).max)) # overflow
foo(np.uint64(1), np.int64(2)) # error
foo(np.uint64(1), np.float32(2)) # error

```