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

[SlashMan]

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

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

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

P.S. а есть ли аналогичный способ если числа представлены в десятичной системе?

[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 = остаток

Только у меня к вам вопросик: почему длину массива С мы принимаем n+1 бит? Ведь тогда он может оказаться больше делителя, а остаток не может быть больше делителя

[DiemonStar]

рассмотрю на простом примере:
пусть в C содержится 1000b
а делитель B: 1001b
получить положительный результат при вычитании у нас не получится т.к. B>C, поэтому нам нужно заполнить С ещё одним битом (пусть будет "1"). Если разрядность одинакова, то: Cn = 0001b, хотя нам нужно значение C = 10001b для вычитания. Именно поэтому С должно быть как-минимум на один бит больше B.