Алгоритм MOD

[Dethlord]

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

[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.. Но это уже отдает каким-то шаманством

[AlexJ]

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

[Dethlord]

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

[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)

[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, то получается, что мы переборщили с умножением -> делим 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<B => 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. Это свойство используется в алгоритме деления!!!