Самостоятельное программирование операторов div и mod.

Пусть:
type
TDigit = 0..9;
TLN = array [0..10000] of TDigit;
{LN — имеется ввиду LongNumber}
var
LN1,LN2:TLN;

Вопрос:
помогите с алгоритмом отыскания LN1 div LN2 и LN1 mod LN2.

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

Здравствуйте, Аноним, Вы писали:

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

{для LN1 div LN2 & LN1 mod LN2:}
tmp := LN1;
divres := 0; {результат операции div будет здесь}
while tmp >= LN2 do begin
  tmp := tmp - LN2
  inc(divres);
end;
modres := tmp; {результат операции mod будет здесь}

если у тебя еще нет таких операторов, то следует их написать

Здравствуйте, atomheart, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

A>если у тебя уже есть операторы сложения и вычитания, то можно использовать такой алгоритм:

A>

A>{для LN1 div LN2 & LN1 mod LN2:}
A>tmp := LN1;
A>divres := 0; {результат операции div будет здесь}
A>while tmp >= LN2 do begin
A>  tmp := tmp - LN2
A>  inc(divres);
A>end;
A>modres := tmp; {результат операции mod будет здесь}

A>

A>если у тебя еще нет таких операторов, то следует их написать

Это будет ОЧЕНЬ, ОЧЕНЬ долго.

Если очень хочеться сделать самому "длинную" арифметику, то надо читать Кнута.

Я бы посоветовал найти уже готовую реализацию. Порекомендовать могу CryptoPP, смотреть класс Integer.

Здравствуйте, atomheart, Вы писали:

A>если у тебя уже есть операторы сложения и вычитания, то можно использовать такой алгоритм:
[]
А скорость какая будет? Нет уж, надо делать честное деление в столбик. Для двоичных чисел алгоритм такой:

Сдвигаем делитель влево до тех пор, пока старший бит не станет 1, запоминаем количество сдвигов.
Повторяем столько раз, сколько было сдвигов:
(
если делитель (модифицированный) меньше делимого, то вычитаем его из делимого, очередной бит ответа — 1
иначе очередной бит ответа — 0
сдвигаем делитель вправо
)

Примерный код:

// Проверка делителя на 0 опущена
// dividend - делимое
// divisor  - делитель
// result   - частное
shift_сounter = 0;
while (!get_high_bit(divisor))
{
    shift_left(divisor);
    ++shift_counter;
}
// В этот момент делитель имеет вид 1xxx
result = 0;
while (shift_counter > 0)
{
    shift_left(result);
    if (divisor <= dividend)
    {
        inplace_subtract(dividend, divisor);
        set_low_bit(result);
    }
    shift_right(divisor);
    --shift_counter;
}
// Остаток от деления в dividend

Пример: делим 126(1111110) на 25(11001)

 1111110
-1100100 1 -> частное (старший бит)
 -------
  011010
 -000000 0 -> частное (поскольку на этом шаге делитель > делимого, вычитания нет)
  ------
   11010
  -11001 1 -> частное
   -----
   00001 (это остаток)

Получается ответ 5(101) (собираем сверху вниз), остаток 1(1).

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

Есть более скоростные алгоритмы, которые основаны на обработке не одного бита за раз, а сразу группы бит (2, 4, 8), но они сложнее.