Арифметика чисел в b-ичной системе счисления (Длинная арифметика) — различия между версиями
Senya (обсуждение | вклад) (английские термины, <tex>) (Метки: правка с мобильного устройства, правка из мобильной версии) |
Senya (обсуждение | вклад) (источники, см.также, знаки неравенств) (Метки: правка с мобильного устройства, правка из мобильной версии) |
||
Строка 30: | Строка 30: | ||
правильного результата, однако неплохое приближение все же получится. | правильного результата, однако неплохое приближение все же получится. | ||
Пусть очередной шаг представляет собой деление некоторого <tex>U = (u_0, u_1, \cdots, u_n)</tex> на <tex>B = (b_0, b_1, \cdots, b_{n-1})</tex>. | Пусть очередной шаг представляет собой деление некоторого <tex>U = (u_0, u_1, \cdots, u_n)</tex> на <tex>B = (b_0, b_1, \cdots, b_{n-1})</tex>. | ||
− | Если <tex>b_{n-1} \ | + | Если <tex>b_{n-1} \geqslant </tex> '''BASE''' <tex>/ 2</tex> (где '''BASE''' — основание системы счисления), то можно доказать следующие факты: |
− | *1. Если положить '''qGuess''' <tex> = (u_n \cdot</tex><tex> </tex> '''BASE''' <tex>+\ u_{n-1}) / b_{n-1}</tex> , то '''qGuess'''<tex>-2 \ | + | *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>. | но может быть больше на <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 \ | + | *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} \ | + | Таким образом, если <tex>b_{n-1} \geqslant </tex> '''BASE'''<tex>/2</tex>, то можно вычислить '''qGuess''' <tex> = (u_n \cdot</tex><tex>\ </tex>'''BASE''' <tex> + u_{n-1}) / b_{n-1}</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным <tex>q</tex>, либо, с вероятностью <tex>2/</tex>'''BASE''', на единицу большим числом. |
Что делать, если <tex>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом? | Что делать, если <tex>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом? | ||
Строка 44: | Строка 44: | ||
http://forum.sources.ru/index.php?showtopic=210512&hl= | http://forum.sources.ru/index.php?showtopic=210512&hl= | ||
+ | |||
+ | == Источники информации == | ||
+ | * [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика] | ||
+ | |||
+ | == См. также == | ||
+ | *[[Системы счисления | Системы счисления]] | ||
+ | *[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]] |
Версия 16:41, 11 мая 2018
Определение: |
Длинная арифметика (англ. arbitrary-precision arithmetic, или bignum arithmetic) — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. |
Основная идея заключается в том, что число хранится в виде массива его цифр.
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.
Содержание
Представление в памяти
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в b-й системе счисления.
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
Сложение, вычитание, умножение, деление на короткое, деление на длинное
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
Подбор значения очередной цифры в алгоритме деления в столбик
Подбор следующей цифры
частного можно производить с помощью стандартного алгоритма двоичного поиска за .Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки (qGuess) по первым цифрам делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно правильного результата, однако неплохое приближение все же получится. Пусть очередной шаг представляет собой деление некоторого
на . Если BASE (где BASE — основание системы счисления), то можно доказать следующие факты:- 1. Если положить qGuess BASE , то qGuess qGuess.
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного, но может быть больше на
или .- 2. Если же дополнительно выполняется неравенство qGuess BASE , где – остаток при нахождении qGuess и qGuess BASE, то qGuess qGuess, причем вероятность события qGuess приблизительно равна BASE.
Таким образом, если
BASE , то можно вычислить qGuess BASE и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным , либо, с вероятностью BASE, на единицу большим числом.Что делать, если
слишком мало, чтобы пользоваться таким способом? Например, можно домножить делитель и делимое на одно и то же число scale BASE . В случае, если основание системы счисления является степенью двойки, scale можно выбрать соответствующей степенью двойки. При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если qGuess получилось все же на единицу большим , будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен . Это сигнал, что необходимо прибавить одно B назад. Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос ).http://forum.sources.ru/index.php?showtopic=210512&hl=