Что такое длинная арифметика

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

Содержание

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

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

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

Операции над числами [ править ]

Операции над числами производятся с помощью «школьных» алгоритмов сложения, вычитания, умножения, деления столбиком. После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют. К ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.

Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией «школьных» алгоритмов действий в столбик:

[math]A = abc = 100 \cdot a + 10 \cdot b + c [/math]

[math]B = de = 10 \cdot d + e [/math]

Тогда сумма [math]A + B = abc + de = (100 \cdot a + 10 \cdot b + c) + (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b + d) + (c + e) [/math]

Произведение [math]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[/math]

Сложение [ править ]

Прибавляет к числу [math]a[/math] число [math]b[/math] и сохраняет результат в [math]a[/math] :

Алгоритм не требует дополнительной памяти.

Вычитание [ править ]

Отнимает от числа [math]a[/math] число [math]b\,(a \geqslant b)[/math] и сохраняет результат в [math] a[/math] :

Алгоритм не требует дополнительной памяти.

Умножение длинного на короткое [ править ]

Умножает длинное [math]a[/math] на короткое [math]b\, (b \lt base)[/math] и сохраняет результат в [math]a[/math] :

Алгоритм требует [math]O(n)[/math] памяти, где [math]n[/math] — длина длинного числа.

Умножение двух длинных чисел [ править ]

Умножает [math]a[/math] на [math]b[/math] и результат сохраняет в [math]c[/math] :

Деление длинного на короткое [ править ]

Источник

Длинная арифметика. Сложение, вычитание, умножение на короткое/длинное число

Числа, для представления которых в стандартных типах данных не хватает количества разрядов, называются длинными. Реализация арифметических операций над такими «длинными» числами называется длинной арифметикой. Задачи на «длинную» арифметику возникают, когда разрядности стандартных типов данных (целые, длинные целые, вещественные числа) не хватает чтобы хранить результат (настолько он велик).

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

Длинная арифметика используется:

Представление в компьютере длинных чисел

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

Классификация реализации длинной арифметики (преимущества и недостатки различных способов) Количество знаков может быть фиксированным (знаки хранятся в массиве с индексом от 0 до количества знаков минус 1) и с переменной длиной (отдельно ещё хравнится длина числа).

Разряды в позиционной системе счисления.

Для вычислений его удобно хранить в виде массива:

Алгоритмы чтения и записи длинных чисел

Ввод длинного числа из файла. Решение задачи начнем с описания данных.

При обработке каждой очередной цифры входного числа старшая цифра элемента массива с номером i становится младшей цифрой числа в элементе i + 1, а вводимая цифра будет младшей цифрой числа из А[1]. В результате работы нашего алгоритма мы получили число, записанное «задом наперед».

Задачи на длинную арифметику

