Пытаясь найти обсуждение Кнута частное и остаток

Question

Кажется, я помню, как однажды прочитал в одной из глав tAOCP обсуждение Кнута вычисления целого отношения и остатка.Моя память состоит в том, что он утверждает, что невозможно вычислить одно без другого, и что он полагал, что результаты должны быть доступны для программиста.Проблема в том, что большинство языков программирования вынуждают программиста вычислять что-то вроде q = a / b, а затем r = a% b, но под капотом CPUB дважды выполнял один и тот же расчет, что является пустой тратой.

IЯ только что искал в MMIX Volume Fascicle 1 описание DIV в разделе 1.3.1, но я не нахожу обсуждения, которое мне кажется, вспомнить.

Может кто-нибудь сказать мне, вспоминают ли они подобное обсуждение,и где я могу это найти?

Answer 1

Следующее может быть тем, что вы ищете - это единственное упоминание, которое я нашел во всех томах TAOCP и (до) выпусков, выпущенных до сих пор.(Это всего лишь часть предложения, а не подробное обсуждение, но память может быть хитрой.) Из тома 1, глава 1, раздел 1.3 ′ (MMIX), в частности 1.3.1´ (описание MMIX).Как вы знаете, в «Арифметических операциях» операция DIV определяется таким образом, что DIV $X,$Y,$Z (если $Z не содержит ноль) устанавливает $X для хранения (нижнего) коэффициента значений в $Yи $Z и одновременно устанавливает регистр rR для хранения остатка.

Позже, в разделе «MMIX против реальности», второй пункт:

Коммерческие машиныкак правило, недостаточно в их поддержке целочисленной арифметики.Например, они почти никогда не производят истинное частное ⌊ x / y ⌋ и истинный остаток x mod y при x отрицательно или y отрицательно;они часто выбрасывают верхнюю половину продукта.Они не рассматривают сдвиги влево и вправо как строгие эквиваленты умножения и деления на степени 2. Иногда они вообще не реализуют аппаратное деление;и когда они обрабатывают деление, они обычно предполагают, что верхняя половина 128-битного дивиденда равна нулю.Такие ограничения усложняют высокоточные вычисления.