Let's say you have an array of length 5 and you want to use it as a circular array.

0 | 1 | 2 | 3 | 4 |

If you start at index 2 and move 1 to the right then you end up in index 3. But if you move 3 to the right you end up in index 0. On the other hand if you move 3 to the left then you end up in index 4. Here are some other examples of this translation:

Starting index | Add to it | Resultant | Translated index |
---|---|---|---|

2 | +1 | 3 | 3 |

2 | -1 | 2 | 2 |

4 | +1 | 5 | 0 |

0 | -1 | -1 | 4 |

2 | +3 | 4 | 0 |

2 | -3 | -1 | 4 |

2 | +7 | 9 | 4 |

2 | -7 | -5 | 0 |

2 | +15 | 17 | 2 |

2 | -15 | -13 | 2 |

We need a general formula to map arbitrary resultant integers into corresponding indexes. The modulo operator will not map negative numbers correctly:

6 % 5 = 1 5 % 5 = 0 4 % 5 = 4 3 % 5 = 3 2 % 5 = 2 1 % 5 = 1 0 % 5 = 0 -1 % 5 = -1 -2 % 5 = -2 -3 % 5 = -3 -4 % 5 = -4 -5 % 5 = 0 -6 % 5 = -1

This is because if the whole number division of a negative number N divided by a positive number P is D, then the remainder would be the number X such that D*P + X = N holds. For example, 4/5 = 0 remainder 4, because 0*5 + 4 = 4. Another example, -4/5 = 0 remainder -4 because 0*5 + -4 = -4.

Now in order to get a mapping from arbitrary resultant integers to corresponding indexes in a circular array we need to use the following formula:

Given a resultant R and a length of array L, the corresponding index is

(R%L + L)%L

## No comments:

## Post a Comment