Изменения

Перейти к: навигация, поиск
Вычитание
{{Определение
|definition=
'''Длинная арифметика ''' (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
}}
{{Определение
|definition=
'''Классическая длинная арифметика''' — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.
}}
==Представление в памяти==
 
Один из вариантов хранения длинных чисел — массив целых чисел '''int''', где каждый элемент — это одна цифра числа в <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> === Сложение ===Прибавляет к числу <tex>a</tex> число <tex>b</tex> и сохраняет результат в <tex>a</tex> : Алгоритм работает за <tex>O(max(n, m))</tex>, где <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] '''else''' a[i] += carry carry = a[i] <tex>\geqslant</tex> base '''if''' carry a[i] -= 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</tex> это одна цифра числа в '''длины чисел <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] -= 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> — длина длинного числа.
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложенияАлгоритм требует <tex>O(n)</tex> памяти, вычитания, умножения, деления столбикомгде <tex>n</tex> — длина длинного числа.
После совершения операций следует не забывать удалять лидирующие нули '''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>k O(n \in [0cdot m)</tex>, где <tex>n, b)m</tex> — длины чисел <tex>a</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за и <tex>\ln(b)</tex>.
Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки ('''qGuess''') по первым цифрамделителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированноправильного результата, однако неплохое приближение все же получится.Пусть очередной шаг представляет собой деление некоторого Алгоритм требует <tex>U = O(u_0, u_1, n \cdots, u_ncdot m)</tex> на памяти, где <tex>B = (b_0, b_1n, \cdots, b_{n-1})m</tex>.Если — длины чисел <tex>b_{n-1} \geqslant a</tex> '''BASE''' и <tex>/ 2b</tex> (где '''BASE''' — основание системы счисления), то можно доказать следующие факты:.
*1. Если положить '''qGuessfunction''' <tex> = getCompLongLong(u_n \cdot</tex><tex> a: '''vector</texint> '''BASE, b: ''' vector<texint>+\ u_{n-1}) / b_{n-1}</tex> , то '''qGuess): '''vector<texint>-2 \leqslant q \leqslant</tex> '''qGuess'''.Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного, carry = 0но может быть больше на <tex>1</tex> или <tex>2</tex>. i = 0*2. Если же дополнительно выполняется неравенство '''qGuesswhile'''i <tex> \cdot b_{n-2} ></tex> a.size() j = 0 '''BASEwhile''' (j <tex>\cdot r +\ u_{n-2}</tex> , где <tex>r</tex> – остаток при нахождении b.size() || carry) '''qGuess''' и '''qGuessif''' j <tex>≠</tex> '''BASE''', то '''qGuess''' b.size() cur = c[i + j] + a[i] <tex>-1 \leqslant q \leqslantcdot</tex> b[j] + carry '''qGuesselse''', причем вероятность события '''qGuess'''<tex> cur = q c[i + 1</tex> приблизительно равна <tex>2 / </tex> j] + carry c[i + j] = cur '''BASEmod'''.baseТаким образом, если <tex>b_{n-1} \geqslant < carry = cur /tex> base j++ i++ '''BASEwhile'''<tex>/2</tex>, то можно вычислить '''qGuess''' <tex> = c.size(u_n \cdot</tex><tex) >\ </tex>'''BASE''' <tex> + u_{n-1}&& c.back() / b_{n-1}</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия== 0 c. Получившееся значение будет либо правильным частным <tex>q</tex>, либо, с вероятностью <tex>2/</tex>pop_back() '''BASEreturn''', на единицу большим числом.c
Что делать, если === Деление длинного на короткое ===Делит длинное <tex>b_{n-1}a</tex> слишком мало, чтобы пользоваться таким способом?Например, можно домножить делитель и делимое на одно и то же число '''scale''' короткое <tex> = </tex> '''BASE'''b\, (b <tex> / ( b_{n-1} +1 base)</tex>. В случае, если основание системы счисления является степенью двойки, '''scale''' можно выбрать соответствующей степенью двойки.При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если '''qGuess''' получилось все же на единицу большим сохраняет в <tex>qa</tex>, будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен <tex>-1</tex>. Это сигнал, что необходимо прибавить одно B назад.Заметим, что остаток в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)carry</tex>).:
http:Алгоритм работает за <tex>O(n)</tex>, где <tex>n</forumtex> — длина длинного числа.sources.ru/index.php?showtopic=210512&hl=
Алгоритм не требует дополнительной памяти. '''function''' getDivLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>''' carry =0 i = Источники информации a.size() - 1 '''while''' i <tex>\geqslant</tex> 0 cur =a[i] + carry <tex>\cdot</tex> base a[i] =cur '''mod''' base* [http: carry = cur //ebase i--maxx '''while''' a.size() > 1 && a.back() == 0 a.ru/algo/big_integer e-maxx: Длинная арифметика]pop_back() '''return''' a
== См. также ==
*[[Системы счисления | Системы счисления]]
*[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]]
 
 
== Источники информации ==
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
 
 
[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Теория чисел]]
344
правки

Навигация