Есть ли ошибка в алгоритме 4.3.1D TAOCP Кнута?

Question

Вы можете найти объяснение Алгоритма 4.3.1D, как оно появляется в книге Art of The Computer Programming Vol. 2 (стр. 272-273) Д. Кнута в приложении к этому вопросу.

Похоже, что на этапе D.6 ожидается qhat быть выключенным не более чем на один.

Предположим, что base равен 2^32 (т.е. мы работаем с 32-разрядными цифрами без знака). Пусть u = [238157824, 2354839552, 2143027200, 0] и v = [3321757696, 2254962688]. Ожидаемый результат этого деления составляет 4081766756 Ссылка

И u, и v уже нормализованы, как описано в D.1 (v[1] > b / 2 и u дополняется нулями).

Первая итерация от l oop D.3 до D.7 не работает, поскольку qhat = floor((0 * b + 2143027200) / (2254962688)) = 0 in Первая итерация.

Во второй итерации l oop, qhat = floor((2143027200 * b + 2354839552) / (2254962688)) = 4081766758 Ссылка .

Нам не нужно вычислять шаги D .4 и D.5 , чтобы понять, почему это проблема. Так как qhat будет уменьшен на единицу в D.6 , результат алгоритма будет выглядеть как 4081766758 - 1 = 4081766757, однако, результат должен быть 4081766756 Link .

Правильно ли я считаю, что в алгоритме есть ошибка или в моих рассуждениях есть ошибка?

Приложение

Answer 1

ошибки нет; вы игнорируете l oop внутри шага D3:

В вашем примере, в результате этого теста, значение q̂, который первоначально был установлен на 4081766758, уменьшен в два раза, сначала до 4081766757, а затем до 4081766756, прежде чем перейти к шагу D4.

(Извините, у меня не было времени, чтобы сделать более подробный / «правильный» ответ .)