Задача 1. (Районная олимпиада 1997).
Числа Фибоначчи выписываются подряд, начиная с Ф(1). Какая цифра будет на N-ом месте (N Указание: Ф(n+1) = Ф(n) + Ф(n-1); Ф(1) = Ф(2) = 1

Необходимо написать процедуру сложения «длинных» чисел (представленных в виде массивов отдельных разрядов A и B). В первой ячейке массива будем хранить «длину» числа (количество разрядов). Массив B содержит предыдущее вычисленное число Фибоначчи, а массив A – текущее число. Для удобства сложения полагаем Ф(0) = 0.

Программа на Basic для сложения 2 «длинных чисел» :

Реализация знаковой длинной целой арифметики для Delphi: cложение, вычитание, умножение и деление.

Источник

Длинная арифметика

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

Виды целочисленной длинной арифметики

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

Классическая длинная арифметика

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

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

Операции над числами в этом виде длинной арифметики производятся с помощью «школьных» алгоритмов сложения, вычитания, умножения, деления столбиком. Впрочем, к ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.

Здесь описана работа только с неотрицательными длинными числами. Для поддержки отрицательных чисел необходимо ввести и поддерживать дополнительный флаг «отрицательности» числа, либо же работать в дополняющих кодах.

Структура данных

Хранить длинные числа будем в виде вектора чисел , где каждый элемент — это одна цифра числа.

Для повышения эффективности будем работать в системе по основанию миллиард, т.е. каждый элемент вектора содержит не одну, а сразу цифр:

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

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

Вывод

Самое простое — это вывод длинного числа.

Сначала мы просто выводим самый последний элемент вектора (или , если вектор пустой), а затем выводим все оставшиеся элементы вектора, дополняя их нулями до символов:

(здесь небольшой тонкий момент: нужно не забыть записать приведение типа , поскольку в противном случае число будут беззнаковым, и если , то при вычитании произойдёт переполнение)

Чтение

Считываем строку в , и затем преобразовываем её в вектор:

Если использовать вместо массив ‘ов, то код получится ещё компактнее:

Если во входном числе уже могут быть лидирующие нули, то их после чтения можно удалить таким образом:

Сложение

Прибавляет к числу число и сохраняет результат в :

Вычитание

Отнимает от числа число () и сохраняет результат в :

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

Умножение длинного на короткое

Умножает длинное на короткое () и сохраняет результат в :

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

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

Умножение двух длинных чисел

Умножает на и результат сохраняет в :

Деление длинного на короткое

Делит длинное на короткое (), частное сохраняет в , остаток в :

Длинная арифметика в факторизованном виде

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

Этот метод также весьма прост для реализации, и в нём очень легко производить операции умножения и деления, однако невозможно произвести сложение или вычитание. С другой стороны, этот метод значительно экономит память в сравнении с «классическим» подходом, и позволяет производить умножение и деление значительно (асимптотически) быстрее.

Этот метод часто применяется, когда необходимо производить деление по непростому модулю: тогда достаточно хранить число в виде степеней по простым делителям этого модуля, и ещё одного числа — остатка по этому же модулю.

Длинная арифметика по системе простых модулей (Китайская теорема или схема Гарнера)

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

Как утверждает Китайская теорема об остатках, этого достаточно, чтобы однозначно хранить любое число в диапазоне от 0 до произведения этих модулей минус один. При этом имеется Алгоритм Гарнера, который позволяет произвести это восстановление из модульного вида в обычную, «классическую», форму числа.

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

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

Помимо этого, производить деление чисел в таком представлении по системе простых модулей не представляется возможным.

Виды дробной длинной арифметики

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

Длинная арифметика в несократимых дробях

Число представляется в виде несократимой дроби , где и — целые числа. Тогда все операции над дробными числами нетрудно свести к операциям над числителями и знаменателями этих дробей.

Обычно при этом для хранения числителя и знаменателя приходится также использовать длинную арифметику, но, впрочем, самый простой её вид — «классическая» длинная арифметика, хотя иногда оказывается достаточно встроенного 64-битного числового типа.

Выделение позиции плавающей точки в отдельный тип

Иногда в задаче требуется производить расчёты с очень большими либо очень маленькими числами, но при этом не допускать их переполнения. Встроенный -байтовый тип , как известно, допускает значения экспоненты в диапазоне , чего иногда может оказаться недостаточно.

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

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

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

Источник

Длинная арифметика

Определение

Для работы с “длинными” числами их разбивают на разряды. Размер разряда может быть произвольным, но чаще всего используются следующие:

(Ограничения на квадрат размера разряда связаны с необходимостью перемножать между собой разряды. Если квадрат разряда превышает ограничение своего типа, при умножении возможны переполнения.)

В большинстве реализаций разряды хранятся в порядке, обратным привычному для упрощения работы с ними. Например число \(578002300\) при размере разряда \(10^4\) представляется следующим массивом:

Количество разрядов числа может быть как ограничено, так и не ограничено, в зависимости от типа используемого контейнера: массива константной длины или вектора.

Реализация

Далее будет приведена реализация длинной арифметики, использующая размер разряда \(10^9\), и массив константой длины \(10\) для хранения разрядов. Таким образом, эта реализация позволяет быстро работать с числами до \(10^<90>\).

Реализация будет приведена в виде структуры bigint с перегруженными математическими операторами. Предполагается владение соответствующим материалом по C++.

Начнём с основных элементов структуры:

Сложение

Длинную арифметику часто сравнивают с детским вычислением “в столбик”. Это достаточно справедливо, так как оба методы основаны на поразрядных операциях. Если вы умеете складывать в столбик, то реализация длинного сложения не должна вызвать у вас трудностей:

Вычитание

Вычитание реализуется симметрично сложению:

Умножение

Реализация умножения немного отличается от алгоритма умножения в столбик, но принцип сохраняется: перемножим каждый разряд одного числа на каждый разряд другого. При умножении разряда \(i\) на разряд \(j\) добавим результат к разряду \(i + j\) произведения (0-индексация). После этого выполним переносы аналогично сложению:

Деление на короткое

В отличие от других арифметических операций, деление длинного числа на другое длинное реализуется достаточно сложно, и в школьных задачах вам вряд ли придётся им пользоваться.

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

Вывод длинного числа

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

Полный код структуры

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

Длинная арифметика в разных языках программирования

В последнее время на олимпиадах длинная арифметика встречается всё реже и реже, и есть вероятность, что скоро она исчезнет насовсем. Главным образом это связано с постепенным включением в списки допустимых языков Java и Python, в которых длинная арифметика встроена в стандартную библиотеку. Из-за этого необходимость реализовывать её самостоятельно полностью отпадает. Для уравнивания участников, использующих C++ с участниками, использующими Java и Python, составители задач стараются избегать задач на банальные длинные арифметические операции. Хотя сама концепция длинных чисел всё ещё встречается, задачи имеют несколько другой вид.

brestprog

Олимпиадное программирование в Бресте и Беларуси

Источник

Реализация длииииииинной арифметики на C++

Структура класса

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

В моей реализации будет сразу два представления нуля — в виде пустого вектора и в виде вектора с одним-единственным нулём.

Создание числа

Первое, что нужно научиться делать — это создавать число. Вот так оно преобразуется из строки, содержащей цифры:

Код процедуры удаления ведущих нулей прост до безобразия:

Также нам нужно уметь преобразовывать обычные числа в длинные:

Код преобразования из остальных типов еще проще, я не стал приводить его здесь.

Вывод числа

Теперь нам нужно научиться печатать наше число в поток и преобразовывать его в строку:

Сравнение чисел

Теперь нам нужно научиться сравнивать два числа друг с другом. Теория говорит, что для этого достаточно всего двух операций, остальные могут быть выведены на их основе. Итак, сначала научимся сравнивать два числа на равенство:

Теперь проверим, меньше ли одно число другого:

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

Знания о том, почему нужно возвращать const big_integer, а не просто big_integer, а также о правилах выбора между дружественной функцией-оператором и оператором-членом класса, я подчерпнул из этой статьи.

Дальше все совсем просто:

Арифметические операции

Сложение

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

Здесь я избежал «дорогой» операции деления в случае, когда получившаяся «цифра» больше основания, по которому я работаю, путем простого сравнения.

Вычитание

В принципе, вычитание аналогично сложению. Нужно лишь рассмотреть случай, когда уменьшаемое меньше вычитаемого:

Инкремент и декремент

Перед реализацией этих двух операций нам нужно реализовать сложение и вычитание с присвоением:

Тогда префиксные версии операций реализуются в одну строчку, а постфиксные — лишь немногим сложнее:

Умножение

Я не стал писать быстрое умножение Карацубы, а снова использовал «школьную» арифметику:

Деление

Поскольку я не нашел в Интернете быстрых способов деления, воспользуемся школьным делением уголком. Начнем делить со старших разрядов. Нам нужно уменьшить текущее значение делимого на максимально возможное число делимым. Это максимальное значение будем искать двоичным поиском. Но сначала нам нужно определить функцию «сдвига» числа вправо, которая позволит нам перебирать разряды последовательно:

Теперь опишем само деление:

Взятие остатка

Возведение в степень

Я использовал алгоритм быстрого возведения в степень. Он требует проверки числа на нечетность. Поскольку вычислять остаток от деления на 2, мягко говоря, было бы затратно, введем такие операции:

Теперь напишем само возведение:

Источник