Длинное^короткое (возведение в степень)

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

Данную операцию можно решить лобовым перемножением исходного числа, а можно воспользоваться быстрым возведением в степень:

1. BigInt pow(const BigInt &a, const int &N)
2. {
3.   BigInt res(1),cur = a;
4.   int n = N;
5.   while (n)
6.   {
7.     if (n&1)
8.       res = res * cur;
9.     cur = cur * cur;
10.     n>>=1;
11.   }
12.   return res;
13. }

* This source code was highlighted with Source Code Highlighter.

Стоит обратить внимание на то, что количество разрядов у результирующего числа очень быстро растет, поэтому нужно грамотно подбирать размерность массива digits в структуре BigInt.

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

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

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

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

Длинное DIV короткое & Длинное MOD короткое

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

При упоминании операции деления на длинных числах молодые олимпиадники резко меняются в лице, меняя веселые гримасы на хмурые лица. Скорее всего причиной тому являются разговоры более опытных товарищей, когда последние в красках обсуждают деление длинного на длинное. Об этой операции мы поговорим чуть позже. А пока спешу успокоить, т.к. деление длинного на короткое не сложнее, чем умножение длинного на короткое):

Длинное * длинное

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

Итак мы подошли к первой операции, реализацию которой можно считать не такой тривиальной, как в предыдущих случаях:

1. BigInt operator * (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   for (int i=0;i<a.amount;i++)
5.   {
6.     int r = 0;
7.     for (int j=0;j<b.amount | r;j++)
8.     {
9.       res.digits[i+j] += a.digits[i] * b.digits[j] + r;
10.       r = res.digits[i+j] / osn;
11.       res.digits[i+j] -= r*osn;
12.     }
13.   }
14.   int pos = a.amount + b.amount;
15.   while (pos>0 && !res.digits[pos])
16.     pos--;
17.   res.amount = pos + 1;
18.   return res;
19. }

* This source code was highlighted with Source Code Highlighter.

Обратим внимание на строчку 11. Т.к. алгоритм квадратичный, то избежание использования операции взятия остатка от деления(%) дает прирост в скорости, более ощутимый, чем для линейных алгоритмов.

Длинное * короткое

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

Умножение длинного числа на короткое является частным случаем умножения длинного на длинное. Но для того, чтобы данная операция работала быстрее общего случая, нужно позаботиться об индивидуальной реализации этой операции:

1. BigInt operator * (const BigInt &a, const int &n)
2. {
3.   BigInt res;
4.   res.amount = a.amount;
5.  
6.   int r = 0;
7.   for (int i=0;i<res.amount | r;i++)
8.   {
9.     res.digits[i] = a.digits[i] * n + r;
10.     r = res.digits[i]/osn;
11.     res.digits[i] -= r*osn;
12.   }
13.   if (res.digits[res.amount])
14.     res.amount++;
15.  
16.   return res;
17. }

* This source code was highlighted with Source Code Highlighter.

Как видно алгоритм линейный. Для ускорения операций в строке 11 мы избежали использования операции взятия остатка от деления(%).