Skip to content

Latest commit

 

History

History
134 lines (98 loc) · 8.61 KB

1_basics.md

File metadata and controls

134 lines (98 loc) · 8.61 KB
Raw

Главы:

  1. Основы длинной арифметики
  2. Длина неполного частного
  3. Деление путём подбора разрядов
  4. Деление столбиком

1. Основы длинной арифметики

Основание (base) системы счисления (СС) — число цифр:

  • в десятичной СС 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
  • в двоичной — две: 0, 1
  • в шестнадцатеричной — 16: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
  • и т.д.

В позиционной СС значение каждой цифры зависит от позиции (разряда). Например в числе 472 четыре сотни, семь десятков и две единицы: 4·100 + 7·10 + 2·1.

Разряды нумеруются с конца. Разряды слева — старшие, а справа — младшие. Номер разряда совпадает со степенью base: 4·102 + 7·101 + 2·100.

Большие числа можно хранить в виде массивов цифр (по одной цифре в каждом элементе массива). При этом математические операции придётся реализовать самостоятельно (например столбиком, как в школе).

Литература:

  1. https://e-maxx.ru/algo/big_integer (ещё в разделе bookz есть полезные Кнут и Окулов)
  2. https://ru.wikipedia.org/wiki/Длинная_арифметика
  3. https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
  4. https://ru.wikipedia.org/wiki/Позиционная_система_счисления

Внимание! Уже упомянутая литература в последующих темах не упоминается.

Сложение столбиком и реверс цифр

Пример:

  238
+ 932
 ────
 1170
  1. Складываем младшие разряды (единицы): 8 + 2 = 10. Так как 10 >= base (10), то есть перенос в следующий столбец
  2. Складываем разряды десятков: 3 + 3 + 1 = 7. Переноса в столбец сотен нет, так как 7 < 10
  3. Складываем разряды сотен: 2 + 9 + 0 = 11. Так как 11 >= 10, то есть перенос в столбец тысяч

Реализация этого алгоритма: 1_basics_add_1.cpp.

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

Тестировать код онлайн можно на сайтах:

  1. https://godbolt.org
  2. https://www.onlinegdb.com

Опции для GCC: -O0 -Wall -Wextra -Wpedantic -fsanitize=undefined -std=c++20.

В приведённом коде имеется 2 проблемы:

  1. Приходится добавлять цифры в начало массива
  2. Если числа разной длины, то приходится складывать цифры с разными индексами

Эти проблемы легко обойти, если хранить цифры в обратном порядке. Реализация: 1_basics_add_2.cpp.

Литература:

  1. https://en.wikipedia.org/wiki/Carry_(arithmetic)
  2. Гуровиц и Гольдштейн
  3. https://www.geeksforgeeks.org/sum-two-large-numbers/

Умножение столбиком и смена base

Рассмотрим программу 1_basics_mul_1.cpp, в которой реализовано умножение столбиком положительных десятичных чисел, а также ввод длинных чисел в виде строк. В каждом элементе массива (тип uint32_t) мы храним по одной десятичной цифре. Лучше будет использовать не десятичную СС, а СС с основанием 109 (в этой СС не 10 цифр, а 1'000'000'000 цифр). При этом массивы с цифрами будут короче, а значит будет меньше потребление памяти и быстрее вычисления.

Почему выбрано именно base 109?

  1. Числа из СС с основанием 10x легко преобразовывать в десятичные строки и обратно (одна цифра длинного числа содержит ровно x десятичных цифр)
  2. Тип uint32_t умещает 109 − 1, но не умещает 1010 − 1, поэтому base 1010 уже не годится

Таким образом, программа будет иметь вид: 1_basics_mul_2.cpp. Обратите внимание, что при промежуточных вычислениях используется тип uint64_t, который способен уместить значение base2 − 1.

Литература:

  1. https://en.wikipedia.org/wiki/Multiplication_algorithm#Other_notations
  2. http://cppalgo.blogspot.com/2010/05/blog-post.html
  3. https://www.geeksforgeeks.org/multiply-large-numbers-represented-as-strings/
  4. https://brestprog.by/topics/longarithmetics/

Вычитание столбиком

Рассмотрим программу 1_basics_sub_1.cpp, в которой реализовано вычитание столбиком длинных чисел. В целом, алгоритм похож на сложение 1_basics_add_2.cpp, только в нём происходит не перенос единицы в старший разряд, а заём единицы из старшего разряда. Так как цифры хранятся в типе uint32_t, то перед вычитанием цифр производится сравнение, чтобы результатом вычисления не стало отрицательное число (и переполнение). Для избавления от лишних ветвлений воспользуемся тем фактом, что в C++ при преобразовании bool в число всегда получается 0 или 1.

uint32_t borrow = minuend_digit < subtrahend_digit;
assert(borrow == 0 || borrow == 1);

Таким образом, программа будет иметь следующий вид: 1_basics_sub_2.cpp.

Деление путём вычитаний и сравнение

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

Пример: 91 / 8 = 91 − 8 − 8 − 8 − 8 … Восьмёрку удаётся вычесть 11 раз (значит неполное частное = 11) и остаётся 3, которая меньше 8.

Таким образом, для данного алгоритма также потребуется операция сравнения. Реализация: 1_basics_div.cpp. Обратите внимание, что при сравнении очень важно, чтобы у чисел не было ведущих нулей.

Недостатоком алгоритма является то, что если числитель большой, а знаменатель маленький, то число циклов будет огромным.

Литература:

  1. https://ru.wikipedia.org/wiki/Алгоритм_деления#Деление_путём_вычитаний
  2. https://en.wikipedia.org/wiki/Division_algorithm

Следующая глава: 2. Длина неполного частного