No Image

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

СОДЕРЖАНИЕ
4 просмотров
10 марта 2020

БлогNot. C++: умножение больших чисел

C++: умножение больших чисел

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

Проверено в консоли Visual Studio 2015.

Первая программка просто вычисляет 2 в сотой степени, используя функцию умножения обычного числа int на массив цифр, ответ

Вторая программа использует работу со строковыми буферами и говорит, что

Excel выводит число на 2 больше, но умножение в столбик легко показывает, что 2 последние цифры именно 38 🙂

28.02.2018, 13:56; рейтинг: 1476

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Тмк натяжные потолки отзывы

Вывод

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

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

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

Чтение

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

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

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

Сложение

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

Вычитание

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Как можно установить игру на компьютер

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Узнать имя держателя карты по номеру

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

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

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

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

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

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

Интересует не столько решение, сколько причина по которой программа выводит неверный результат

Результат выводится неверно. (Запускаю на 64х разрядном компиляторе)

2 ответа 2

Запустил. Получил 12517661106521999860 .

И что значит "неверный результат"? А какой результат вы ожидали?

В языках С и С++ беззнаковый тип uint64_t реализует арифметику по модулю 2 64 = 18446744073709551616 = UINT64_MAX + 1 .

Математически 15482202590115775738 * 2 дает 30964405180231551476 , что превышает 2 64 и по модулю 2 64 равно 12517661106521999860 .

Именно это число и выводит ваша программа. Все правильно.

Однако отдельно стоить заметить, что бессуффиксные целые литералы в С и С++ всегда имеют знаковый тип. И если литерал не помещается в самый большой знаковый тип long long и компилятор не хочет использовать какой-нибудь расширенный тип, то программа является некорректной (см. комментарий @jfs). На вашей платформе, я подозреваю, тип long long является 64-битным. Тогда правильно: 15482202590115775738u

Комментировать
4 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector