Форум на Исходниках.RU

Алгоритм MOD

Dethlord — Tue, 30 Jan 2007 06:10:30 +0000

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

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

A mod A=0

A mod 1=0

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

1. 1234 mod 7=2

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

2. Итак, если A>B:

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

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

5. Если A делим B на 10

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

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

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

9. Результат=A

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

356395 mod 37=C, C=?

A=356395

B=37

A>B – верно

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

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

B*1=37000

B*2=74000

B*3=111000

B*4=148000

B*5=185000

B*6=222000

B*7=259000

B*8=296000

B*9=333000

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

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

A=23395

B=37

A>B – верно

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

B*1=3700

B*2=7400

B*3=11100

B*4=14800

B*5=18500

B*6=22200

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

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

A=1195

B=37

A>B – верно

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

B*1=370

B*2=740

B*3=1110

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

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

A=85

B=37

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

B*1=37

B*2=74

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

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

A=11

B=70

A C=11

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

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

Алгоритм MOD

AlexJ — Tue, 30 Jan 2007 05:06:54 +0000
AlexJ:
Цитата 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)

Алгоритм MOD

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

Алгоритм MOD

AlexJ — Tue, 30 Jan 2007 01:40:42 +0000
AlexJ: MOD=возвращает остаток от деления между двумя числами.

на ассемлере

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

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

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

Алгоритм MOD

kl — Tue, 30 Jan 2007 01:38:12 +0000
kl: Подсказки:
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
Соответственно, допустим, надо посчитать 201^675 mod 20. В лоб будет тоскливо. Но мы знаем, что 201 mod 20 = 1. Т.е. 201^675 = 1^675 | mod 20. Что равно 1.
В общем случае канешна будет посложнее, но идея, думаю понятна.

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

Алгоритм MOD

Dethlord — Tue, 30 Jan 2007 00:40:13 +0000
Dethlord: Каков внутренний алгоритм функции MOD.Смысл MOD я понимаю, но мне нужно зделать MOD свой(для длинных чисел).