Как понять m 3 mod6 что означает

Как понять m 3 mod6 что означает

Оператор div и оператор mod

В этой статье речь пойдет о целочисленном делении и делении с остатком.

Итак, что такое целочисленное деление вообще? В математике целочисленным делением называют такое деление, при котором одно целое число делится на другое целое число ,а результатом является целая часть их частного.

То есть например 20 / 5 = 4, 55 / 6 = 9, 100 / 3 = 33 и т.д.

Согласитесь, что в некоторых случаях это очень удобно и практично. Теперь поговорим о реализации этого метода в Паскале. Тут все достаточно просто, открывать Америку не придется. В паскале за целочисленное деление отвечает оператор div. Теперь как это записывается в Pascal’e

x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — результат целочисленного деления (целочисленное частное)

Таким образом, вот такая запись (55 / 6) нацело = 9 в результате использования оператора div будет выглядеть так

z будет равно 9. Запомните! При использовании оператора div дробная часть будет отброшена!

А сейчас поговорим о делении с остатком. Оно не особо отличается и главным здесь является то, что в результате отбрасывается как раз целая часть. То есть (40 / 6) с остатком = 4, (10 / 3) с остатком =1, (22 /5) с остатком = 2 и т.д. В паскале для этого есть оператор mod. Записывается он точно так же.

x — число , которое будем делить на y (делимое)
y — число , на которое будем делить число x (делитель)
z — остаток

Например (40 / 6) с остатком = 4 с оператором mod будет такой

И как результат получим z=1 .

Кстати оператор mod часто используют, для определения кратности чисел (кратность — это делимость на какое-нибудь число нацело. То есть например говорят, что числа 3, 6, 9, 12, 21 кратны трем. Или числа 5,10,15,20 кратны 5). В статье нахождение четных элементов массива я упоминал о числах кратных двум (четных). Итак как эту кратность определить в паскале. Обратите внимание, что если число кратное, то у него есть остаток (точнее оно имеет в остатке ноль). Этим и стоит воспользоваться.

Сейчас я привел пример условия, которое проверяет кратность, где v — это число, проверяемое на кратность по числу m. Например чтобы проверить,
является ли 40 кратным 4, используем оператор mod с условием и получим

Mod и остаток — не одно и то же

Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!

Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре RSA для SSH, который, очевидно, является самым загружаемым фрагментом кода в истории IT.

Хочется полностью разобраться в этой истории. Кто придумал этот шифр, как он работает, почему работает и будет ли работать в будущем. Сейчас я раскопал одну чертовски интересную историю. Я не криптоманьяк и вижу, как других буквально засасывает в эту область. Но мне это тоже интересно, потому что повсюду есть маленькие норки, а меня как сороку привлекают блестящие штучки в глубоких норках. Я также очень хорош в метафорах.

В любом случае: на прошлой неделе я узнал что-то странное и хочу поделиться: оказывается, mod и остаток от деления — не одно и то же. Действительно забавно то, что некоторые читатели при этих словах выпрыгивают со своих кресел и орут: «А ведь именно это я всегда пытался сказать вам и всем остальным!»

Позовите ребят из секты «mod не остаток»! Это для вас.

Что такое mod?

Я должен был изучить это, как и в прошлый раз, когда всплыла такая тема. Это одна из тех вещей, которые ты знаешь, но не запоминаешь. Когда вы применяете mod, то делите одно число на другое и берёте остаток. Итак: 5 mod 2 будет 1, потому что 5/2=2 с остатком 1.

Термин mod означает операцию modulo, с модулем 2 в данном случае. Большинство языков программирования используют % для обозначения такой операции: 5 % 2 = 1 .

Вот где мы попадаем в странную серую область.

Математика циферблата

Помню, как учил это в школе, а потом забыл. Существует тип математики, называемый «модульной арифметикой», которая имеет дело с циклическими структурами. Самый простой способ представить это — циферблат с циклом 12. Для математика циферблат — это mod 12 . Если хотите понять, можно ли равномерно разделить 253 часа на дни, то можете применить операцию 253 mod 24 , результатом будет 13, поэтому ответ «нет»! Мы можем ответить «да» только если результат 0.

Другой вопрос, который вы можете задать: «Если я выеду в 6 вечера, сколько времени будет по приезду через 16 часов?». Это будет 6 + 16 mod 12 , то есть 10.

Криптографы любят mod , потому что при использовании с действительно большими числами можно создать нечто, известное как «односторонние функции». Это специальные функции, которые позволяют легко вычислить что-то в одном направлении, но не в обратном.

Если я скажу вам, что 9 является результатом возведения в квадрат, вы можете легко определить, что на входе было 3. Перед вами весь процесс от начала до конца. Если я скажу, что 9 является результатом mod 29 , то будет сложнее понять, что на входе.

Криптографам нравится эта идея, потому что они могут использовать деление с остатком с гигантскими простыми числами для генерации криптографических ключей. Это совсем другая история: если хотите прочитать об этом, то можете купить книгу или, ещё лучше, поддержать мои усилия написать её.

Впрочем, не будем отклоняться от темы.

Остатки и математика циферблата

Теперь переходим к сути: modulo и простой остаток одинаковы, когда числа положительны, но отличаются в случае отрицательных чисел.

Рассмотрим такую задачу:

const x = 19 % 12; console.log(x);

Каково значение x ? Делим числа и получаем 7 как остаток от 12. Это верный ответ. Как насчет такого:

const y = 19 % -12; console.log(y);

Используя обычную математику, мы можем умножить -12 на -1, что даёт 12, и у нас по-прежнему остаётся 7, поэтому наш ответ снова 7.

JavaScript с этим согласен:

C# тоже согласен:

Google согласен с первым утверждением, но не согласен со вторым:

Ruby согласен с Google:

Во имя Дейкстры, что здесь происходит?

Вращение часов назад

Чтобы ответить на вопрос, следует понять разницу между остатком и modulo. Программисты объединяют эти операции, но не должны этого делать, потому что они дают одинаковый результат только в случае, если делитель (в нашем случае 12) положителен. Вы можете легко отправить баги в продакшн, если делитель отрицательный.

Но почему существует разница? Рассмотрим положительный делитель 19 mod 12 на часах:

Конечный результат 7. Мы это знаем и мы можем доказать математически. Но что насчёт 19 mod -12 ? Здесь нужно использовать другие часы:

Модуль равен -12, и мы не можем игнорировать или изменить его, умножив на -1, поскольку модульная арифметика так не работает. Единственный способ правильно рассчитать результат — переставить метки на часах так, чтобы мы двигались от -12 или вращали часы против часовой стрелки, что даёт тот же результат.

Почему не начать метки с -1, двигаясь к -2, и т.д.? Потому что в таком случае мы будем двигаться назад и постоянно уменьшать результат, пока не достигнем -12, и в этот момент сделаем прыжок +12, а modulo так не работает.

Это известная вещь

Прежде чем назвать меня сумасшедшим и начать гуглить тему: это известный факт. На самом деле MDN (Mozilla Developer Network) даже дошла до того, чтобы назвать % операцией «остатка» (remainder), а не modulo:

Оператор remainder возвращает остаток от деления одного операнда на другой. Он всегда принимает знак делимого.

Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:

Однако это совсем не то, что оператор % реально делает в C#. Оператор % не является каноническим оператором modulus, это оператор остатка.

А как на вашем языке?

Ну и что?

Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:

1. Я представляю, как этот вопрос займёт меня врасплох на собеседовании.
2. Я представляю, как этот попадёт в продакшн, а разработчики будут несколько часов выяснять, почему математика не работает.

Математические функции CreateUiDefinition

Данные функции позволяют выполнять математические операции.

add

Складывает два числа и возвращает результат.

В следующем примере возвращается 3 .

"[add(1, 2)]" 

ceil

Возвращает наибольшее целочисленное значение, которое больше или равно указанному числу.

В следующем примере возвращается 4 .

"[ceil(3.14)]" 

div

Делит первое число на второе число и возвращает результат. Результат всегда представляет собой целое число.

В следующем примере возвращается 2 .

"[div(6, 3)]" 

floor

Возвращает наибольшее целочисленное значение, которое меньше или равно указанному числу.

В следующем примере возвращается 3 .

"[floor(3.14)]" 

max

Возвращает большее из двух чисел.

В следующем примере возвращается 2 .

"[max(1, 2)]" 

мин

Возвращает наименьшее из двух чисел.

В следующем примере возвращается 1 .

"[min(1, 2)]" 

mod

Делит первое число на второе число и возвращает остаток.

В следующем примере возвращается 0 .

"[mod(6, 3)]" 

В следующем примере возвращается 2 .

"[mod(6, 4)]" 

mul

Умножает два числа и возвращает результат.

В следующем примере возвращается 6 .

"[mul(2, 3)]" 

rand

Возвращает случайное целое число в пределах заданного диапазона. Эта функция не создает криптографически безопасное случайное число.

В следующем примере может вернуться 42 .

"[rand(-100, 100)]" 

range

Создает последовательность целых чисел в пределах заданного диапазона.

В следующем примере возвращается [1,2,3] .

"[range(1, 3)]" 

sub

Вычитает второе число из первого числа и возвращает результат.

В следующем примере возвращается 1 .

"[sub(3, 2)]" 

Дальнейшие действия

• Общие сведения об Azure Resource Manager см. в этой статье.

Как понять m 3 mod6 что означает

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code. /code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии «срочно надо», заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray
‘> Алгоритм MOD

• Подписаться на тему
• Сообщить другу
• Скачать/распечатать тему

Сообщ. #1 , 30.01.07, 00:40

Senior Member
Рейтинг (т): 13

Каков внутренний алгоритм функции MOD.Смысл MOD я понимаю, но мне нужно зделать MOD свой(для длинных чисел).

Сообщ. #2 , 30.01.07, 01:38
Рейтинг (т): 78

• a = b | mod m => a + c = b + c | mod m
• a = b | mod m => a * c = b * c | mod m
• a = b | mod m => a^c = b^c | mod m

