'arithmetic operation overflowed'

1

Can any one please help me with this error. why this occurs ? and what it is ?

pub fn insertion_sort(arr: &mut[i32]) ->&mut [i32]{
    let mut i =1;
    let mut j =1;
    let mut key: i32=0;
    let mut arr_len = arr.len();

    for i in 1..arr_len{
        key = arr[i];
        j = i-1;
        while j>= 0 && key < arr[j] {
        arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j + 1] = key;
    }
    arr
}
2

Some notes:

  • This forum has a button to format the code, it's shaped like </>, use it, so the code is more readable;

  • Fix the formatting of your code, because for you and people it's more easy to spot bugs in tidy code;

  • Listen to your compiler, you have many unaddressed warnings. Fix them;

  • Don't use "mut" unless needed;

  • Define variables in the strictest scope possible;

  • If a procedure mutates the array in-place, then also returning the array is often a bad API (unless you return it with a different incompatible type, like the D language sort);

  • If you use "-g" compiler switch the compiler will probably tell you what's the line number of the arithmetic overflow error, take a look;

  • If you ask people for help, give them a minimal example that reproduces the problem. This means you need to add a main() function with a call that gives the error. I have failed to see the error message in this code:

    fn insertion_sort(arr: &mut[i32]) {
    let arr_len = arr.len();

      for i in 1 .. arr_len {
      let key = arr[i];
      let mut j = i - 1;
      while key < arr[j] {
      arr[j + 1] = arr[j];
          j -= 1;
      }
      arr[j + 1] = key;
  }

    }

    fn main() {
    let mut a = [10, 30, 20];
    insertion_sort(&mut a);
    println!("{:?}", a);
    }

2 Likes
3

Though he brings up good points, it looks like @leonardo was too busy nitpicking the formatting and code style to notice the actual error--which is actually plain as day, at least by my eyes (and it's almost bedtime for me).

The error message is a bit misleading, as we're actually looking at an arithmetic underflow (unsigned value going under 0 and wrapping around to an absurdly high value), which is only triggered if the first two elements are out of order.

pub fn insertion_sort(arr: &mut[i32]) ->&mut [i32]{
    let mut i =1;
    let mut j =1;
    let mut key: i32=0;
    let mut arr_len = arr.len();

    for i in 1..arr_len{
        key = arr[i];
        // On first iteration, this is set to 0
        j = i-1;
        while j>= 0 && key < arr[j] {
        arr[j+1] = arr[j];
            // If this is executed when j = 0, it will underflow.
            j = j-1;
        }
        arr[j + 1] = key;
    }
    arr
}

This is triggered with a trivial test-case:

fn main() {
    let mut array = [20, 10];
    insertion_sort(&mut array);
}

Unfortunately, I'm a little too tired to go through and fix your sort implementation for you, but hopefully you at least know what's going wrong now. :slight_smile:

1 Like
4

j>= 0 followed by j = j-1;

5

I didn't look for the error. First you fix the formatting and similar mistakes, then you look for the bugs. Spotting the bug for the OP is pedagogically bad.

6

OP might never have spotted the bug (at least not without a lot of frustration), because the error message unhelpfully told him to look for an integer overflow. It's pretty clear he's coming to Rust from a language without unsigned integers (or one that uses signed integers for indexing), as he's expecting 0 - 1 to work just fine for index calculation and break the while loop, and he doesn't use it again without adding 1 back.

OP already fixed the formatting and the code style is something that can be smoothed over as he learns. Lighten up. I didn't go out of my way to solve his problem for him; he still has to fix the sort in a way that doesn't rely on the above assumption.

7

So to add to what @DroidLogician said.

To understand why this code panics you have to know what type the variables are. In this code it is not obvious at first, because type inference deduces the types for you.

If you quickly want to see what type the type inference choose you can change the assignment to:

let j: () = ...

The compiler will then give an error like:

error: mismatched types:
 expected `()`,
    found `usize`
(expected (),
    found usize)

For this code we find that j is of type usize, which is an unsigned pointer-size integer type. You could also have deduced the type of j yourself because indexing in Rust is always done using usize types. So when you do arr[j + 1] then j + 1 has to be usize and because Rust does not do implicit conversions, j has to be usize.

Knowing the type of j you can now understand why it causes the problem described by @DroidLogician

8

Thank you so much to all.:grin: