Modular operation (%) provides false output

Question

With a function, getNextIdx, I want to receive a new index for an array that depends on the current index and the value of the array at that index.

I want the function to return the new index by summing the current index with the value of the array at that index, modular to the array size.

#include<vector> 
using namespace std;

int getNextIdx(int currentIdx, vector<int> array) {
    int jump = array[currentIdx];
    int nextIdx = (currentIdx + jump) % array.size();
    
    return (nextIdx >= 0) ? nextIdx : nextIdx + array.size();
}
int main() {
    vector<int> test = {2, 3, 1, -4, -4, 2};
    int nextIdx = getNextIdx(3, test);    
}

Example: If the current index is 3 (4th element), and the value of the 4th element in the array is -4, and the size of the array is 6, then the function should return 5.

The problem is that my program returns 3 in the above example.

Your c++ concepts are bit unclear. Current Index which is 3 in your case(array[currentIdx] => array[3]) will give element -4. Your question is also bit unclear. Let me know your input and output. — sonulohani, Jul 12 '20 at 05:54
The `%`operator is a bit weird with negative numbers, see https://stackoverflow.com/questions/11720656/modulo-operation-with-negative-numbers/42131603 make your number positive before using `%` to fix the problem — Alan Birtles, Jul 12 '20 at 06:09
@AlanBirtles, using negative numbers is fine (a little odd to some people, true, but it's still fine). The problem here is the mixing of integer *types*. — Elliott, Jul 12 '20 at 07:37

score 3 · Answer 1 · answered Jul 12 '20 at 07:17

Another issue that should be considered about the sample code is type casting take place. Since type of array.size()(6) is size_t and on other hand the other number is negative so compiler cast the negative number to size_t and then apply the Modulo operator on them. For example the output of (-1)% 6 is (-1) but the out put of (-1) % array.size() is (3) because (-1) convert to size_t and became (4294967295)(based on platform the output should be varied) so the Modulo of (4294967295 % 6) is (3).

Elliott · Answer 2 · 2020-07-21T17:35:23.073

Using negative arguments with the % operator is fine. The problem is that you're mixing integer types: nextIdx is a singed integer and array.size() returns an unsigned integer. So your problem can be boiled down to this line of code:

std::cout << -1 % 6u << std::endl; // returns 3

What the % operation does here is convert the type of the left-hand-side to the type of the right-hand-side, so your -1 becomes unsigned, and this messes with your logical modular operation.

You could solve this by changing your function like so:

int nextIdx = (currentIdx + jump) % (int) array.size();

(unasked for) CODE REVIEW:

It would be even better if you could arrange your functions to do these kinds of type conversions for you by defining their inputs appropriately. Also, let's sanitise the inputs.

Something like this:

#include <cassert>
#include <iostream>
#include <vector> 

int64_t PostiveModular (int64_t n, int64_t m)
{
    assert(m > 0);
    
    return n % m + (n < 0) * m;
}

uint64_t NextIndex (uint64_t i, const std::vector<int> & vec)
{
    assert(i < vec.size());
    
    return PostiveModular(i + vec[i], vec.size());
}

score 0 · Accepted Answer · answered Jul 12 '20 at 06:13

0

The modulus operator rounds towards zero (even for negative numbers). Your math expects modulus to round towards negative or positive infinity. See Modulo operation with negative numbers

int getNextIdx(int currentIdx, vector<int> array){
  int jump = array[currentIdx];
  int nextIdx = currentIdx + jump;
  if (nextIdx < 0)
    nextIdx += array.size();
  if (nextIdx >= array.size())
    nextIdx -= array.size();
  return nextIdx;
}

answered Jul 12 '20 at 06:13

Bill Lynch

80,138
16
128
173

Thank you for editing my code and answer, Bill. Your answer is very useful. – Peter Jul 12 '20 at 06:22
There is no rounding in modular operations. The link to the three problem examples may seem strange to someone using the `%` operator initially, but the results are still logically correct. The problem that the OP has posted is an example where the operator returns something logically false (no `n` integer exists so that `nextIdx + n* 6 = 5`). – Elliott Jul 12 '20 at 07:28

Modular operation (%) provides false output

3 Answers3

Linked

Related