10.7. ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ 173

Программа для d = 3 , W = 32 оказывается короче программы для общего случая, поскольку в ней не требуется выполнение команд add и shrsi после команды mulhs. Возникает вопрос: для каких делителей программа также оказывается укороченной?

Рассмотрим только положительные делители. Итак, требуется найти целые числа т и р, которые удовлетворяют уравнениям (1,а) и (1,6) и для которых выполняются соотношения p = W и Ойтй г"". Поскольку любые целые числа тир, которые удовлетворяют уравнениям (1,а) и (1,6), должны также удовлетворять неравенству (4), достаточно найти те делители d, для которых (4) имеет решение при p = W и 0<.т< г"". Все решения (4) при p = W задаются уравнением

m=---, к = \,2,3...

Объединяя его с правой частью (4) и упрощая, получим

rem(2",t/)>W--. (21)

Наименьшим ограничением на rem(2",t/) является ограничение при =1 и равном своему минимальному значению 2*", так что

Km{2*,d)>d-A,

т.е. d является делителем 2" +1, 2" + 2 или 2" + 3 .

Посмотрим теперь, какие из данных делителей в действительности имеют оптимальные программы.

Если d является делителем 2" +1, то rem(2",</) =</-!. Тогда решением (6) является

p = W , так как неравенство превращается в очевидное:

2>n,{d-id-l)) = n„

поскольку и, < 2*. При вычислении т имеем

2"+t/-(t/-l) 2"+!

т =-=-,

и при d3 это Значение оказывается меньше, чем 2"" (d не может быть равно 2, поскольку является делителем г" +1). Следовательно, все делители 2" +1 имеют оптимальные программы.

Аналогично, если d является делителем 2*+2, то rem(2",t/) = t/-2. Здесь также решением (6) является p = W , поскольку неравенство также превращается в

2->n,{d~{d-2)) = 2n,, которое, очевидно, является истинным. Вычисление т дает значение

2 + d-{d-2) 2" + 2

т =-=-,

превьшающее г" -1 для d=2, но не превьшающее 2*" -1 гфи W г 3, rf й 3 (случай W=3 и rf=3 невозможен, поскольку 3 не является делителем 2 + 2 = 10). Следовательно, все делители 2* + 2, за исключением числа 2 и дополнигельнгапо ему (дсшолнительным к 2 делители является (2* + 2)/2, т.е. число, которое нельзя представить как W-битовое знаковое целое).

Если d является делителем 2* + 3, то показать, что оптимальной программы для него нет, можно следующим образом. Поскольку rem(2,rf) =rf-3, из неравенства (21) имеем

Самое слабое ограничение - при =1, так что < . Из (3,а) > г* -rf или rf > г*" -п,, следовательно:

Кроме того, поскольку 2, 3 и 4 не могуг быть делителями 2* + 3, наименьщим возможным делителем 2* + 3 является 5 и, следовательно, наибольший возможный делитель равен (2* +з)/5 . Таким образом, если d является делителем 2* + 3 н rf имеет оптимальную программу, то

2W 2"+3

- <rfS-.

Преобразуя данное неравенство, для дополнительного к d делителя (2" +3)/rf получаем следующие границы:

Эти границы указывают, что при W а 5 единственными возможными дополнительными делителями являются 5 и 6. При W<5 легко убедиться, что делителей 2+3 не существует. Поскольку б не может быть делителем 2* + 3, единственным возможным делителем этого числа может быть 5. Таким образом, единственным возможным делителем 2* + 3, который может иметь оптимальную программу, является (г* + 3)/5 .

Для rf = (2»+3)/5

(2»+3)/5

Г 2*+3

а так как для IV й 4

2<

(г+зуз

<2.5,

Эта величина превышает 2*/3 , так что d = [2 +3)15 оптимальной программы не имеет.

Поскольку для W <4 величина 2* + 3 делителей не имеет, можно сделать вывод о том, что делителей 2* + 3 с оптимальной программой не существует.

Резюмируем: все делители 2" +1 и 2* +2, за исключением 2 и (2* +2)2, имеют оптимальные программы, и никакие другие числа оптимальных программ не имеют. Более того, приведенное выше доказательство показывает, что алгоритм из листинга 10.1 всегда дает оптимальную программу, если таковая существует.

Рассмотрим частные случаи значений W, равные 16, 32 и 64. Соответствующие разложения на множители показаны ниже.

Следовательно, для W = 16 имеется 20 делителей, для которых существует оптимальная программа. Из них меньше 100 делители 3, 6, 9, 11, 18, 22, 33, 66 и 99.

Для W = 32 естьшесгьтакихдеш1телей:3, 6,641,6700417,715827883, 1431655766.

Для W = 64 есть 126 таких делителей. Из них меньше 100 делители 3, 6, 9, 18, 19, 27, 38,43,54,57 и 86.

10.8. Беззнаковое деление

Беззнаковое деление на величину, представляющую собой степень двойки, реализуется с помощью единственной команды сдвига вправо, а остаток - с помощью команды и с непосредственно задаваемым операндом.

Может показаться, что обработка других делителей должна быть несложной: просто использовать результаты для знакового деления с d>0, опуская две команды, которые добавляют 1 при отрицательном частном. Однако вы увидите, что некоторые детали беззнакового деления в действительности несколько сложнее.

Беззнаковое деление на 3

Начнем рассмотрение беззнакового деления на другие числа с беззнакового деления на 3 на 32-битовой машине. Поскольку делимое п теперь может достигать по величине 2-1, множитель [2+2)J3 оказывается неадекватен (член-ошибка 2пДз-2") может

превысить 1/3). Однако можно использовать множитель {2" + \)J3. Соответствующий код имеет вид

li М,ОхАААААААВ Загрузка магического числа (2**33-ь1)/3

mulhu q,M,n q = floor(M*n/2**32) shri q,q,l

muli t,q,3 Вычисление остатка по формуле

sub r,n,t г = n - q*3

10.8. БЕЗЗНАКОВОЕ ДЕЛЕНИЕ 175