Кстати, если делитель легко факторизуется (что не всегда!), то можно использовать Chinese Remainder Theorem.. Но это уже отдает каким-то шаманством

Сообщ. #3 , 30.01.07, 01:40
Рейтинг (т): 191

MOD=возвращает остаток от деления между двумя числами.

mov eax,Младший Dword
mov edx,старший Dword
div src
результат
quotient is stored in EAX
and the remainder in EDX

так вот remainder(остаток) и есть результат операции MOD

P.S.
фу блин не дочитал саме интересное(для длинных чисел) ну ладно пусть остается может пригодится

Сообщение отредактировано: AlexJ — 30.01.07, 01:49
Сообщ. #4 , 30.01.07, 02:45

Senior Member
Рейтинг (т): 13

Мне одно не понятно естли это остаток от деления то почему:
5 mod 6=5 когда 5/6=0,83(3)
хотя иногда, получается например:
5 mod 4=1 когда 5/4=1,25- естли округлить
В чем прикол я не пойму обьясните что это за остаток такой интересный?
Каков алгоритм?

Сообщ. #5 , 30.01.07, 05:06
Рейтинг (т): 191
Цитата Dethlord @ 30.01.07, 02:45
Мне одно не понятно естли это остаток от деления то почему:
5 mod 6=5 когда 5/6=0,83(3)

5/6=0.83 — это арифметическое деление
операция же MOD

The result of the initial division is truncated to an integer-class value, before the remainder is calculated.

Т.е. операция деления производится над целыми числами,
если делитель больше чем делимое, тогда резултат операции MOD будет равен делимому. Или другими словами целое число не может быть разделено больше чем на само себя. 5 mod 149 = 5 ; 5 mod 12345 = 5 ; 9 mod 345 = 9

хотя иногда, получается например:
5 mod 4=1 когда 5/4=1,25- естли округлить

Ну здесь помоему все понятно 4 укладывается в 5-ке один раз, и остаток от деления = 1

22 mod 5 = 2 (5-ка укладывается полностью в 22 четыре раза, и остаток от деления =2)

Сообщ. #6 , 30.01.07, 06:10

Senior Member
Рейтинг (т): 13

Всем спасибо проблемма решена:
Взятие модуля

С этим алгоритмом пришлось изрядно повозиться из-за того, что операция Mod практически нигде не описана. Опять вспоминаем математику:

A mod B=C означает, что существует такое положительное целое число K, что B*K+C=A. C нам надо найти. Что ж, существует очень простой способ: отнимать от A число B до тех пор, пока A>=B. В итоге получим C. Но представьте только, сколько операций вычитания придётся сделать при больших числах. Надо как-то оптимизировать вычитание. До сих пор мы не использовали число K. Каким оно может быть? K может быть разложено на произведение чисел. Чем оптимальнее будут выбраны эти числа, тем лучше! Самое лучшее решение, что приходит в голову: выбирать K поразрядно (по степеням 10). Протестируем идею — рассмотрим пару примеров:

2. 1237 mod 70=44 44 mod 7=2

3. 1237 mod 700=534 534 mod 70=44 44 mod 7=2

Значит, мы можем варьировать значением числа K~B (с определёнными условиями)!

Воплощаем мысль в алгоритм:

1. Откинем все частные случаи и тогда получим, что: A>B

3. Будем умножать B на 10 до тех пор, пока длины чисел A и B не сравняются.

4. Если A=B, то mod=0

6. Поочерёдно умножаем B на i=1,2,3,… пока B не станет больше A

7. Берём предыдущее число (i), на которое было умножено B, и выполняем A=A-B*i

8. Идём на шаг 2

Возможно, пример поможет понять алгоритм:

356395 mod 37=C, C=?

Умножаем B на 10, пока длины не сравняются: B=370000

B>A – с нулями мы переборщили => B=37000 ** умножили на 1000

B*10=37000 B>A – верно

A=A-B*9=356395-333000=23395 ** умножили на 9

B=37000 – перебор => B=3700 ** умножили на 100

B*7=25900 B>A – верно

A=A-B*6=23395-22200=1195 ** умножили на 6

B=3700 – перебор => B=370 ** умножили на 10

B*4=1480 B>A – верно

A=A-B*3=1195-1110=85 ** умножили на 3

B=370 – перебор, B=37 ** умножили на 1

B*3=111 B>A – верно

A=A-B*2=85-74=11 ** умножили на 2

Всего потребовалось: 4 вычитания и 19 сложений (куда пропали умножения, смотрите в исходном коде)

А если бы мы пользовались простыми вычитаниями, то их потребовалось бы: 9632 штуки. Кстати, это и есть число K – целая часть от деления A на B, а ведь из приведённого примера мы можем вычленить это число, если обратим внимание на строки, помеченные **: если выпишем вынесенные числа, то получим: 1000 9 100 6 10 3 1 2. А теперь расставим арифметические знаки: 1000*9+100*6+10*3+1*2=9632. Это свойство используется в алгоритме деления.