Длинное DIV длинное & Длинное MOD длинное

[Вся длинная арифметика] 

Пришло время познакомиться с самой “страшной” операцией на длинную арифметику. Первый раз я ее реализовал на Accepted 31 июля 2008. До этого момента мне было даже страшно подумать над ее реализацией. Но как оказалось не так уж это деление и страшно, как его малюют. Мы не будем изобретать велосипед, а просто грамотно, максимально понятно и быстро реализуем деление столбиком. Рассмотрим нижепредставленный рисунок.

Как видно osn = 100.

Заметим факт, что количество разрядов у частного от деления не превосходит количества разрядов у делимого. Т.е. начинаем формировать ответ со старшего разряда. На каждой итерации имеем текущее значение, которое пытаемся уменьшить на максимально большое количество раз делимым. Итак: как будем искать это “максимально большое количество”? За ответом отсылаю в нашу любимую первую главу “Программирование в алгоритмах”. Ответ прост. Вместо того, чтобы линейно перебирать цифры в интервале от 0 до osn в поисках нужного ответа, мы будем использовать бинарный поиск.

Корректность этого утверждения вытекает из того, что рассматриваемая функция, которую можно представить в виде b * x(где b – делимое, x – подбираемое значение) является монотонной. В нашем случае возрастающей.

Оценим выигрыш в скорости относительно “лобовой реализации”. Для osn = 10000 предложенная реализация будет работать на 10000/log(10000) ~ 769 раз быстрее.

Рассмотрим конкретную реализацию целочисленного деления двух длинных чисел:

1. void LevelUp()
2. {
3.   for (int i = amount;i>=1;i--)
4.     digits[i] = digits[i-1];
5.   if (digits[amount])
6.     amount++;
7. }
8. ...
9. BigInt operator / (const BigInt &a, const BigInt &b)
10. {
11.   BigInt res;
12.   BigInt curValue;
13.   for (int i = a.amount-1; i>=0; i--)
14.   {
15.     curValue.LevelUp(); // * osn
16.     curValue.digits[0] = a.digits[i];
17.     // подбираем максимальное число x, такое что b * x <= curValue
18.     int x = 0;
19.     int l = 0, r = osn;
20.     while (l <= r)
21.     {
22.       int m = (l + r) >> 1;
23.       BigInt cur = b * m;
24.       if (cur <= curValue)
25.       {
26.         x = m;
27.         l = m+1;
28.       }
29.       else
30.         r = m-1;
31.     }
32.     res.digits[i] = x;
33.     curValue = curValue - b * x;
34.   }
35.   // избавляемся от лидирующих нулей
36.   int pos = a.amount;
37.   while (pos>=0 && !res.digits[pos])
38.     pos--;
39.   res.amount = pos+1;
40.  
41.   return res;
42. }

* This source code was highlighted with Source Code Highlighter.

Обратите внимание на строчку 20. Строгая проверка дает неправильное решение. Советую разобраться почему.

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

1. BigInt operator % (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   BigInt curValue;
5.   for (int i = a.amount-1; i>=0; i--)
6.   {
7.     curValue.LevelUp(); // * osn
8.     curValue.digits[0] = a.digits[i];
9.     // подбираем максимальное число x, такое что b * x <= curValue
10.     int x = 0;
11.     int l = 0, r = osn;
12.     while (l <= r)
13.     {
14.       int m = (l + r) >> 1;
15.       BigInt cur = b * m;
16.       if (cur <= curValue)
17.       {
18.         x = m;
19.         l = m+1;
20.       }
21.       else
22.         r = m-1;
23.     }
24.     res.digits[i] = x;
25.     curValue = curValue - b * x;
26.   }
27.   return curValue;
28. }

* This source code was highlighted with Source Code Highlighter.