Для п>п, значение и ограничено диапазоном

n, + \<n<n,+d-\, (9)

так как n>n,+d противоречит выбору как наибольшего значения п, такого, что rem(«,t/) = t/-l (кроме того, из (3,а) видно, что n>n+d влечет за собой и22*"). Из (4), для л > О, следует:

и тп п п+1. - < - <--. d 2" d

Путем элементарных алгебраических преобразований это неравенство может быть записано следующим образом:

п тп п,+1 (я-я,)(я, + 1) d 2 d dn,

Из (9) 1<л-л,<-1,такчто

dn, d

Поскольку (из (3,6)) n,>d~l и (п, +1)/" максимально при минимальном п„

О Л"-".)("с+1)/-Ы-1 + 1 dn, d d-l

В (10) член {n, + l)/d является целым числом. Член {n-n,){n, + \)/dn, меньше или равен 1. Следовательно, (10) становится

.п+1

Для всех п из диапазона (9) ln/dj = {n, + l)/d . Следовательно, (1,а) выполняется и в этом случае (п+1<л<л+</-1).

Для ж О из (4), так как т - целое число, имеем

d d п.

При умножении на л/2 с учетом того, что ж О, это выражение преобразуется:

л л,+ 1 тл л 2 +1

d п 2" d 2"

л л,+ 1

d п.

Применив теорему D2, получим:

n,{n,+\)-dn, + \ dn

л2+1

d 2"

+ 1.

n{2 + \)-2d + \

+ 1,

"и(я,+1) + 1"

+i<

"n(2+l) + r

Поскольку и+1 < 0, правое неравенство может быть ослаблено, что дает нам

I тп

п п + 1 - +

d dn.

+ 1<

Для -и, <и<-1

-и +1 и +1 ,

--<-<0 или

dn dn

d dn.

Следовательно, в силу теоремы D4

и и + 1 - +

d dn..

так что в данном случае (-п,<.п<~1) вьшолняется уравнение (1,6). При и < -и, величина п ограничена диапазоном

-n,-dunu-n,-l. (12)

(Исходя из (3,а), из n<-n,-d вытекает и < -2"", что невозможно.) Выполняя элементарные алгебраические преобразования в левой части (11), получаем

-и,-1 (и + и,)(и,+1) + 1

+ 1<

(13)

Для -n,-d<n<-n-l

{-d + l){n,+l) X {п + п,){п,+1) + 1 -{п,+1) + 1 1

dn, dn, dn, dn, d

Отношение {n, + l)/n, максимально при минимальном значении Пс, таким образом,

n,=d-l. Следовательно,

i-d + l)id-l + l) 1 {п + п,){п,+1) + 1

d{d-l)

-i<(£±iOKll)±i<o

Из (13), поскольку (-И, -l)/t/ - целое число, а прибавляемая величина находится между О и -1, получим:

-и-1

Для и из диапазона ~n,~d + l<n<~n,~l

-п-1

Следовательно, тп/2 +1 = [«/</], т.е. выполняется (1,6).

Последний случай, n--n,~d, может осуществиться только для некоторых значений d. Из (3,а) вытекает, что -и,-rf -г*", поэтому если п принимает указанное значение, то п = -п-rf =-2"" и, следовательно, и, =2""-rf. Таким образом, rem(2*,rf) = rem(n+rf,rf) = rf-l (т.е. является делителем 2*"+1).

Для рассматриваемого случая n--n,-d формула (6) имеет рещение p~W-l (наименьшее возможное значение р), поскольку при этом

«Дrf-гem(2rf)) =(2--rf)(rf-rem(2«-,rf)) =

= (2--rf)(rf-(rf-1)) =

= 2»--rf<2- = 2.

Тогда из (5)

Таким образом.

2"- + rf - rem(2-.rf) 2" + rf - (rf -1) 2" +1 ~ rf ~ rf ~\ rf

+ 1 =r

2"-+ 1-2"

rf г"-

-2"--rf

+ 1 =

-2"--l

+ 1 =

+ 1 =

так что уравнение (1,6) справедливо.

Этим завершается доказательство того, что если /и и р вычислены по формулам (5) и (6), то уравнения (1,а) и (1,6) выполняются для всех возможных значений п.

10.5. Знаковое деление на делитель, не превышающий -2

Поскольку знаковое целое деление удовлетворяет соотношению n + (-rf) = -(n+rf), вполне приемлемой реализацией будет генерация кода для деления n+rf с последующей командой обращения знака частного. (В этом случае мы не получим верный результат при делении на rf = -г"", но для этой и других отрицательных степеней 2 можно воспользоваться кодом из раздела 10.1, после которого пррсто изменить знак полученного результата.) Менять знак делимого при этом не следует из-за того, что делимое может оказаться максимальным по абсолютному значению отрицательным числом.

Однако можно избежать команды обращения знака. Схема такого вычисления имеет следующий вид:

при п<0;