Объяснение алгоритма деления двухразрядных чисел по материалам Дональда Кнута

info@vsetut.pro

Стать автором

Вернуться

06.12.2025 20:22:43 | Хабр

Хабы: Математика, Программирование

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

Ограничимся делением двухразрядных чисел без знака. Деление чисел большей разрядности можно обобщить, при необходимости обратившись к первоисточнику [1]. Описываемый алгоритм назовем «программный 128/128». Заметим, что во многих 64-битных компиляторах он реализован (GCC, Clang, Intel Compiler) и может быть использован напрямую без изобретения велосипеда.

Цель данной статьи — подробно объяснить детали алгоритма, чтобы снизить порог входа в энциклопедические труды Д. Кнута, в том числе объяснить почему деление в процессоре дает лишь одноразрядное частное (конкретно для 64-битных процессоров можно делить 128-битное число на 64-битное, получая лишь 64-битное частное). Назовем процессорный алгоритм деления как «аппаратный 128/64».

Ключевым моментом в понимании алгоритма деления является процесс нормализации чисел, который позволяет воспользоваться встроенным в процессор делением 128/64.

Алгоритм деления двухразрядных чисел в зависимости от разрядности делителя разделяется на два: половинчатое деление, когда делитель по факту одноразрядный, и полное деление, когда делитель двухразрядный. Назовем первый алгоритм как «половинчатый программный», а второй как «полный программный». Заметим, что «аппаратный 128/64» является половинчатым; он будет использован в обеих ветках программного алгоритма.

Подробнее