Главы:
Рассмотрим ещё один очень простой алгоритм деления.
Допустим нам нужно разделить 63 на 3. Для простоты будем использовать десятичную СС и обычный порядок цифр.
1) Максимальная длина результата = 2 − 1 + 1 = 2. Обнуляем массив результата:
результат = {0, 0}
2) Увеличим старший разряд результата на 1:
результат = {1, 0} // 10
3) Проверяем, что результат * знаменатель <= числитель:
{1, 0} * {3} <= {6, 3} // 30 <= 63
Условие выполняется.
4) Снова увеличим старший разряд на 1 и снова проверяем:
результат = {2, 0} // 20
{2, 0} * {3} <= {6, 3} // 60 <= 63
Условие выполняется.
5) Снова увеличим старший разряд на 1 и снова проверяем:
результат = {3, 0} // 30
{3, 0} * {3} <= {6, 3} // 90 <= 63
Условие не выполняется. Значит на предыдущем шаге был найден старший разряд результата.
6) Вычитаем из старшего разряда 1, чтобы вернуть предыдущее значение:
результат = {2, 0} // 20
7) Старший разряд мы подобрали, теперь начинаем увеличивать на 1 следующий разряд:
результат = {2, 1} // 21
{2, 1} * {3} <= {6, 3} // 63 <= 63
Условие выполняется.
8) Снова увеличиваем на 1 первый разряд (нумерация с 0):
результат = {2, 2} // 22
{2, 2} * {3} <= {6, 3} // 66 <= 63
Условие не выполняется. Значит на предыдущем шаге был найден первый разряд результата.
9) Вычитаем из первого разряда единицу:
результат = {2, 1} // 21
Разрядов больше нет, ответ получен.
Реализация: 3_brute_force_div_1.cpp.
Из-за перебора цифр этот алгоритм также очень медленный. В худшем варианте каждую цифру результата придётся проверять base раз. Подбор цифр можно значительно ускорить с помощью двоичного поиска. Релизация: 3_brute_force_div_2.cpp.
Проблемой остаётся то, что при каждой проверке длинные числа перемножаются целиком.
Источник: https://www.youtube.com/watch?v=vWIY5itZT-o&list=PLpPkxUHf9Qhj7K2DMCJrHdzMYIWEr008B&index=9.
Следующая глава: 4. Деление столбиком