Арифметика чисел в b-ичной системе счисления (Длинная арифметика) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Подбор значения очередной цифры в алгоритме деления в столбик)
(Подбор значения очередной цифры в алгоритме деления в столбик)
Строка 24: Строка 24:
 
==Подбор значения очередной цифры в алгоритме деления в столбик==
 
==Подбор значения очередной цифры в алгоритме деления в столбик==
  
Подбор следующей цифры <tex>k \in [0, b]</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>\ln(b)</tex>.
+
Подбор следующей цифры <tex>k \in [0, b)</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>\ln(b)</tex>.

Версия 20:54, 28 мая 2011

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


Основная идея заключается в том, что число хранится в виде массива его цифр.

Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.

Представление в памяти

Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в b-й системе счисления.

Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).

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

Сложение, вычитание, умножение, деление на короткое, деление на длинное

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

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

Подбор значения очередной цифры в алгоритме деления в столбик

Подбор следующей цифры [math]k \in [0, b)[/math] частного можно производить с помощью стандартного алгоритма двоичного поиска за [math]\ln(b)[/math].