Пусть Пс - наибольшее (положительное) значение п, такое, что rem(n.,t/) = d-l. Оно существует, поскольку имеется, как минимум, одно возможное значение n,=d-\. Его можно вычислить как

= [i-/dld-1=г""- - Km{f-\d) -1.

Поскольку Пс представляет собой одно из d наибольших допустимых значений п, то

2"--t/S«,2"--l (3,а)

и, очевидно,

n,>d-l. (3,6)

Поскольку (1,а) должно выполняться при п-п,

Объединяя полученный результат с (2), получим

2" 2" п+1

- <т<--

t/ d п..

Поскольку /и должно быть наименьшим целым, удовлетворяющим (4), оно представляет собой целое число, следующее за lJd, т.е.

2+d-rem(2t/)

Комбинируя полученную формулу с правой частью (4), получим:

2>n,(t/-rem(2t/))

Алгоритм

Таким образом, алгоритм поиска магического числа М и величины сдвига s для данного делителя d начинается с вычисления Пс, а затем неравенство (6) решается путем подстановки последовательных возрастающих значений. Если р < W , то устанавливаем р = W (теорема ниже показывает, что данное значение также удовлетворяет неравенству (6)). Когда найдено наименьшее р > W , удовлетворяющее неравенству (6), из (5) вычисляется значение т. Это наименьшее возможное значение т, поскольку нами найдено наименьшее приемлемое р, а из (4) понятно, что, чем меньше значение р, тем меньше и значение т. И наконец, s = p-W и Л/ просто являются интерпретацией т как знакового целого числа (как оно рассматривается командой mulhs).

То, что при р < W мы устанавливаем p = W , обосновывается следующей теоремой.

Теорема DC1. Если для некоторого значения р справедливо неравенство (6), то оно справедливо и для больших значений р.

Доказательство. Предположим, что неравенство (6) справедливо для р = Ро • Умножение (6) на 2 дает

2**>n,(2rf-2rem(2*,d)). Из теоремы D5 rem(2**",d) > ггетг" ,d) - d . Объединяя эти выражения, получим

2">n,(2d-(rem(2**,d) + d)) или г**>n,(d-rem(2**,d)).

Следовательно, неравенство (6) справедливо для р = +1, а потому и для всех больших значений.

Таким образом, можно решить (6) путем бинарного поиска, хотя, по-видимому, предпочтительнее простой линейный поиск, начинающийся со значения р = W , поскольку d обычно мало, а малые значения d приводят к малым значениям р.

Доказательство пригодности алгоритма

Покажем, что (6) всегда имеет решение и что О S m < 2* (нет необходимости показывать, что р S W , так как это условие выполняется принудительно).

Покажем, что (6) всегда имеет решение, получив верхнюю границу р. Кроме того, в познавательных целях получим также нижнюю границу в предположении, что р не обязано быть равным как минимум W. Для получения указанных границ р заметим, что для любого положительного целого х существует степень 2, большая jc и не превосходящая 2х. Следовательно, из (6):

n,(rf-rem(2,d))< 2" < 2n,(d-rem(2,d)). Поскольку 0<rem(2,d)<d-l,

n,+lu2u2n,d. (7)

Из (3,a) и (3,6) получаем Snmx(2*"-d,d-l). Графики функций f{d) = 2-d и f,(d) = d-l в точке d = (г*"+ l)/2. Следовательно, >(г*"-l)/2. Поскольку -целое число, > г*". С учетом того, что n,d й г*" -1, (7) превращается в

2«-=+lS2S2(2--lf

W-lup<2W-2. (8)

Нижняя граница p = W~l вполне может быть достигнута (например, для W=32, d=3),

но в этом случае мы устанавливаем p = W .

Если не делать р равным W принудительно, то из (4) и (7) получаем

и +1 2nd п +1 -<т<---.

Применение (3,6) дает

<т<2{п+\).

Так как п,<2*--1 (3,а),

2<т<2*-1.

Если р принудительно делается равным W, то из (4) получаем

2* 2" п,+\

- <т<----.

Поскольку 2<d<2*- -1 и S г*",

2W 2«2"-Ч1

3<т<2*-+1.

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

Доказательство корректности произведения

Покажем, что если рят вычисляются из <6) и (5), то выполняются уравнения (1,а) и (1,6).

Уравнение (5) и неравенство (б), как легко видеть, имеют следствием (4). (В случае, когда р принудительно приравнивается к W, как показывает теорема DC1, неравенство (6) остается справедливым.) Далее рассмотрим отдельно пять диапазонов значений п:

и, +1<п<п+г/-1, -и <п<-1, -n,-d + l<nu-n-l и п = -п-d .

Из (4), поскольку т - целое число, следует:

- < m S-.

d dn.

При умножении на п/2 для и > О это соотношение превращается в

и тп 2<пЫ+1)-п

- <,-<-----, так что

d 2" 2dn

Если 0<п5п,,то 0<(2-l)n/(2d4„)<l/t/,так что по теореме D4

Следовательно, в случае 0<п<п уравнение (1,а) вьшолняется. 10.4. ЗНАКОВОЕ ДЕЛЕНИЕ НА даЛИТЕЛЬ, НЕ МЕНЬШИЙ 2