Остаток от деления длинного числа на длинное число

[SlashMan]

Доброго времени суток, уважаемые форумчане!

Есть такая задача:
Реализовать нахождение остатка от деления большого числа на большое число (оба числа представляют собой массив int где каждый элемент - разряд числа, младший разряд - нулевой элемент массива, старший разряд - последний элемент массива), известно что делимое по длине максимум в два раза больше делителя

Решение задачи "в лоб", то есть вычитанием делимого из делителя в цикле пока не получим остаток мне кажется здесь жутко неудобным

Что можете посоветовать? Какие мысли у вас есть на этот счет?

Заранее спасибо!


P.S. Проект разрабатывается в Visual Studio на C++, а ассемблерный код размещается во вставке после определения числовых массивов

[alexcoder]

Вот, когда-то делал деление. Не оптимизировано.

[evg_m]

( a x + b ) mod z == ( (a mod z) x + b ) mod z

делать аналогично делению в столбик но без хранения результата
надеюсь будет понятно
1234 mod 11 =?
11
----------------
_134 mod 11 =?
_11
-----------------
__24 mod 11 =?
__11
--------------
__13 mod 11 =?
__11 mod 11
----------------
___2 <11 =2

[DiemonStar]

как я понимаю, длина чисел должна быть произвольной?
на мой взгляд, самым быстрым решением будет вычитание с побитным сдвигом. т.е.

если длина делимого(A) = m бит, а длина делителя (B) = n бит

1. создаём проверочный массив C = n+1 бит
2. копируем в младшие n бит массива C n старших бит из A

3. сравниваем B и C
4. если C > B, тогда C = C - B, а частное D = (D shl 1) + 1
5. иначе D = D shl 1
6. С = С shl 1 + следующий разряд из A
7. если в А разрядов больше не оставалось, тогда:

D = частное
C = остаток

[SlashMan]

Сообщение от DiemonStar

как я понимаю, длина чисел должна быть произвольной?
на мой взгляд, самым быстрым решением будет вычитание с побитным сдвигом. т.е.

если длина делимого(A) = m бит, а длина делителя (B) = n бит

1. создаём проверочный массив C = n+1 бит
2. копируем в младшие n бит массива C n старших бит из A

3. сравниваем B и C
4. если C > B, тогда C = C - B, а частное D = (D shl 1) + 1
5. иначе D = D shl 1
6. С = С shl 1 + следующий разряд из A
7. если в А разрядов больше не оставалось, тогда:

D = частное
C = остаток

Да, вы правы, длина чисел абсолютно произвольная
У меня к вам вопрос по алгоритму: что изначально представляет из себя D? Должен быть заполнен нулями? А то просто от делимого и делителя он совсе получается независим изначально

[SlashMan]

Сообщение от evg_m

( a x + b ) mod z == ( (a mod z) x + b ) mod z

делать аналогично делению в столбик но без хранения результата
надеюсь будет понятно
1234 mod 11 =?
11
----------------
_134 mod 11 =?
_11
-----------------
__24 mod 11 =?
__11
--------------
__13 mod 11 =?
__11 mod 11
----------------
___2 <11 =2

Интересно, я попробую, спасибо
Если будут вопросы - я отпишу здесь

[DiemonStar]

что изначально представляет из себя D? Должен быть заполнен нулями?

и D и С должны быть нулевыми...

[SlashMan]

Сообщение от DiemonStar

как я понимаю, длина чисел должна быть произвольной?
на мой взгляд, самым быстрым решением будет вычитание с побитным сдвигом. т.е.

если длина делимого(A) = m бит, а длина делителя (B) = n бит

1. создаём проверочный массив C = n+1 бит
2. копируем в младшие n бит массива C n старших бит из A

3. сравниваем B и C
4. если C > B, тогда C = C - B, а частное D = (D shl 1) + 1
5. иначе D = D shl 1
6. С = С shl 1 + следующий разряд из A
7. если в А разрядов больше не оставалось, тогда:

D = частное
C = остаток

В пункте 4 возникает проблема с вычитанием: как мне оптимально реализовать вычитание двух таких чисел? использовать вычитание столбиком? или есть что полегче и побыстрее?

[SlashMan]

Кстати, забыл сказать, что делитель по которому берется модуль состоит в двоичной записи только из единиц, то есть представляет собой число 2^n-1, может это как-нибудь может упростить использование алгоритма

[DiemonStar]

Всё от конкретной реализации зависит. Если на чистом ассемблере делать, то там ничего сложного я не вижу...