Изменения

'''Длинная арифметика ''' (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.

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

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

==Сложение, вычитание, умножение, деление на короткое, деление на длинноеОперации над числами==

Тогда сумма <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>k A - B = abc - de = (100 \cdot a + 10 \in [0, cdot b+ c) - (10 \cdot d + e)</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>= 100 \cdot a + 10 \lncdot (b- d) + (c - e)</tex>.

Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки ('''qGuess''') по первым цифрамделителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированноправильного результата, однако неплохое приближение все же получится.Пусть очередной шаг представляет собой деление некоторого Произведение <tex>U A \cdot B = abc \cdot de = (u_0, u_1, 100 \cdot a + 10 \cdots, u_ncdot b + c)</tex> на <tex>B \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 (b_0, b_1, a \cdot e + b \cdots, b_{n-1}cdot d)</tex>.Если <tex>b_{n-1} + 10 \cdot (b \cdot e + c \cdot d) + c \geqslant </tex> '''BASE''' <tex>/ 2cdot e</tex> (где '''BASE''' — основание системы счисления), то можно доказать следующие факты:

*1. Если положить '''qGuess''' <tex> = (u_n \cdot</tex><tex> </tex> '''BASE''' <tex>+\ 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>2 / </tex> '''BASE'''.= Сложение ===Таким образом, если Прибавляет к числу <tex>b_{n-1} \geqslant a</tex> '''BASE'''число <tex>/2</tex>, то можно вычислить '''qGuess''' <tex> = (u_n \cdot</tex><tex>\ </tex>'''BASE''' <tex> + u_{n-1}) / b_{n-1}b</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным <tex>q</tex>, либо, с вероятностью сохраняет результат в <tex>2/a</tex>'''BASE''', на единицу большим числом.:

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

http://forumАлгоритм не требует дополнительной памяти.sources.ru/index.php?showtopic=210512&hl=

'''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] '''else''' a[i] +=carry carry =a[i] <tex>\geqslant</tex> base* '''if''' carry a[httpi] -= base i++ '''return''' a === Вычитание ===Отнимает от числа <tex>a</tex> число <tex>b\,(a \geqslant b)</tex> и сохраняет результат в <tex> a</tex>: Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</etex> — длины чисел <tex>a</tex> и <tex>b</tex>. Алгоритм не требует дополнительной памяти. '''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] '''else''' a[i] -maxx= 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 === Умножение длинного на короткое ===Умножает длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex> и сохраняет результат в <tex>a</tex> : Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.ru Алгоритм требует <tex>O(n)</algotex> памяти, где <tex>n</big_integer etex> — длина длинного числа.  '''function''' getCompLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>''' carry = 0 i = 0 '''while''' i < a.size() || carry '''if''' i == a.size() a.push_back(0) cur = carry + a[i] <tex>\cdot</tex> b; a[i] = cur '''mod''' base carry = cur / base i++ '''return''' a === Умножение двух длинных чисел ===Умножает <tex>a</tex> на <tex>b</tex> и результат сохраняет в <tex>c</tex> : Алгоритм работает за <tex>O(n \cdot m)</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>. Алгоритм требует <tex>O(n \cdot m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.  '''function''' getCompLongLong(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>''' carry = 0 i = 0 '''while''' i < a.size() j = 0 '''while''' (j < b.size() || carry) '''if''' j < b.size() cur = c[i + j] + a[i] <tex>\cdot</tex> b[j] + carry '''else''' cur = c[i + j] + carry c[i + j] = cur '''mod''' base carry = cur / base j++ i++ '''while''' c.size() > 1 && c.back() == 0 c.pop_back() '''return''' c === Деление длинного на короткое ===Делит длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex>, частное сохраняет в <tex>a</tex>, остаток в <tex>carry</tex> : Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа. Алгоритм не требует дополнительной памяти. '''function''' getDivLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>''' carry = 0 i = a.size() -maxx: Длинная арифметика1 '''while''' i <tex>\geqslant</tex> 0 cur = a[i] + carry <tex>\cdot</tex> base a[i]= cur '''mod''' base carry = cur / base i-- '''while''' a.size() > 1 && a.back() == 0 a.pop_back() '''return''' a