Изменения

Один из вариантов хранения длинных чисел — массив целых чисел <tex>'''int</tex>''', где каждый элемент — это одна цифра числа в ''<tex>b''</tex>-ичной системе счисления.Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит <tex>9</tex> цифр): '''const''' '''int''' base <tex>\,=\,</tex> 1000 <tex>\cdot</tex> 1000 <tex>\cdot</tex> 1000 

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

К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [https://ru.wikipedia.org/wiki/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%9A%D0%B0%D1%80%D0%B0%D1%86%D1%83%D0%B1%D1%8B Алгоритм Карацубы]. Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик: <tex>A = abc = 100 \cdot a + 10 \cdot b + c </tex> <tex>B = de = 10 \cdot d + e </tex> Тогда сумма <tex>A + B = abc + de = (100 \cdot a + 10 \cdot b + c) + (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b + d) + (c + e) </tex> Разность <tex>A - B = abc - de = (100 \cdot a + 10 \cdot b + c) - (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b - d) + (c - e) </tex> Произведение <tex>A \cdot B = abc \cdot de = (100 \cdot a + 10 \cdot b + c) \cdot (10 \cdot d + e) = 100 \cdot a \cdot 10 \cdot d + 10 \cdot b \cdot 10 \cdot d + c \cdot 10 \cdot d + 100 \cdot a \cdot e + 10 \cdot b \cdot e + c \cdot e = 1000 \cdot a \cdot d + 100 \cdot (a \cdot e + b \cdot d) + 10 \cdot (b \cdot e + c \cdot d) + c \cdot e</tex>

<font color=green>//Прибавляет к числу <tex>a </tex> число <tex>b </tex> и сохраняет результат в <tex>a</tex> : Алгоритм работает за <tex>O(max(n, m))</fonttex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>. Алгоритм не требует дополнительной памяти.  '''function''' getSum(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>''' carry = 0 i = 0 '''while''' i < max(a.size(),b.size()) || carry '''if''' i == a.size() a.push_back (0) '''if''' i < b.size() a[i] += carry + (b[i < b.size() ? b] '''else''' a[i] : 0)+= carry carry = a[i] <tex>\geqslant</tex> base '''if''' carry a[i] -= base i++ '''return''' a 

<font color=green>//Отнимает от числа <tex>a </tex> число <tex>b \,(a <tex>\geqslantb)</tex> b) и сохраняет результат в <tex> a</tex>: Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</fonttex>. Алгоритм не требует дополнительной памяти. '''function''' getSub(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>''' carry = 0 i = 0 '''while''' i < b.size() || carry '''if''' i < b.size() a[i] -= carry + (b[i < b.size() ? b] '''else''' a[i] : 0)-= carry carry = a[i] < 0 '''if''' carry a[i] += base i++ '''while''' a.size() > 1 && a.back() == 0 a.pop_back() <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font> '''return''' a 

Умножает длинное <font color=greentex>a<//Умножает длинное a tex> на короткое <tex>b \, (b < base) </tex> и сохраняет результат в a:</fonttex> carry = 0 i = 0 '''while''' i < a.size() || carry '''if''' i == a.size() a.push_back (0) '''long long''' cur = carry + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> b; a[i] = cur '''mod''' base carry = cur / base i++ '''while''' a.size() > 1 && a.back() == 0 a.pop_back() <font color=green>//Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>:

=== Умножение двух длинных чисел === Алгоритм работает за <font color=greentex>O(n)<//Умножает a на b и результат сохраняет в c:tex>, где <tex>n</fonttex> carry = 0 i = 0 '''while''' i < a— длина длинного числа.size() j = 0 '''while''' (j Алгоритм требует < b.sizetex>O(n) || carry) '''long long''' cur = c[i+j] + a[i] <tex>\cdot</tex> 1ll памяти, где <tex>\cdotn</tex> (j < (int)b— длина длинного числа.size() ? b[j] : 0) + carry c[i+j] = cur '''mod''' base carry = cur / base i++ j++ '''while''' c.size() > 1 && c.back() == 0 c.pop_back()

=== Деление длинного на короткое === '''function''' getCompLongShort(a: '''vector<font color=greenint>//Делит длинное a на короткое ''', b (b < base: '''int'''), частное сохраняет в a, остаток в carry:'''vector</fontint>''' carry = 0 i = a.size()-10 '''while''' i \geqslant 0< a.size() || carry '''long longif''' i == a.size() a.push_back(0) cur = carry + a[i] + carry <tex>\cdot</tex> 1ll <tex>\cdot</tex> baseb; a[i] = cur '''mod''' base carry = cur / base i--++ '''whilereturn''' a.size() > 1 && a.back() == 0 a.pop_back()

Подбор следующей цифры Алгоритм требует <tex>k O(n \in [0cdot m)</tex> памяти, b)где <tex>n, m</tex> — длины чисел <tex>a</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за и <tex>\ln(b)</tex>.

Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки '''function''' getCompLongLong(a: '''vector<int>'qGuess'', b: '''vector<int>''') по первым цифрам: '''vector<int>''' carry = 0делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно i = 0правильного результата, однако неплохое приближение все же получится '''while''' i < a.size()Пусть очередной шаг представляет собой деление некоторого <tex>U j = 0 '''while''' (u_0, u_1, \cdots, u_n)j </tex> на <tex>B = b.size(b_0, b_1, \ldots, b_{n-1})|| carry) '''if''' j </tex>b.size()Если cur = c[i + j] + a[i] <tex>b_{n-1} \geqslant cdot</tex><tex>\frac{BASE}{2}<b[j] + carry '''else''' cur = c[i + j] + carry c[i + j] = cur '''mod''' base carry = cur /texbase j++ i++ '''while''' c.size() > 1 && c.back(где ) == 0 c.pop_back() '''BASEreturn''' — основание системы счисления), то можно доказать следующие факты:c

*1. Если положить '''qGuess''' <tex> = \frac{ (u_n \cdot BASE + \ u_{n-1}) }{ b_{n-1} }</tex> , то '''qGuess'''<tex>-2 \leqslant q \leqslant</tex> '''qGuess'''.Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,но может быть больше == Деление длинного на <tex>1</tex> или <tex>2</tex>.*2. Если же дополнительно выполняется неравенство '''qGuess'''<tex> \cdot b_{n-2} ></tex> '''BASE''' <tex>\cdot r +\ u_{n-2}</tex> , где <tex>r</tex> – остаток при нахождении '''qGuess''' и '''qGuess''' <tex>≠</tex> короткое '''BASE''', то '''qGuess''' <tex>-1 \leqslant q \leqslant</tex> '''qGuess''', причем вероятность события '''qGuess'''<tex> = q + 1</tex> приблизительно равна <tex>\frac{2}{BASE}</tex>.==Таким образом, если Делит длинное <tex>b_{n-1} \geqslant a</tex> на короткое <tex>b\frac{BASE}{2}</tex>, то можно вычислить '''qGuess''' (b <tex> = \frac{ (u_n \cdot BASE + \ u_{n-1}base) }{ b_{n-1} }</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным частное сохраняет в <tex>qa</tex>, либо, с вероятностью остаток в <tex>\frac{2}{BASE}carry</tex>, на единицу большим числом.:

Что делать, если Алгоритм работает за <tex>b_{O(n-1})</tex> слишком мало, чтобы пользоваться таким способом?Например, можно домножить делитель и делимое на одно и то же число '''scale''' где <tex> = \frac{BASE}{b_{n-1} + 1}</tex>. В случае, если основание системы счисления является степенью двойки, '''scale''' можно выбрать соответствующей степенью двойки.При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если '''qGuess''' получилось все же на единицу большим <tex>q</tex>, будем использовать вычитание, которое вместо отрицательного — длина длинного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен <tex>-1</tex>. Это сигнал, что необходимо прибавить одно B назад.Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>).

Алгоритм не требует дополнительной памяти. '''function''' getDivLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>''' carry = 0 i = a.size() - 1 '''while''' i <tex>\geqslant</tex> 0 cur = a[http:i] + carry <tex>\cdot</tex> base a[i] = cur '''mod''' base carry = cur /forumbase i-- '''while''' a.sourcessize() > 1 && a.ru/index.php?showtopicback() =210512&hl= Источник]0 a.pop_back() '''return''' a