2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 mod для отрицательного числа
Сообщение08.03.2010, 12:12 
День добрый. Подскажите, как правильно считать подобные примеры:
-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

 
 
 
 Re: mod для отрицательного числа
Сообщение08.03.2010, 12:47 
Аватара пользователя
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. Впрочем, надо смотреть, что там компилятор сделает из этого алгоритма.

 
 
 
 Re: mod для отрицательного числа
Сообщение08.03.2010, 13:01 
Someone в сообщении #295825 писал(а):
Сложно. Мне кажется, будет быстрее, если вычислить zz Mod pp, и если получится отрицательная величина, прибавить pp. Впрочем, надо смотреть, что там компилятор сделает из этого алгоритма.

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

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

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

 
 
 
 Re: mod для отрицательного числа
Сообщение08.03.2010, 14:22 
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).

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group