Алгоритм определения «направления движения» в конечном поле.

Question

Я пытаюсь определить наиболее эффективный механизм для определения направления движения (т. Е. Кратчайшего направления между начальным начальным значением и вторым конечным значением) в конечном поле (т. Е. Поле numeri c целых чисел mod M ).

Например, если данное поле было определено как положительные целые числа по модулю 20 и мое начальное значение было 15, то следующий набор будет «вправо / положительно / по часовой стрелке» - {16, 17, 18, 19, 0, 1, 2, 3, 4, 5} и «влево / минус / против часовой стрелки» будут {14, 13, 12, 11, 10, 9, 8, 7, 6}.

Метод "грубой силы" - это линейный поиск по модулю 20, начиная с начального значения и сравнивая каждое значение с новым значением. Например,

int field_size = 20, starting_point = 15, new_value = 2;
auto half_field_size = field_size / 2;

// 0 - not set
// 1 - clockwise
// 2 - anti-clockwise
int direction = 0;

for(int i = 0; i <= half_field_size; i++){
    if(((starting_point + i) % field_size) == new_value){
        direction = 1;
        break;
    }
}
if(direction == 0) direction = 2;

Хотя это относительно легко понять (с точки зрения кода), это кажется довольно неэффективным способом определения направления. Я чувствую, что есть более прямой способ использования модульной арифметики c, но мне сложно придумать что-то последовательное.

Answer 1

Мне кажется, что есть более прямой способ использования модульной арифметики c

Основная идея - сравнить starting_point - new_value с field_size/2 по модулю.

Рассмотрим:

direction = (field_size + starting_point - new_value)%field_size*2 >= field_size;

(field_size + starting_point - new_value)%field_size либо [0 ... field_size / 2) для одного направления, либо [field_size / 2 ... field_size-1] для другого.