mod для отрицательного числа

[Kylibin]

День добрый. Подскажите, как правильно считать подобные примеры:
-1284 mod 17
Если верить примеру из учебника (Элементы абстрактной и компьютерной алгебры), то ответ будет 8, а если калькулятору Windows в режиме программиста, то ответ -9

-50 mod 11 = 5 (учебник)
-50 mod 11 = -6 (калькулятор)

P.S.: Если имеет значение, то мне это нужно для освоения алгоритма перемножения 2-х чисел

-- Пн мар 08, 2010 14:32:59 --

Кажется нашел нужный мне алгоритм
Если надо найти zz mod pp , где zz<0 и zz mod pp <>0, то идем по такому алгоритму

pp - (ABS(zz) - pp * (ABS(zz) div pp)) mod pp

[Someone]

Kylibin в сообщении #295820 писал(а):

День добрый. Подскажите, как правильно считать подобные примеры:
-1284 mod 17
Если верить примеру из учебника (Элементы абстрактной и компьютерной алгебры), то ответ будет 8, а если калькулятору Windows в режиме программиста, то ответ -9

-50 mod 11 = 5 (учебник)
-50 mod 11 = -6 (калькулятор)

Это, в общем-то, одно и то же. Просто нужно договориться, какому множеству должен принадлежать остаток.
В математике чаще всего $m\pmod{n}$ берётся из множества $\{0,1,2,\ldots,n-1\}$, но могут быть варианты (например, часто используется наименьший по модулю остаток).
Процессор компьютера при целочисленном делении, как правило, даёт неотрицательный остаток при неотрицательном $m$ и неположительный - при неположительном.

Kylibin в сообщении #295820 писал(а):

Кажется нашел нужный мне алгоритм
Если надо найти zz mod pp , где zz<0 и zz mod pp <>0, то идем по такому алгоритму

pp - (ABS(zz) - pp * (ABS(zz) div pp)) mod pp

Сложно. Мне кажется, будет быстрее, если вычислить zz Mod pp, и если получится отрицательная величина, прибавить pp. Впрочем, надо смотреть, что там компилятор сделает из этого алгоритма.

[Kylibin]

Someone в сообщении #295825 писал(а):

Сложно. Мне кажется, будет быстрее, если вычислить zz Mod pp, и если получится отрицательная величина, прибавить pp. Впрочем, надо смотреть, что там компилятор сделает из этого алгоритма.

Проверил zz mod pp + pp . Ответ устраивает

за пояснение выше отдельное спасибо!

[Cave]

И будьте осторожны: в некоторых языках программирования, включая C и C++, взятие остатка отрицательного числа по модулю неверно реализовано: (-n) mod k = -(n mod k), что неправильно. В таких случаях нужно самостоятельно разбирать случаи.

[ewert]

Cave в сообщении #295847 писал(а):

И будьте осторожны: в некоторых языках программирования, включая C и C++, взятие остатка отрицательного числа по модулю неверно реализовано: (-n) mod k = -(n mod k), что неправильно.

Остаток -- это остаток от деления "нацело", т.е.: $r=m\mod n\quad\Leftrightarrow\quad m=n\cdot z+r$, где $z$ -- это округлённое значение ${m\over n}$ и $|r|<n$. Вопрос только в том, что понимать под округлением; тут, в принципе, возможны самые разные варианты. Чтобы получить правильную арифметику вычетов на всём множестве целых чисел (с только неотрицательными остатками), округлять надо всегда влево. Ну а в трансляторах (а может, даже и в самом процессоре -- не помню) зашито другое правило округления -- в сторону нуля, вот и всё.

------------------------------------------
Во, проверил. Действительно, такое правило зашито в сам процессор. Тестовый пример:

Используется синтаксис Pascal

  j:=-17;
  k:=6;
  
  asm
    mov  dx,$FFFF
    mov  ax,j
    idiv k
    mov  n,ax
    mov  m,dx
  end;

  writeln(i:5, k:5, n:7, m:5);

Выдаёт в качестве остатка от деления (-17) на 6 число (-5).