такого, что dx = g(mod 2*), где - наибольший обший делитель d и 2, т.е. наибольшей

степени 2, являюшсйся делителем d. Такая модифицированная программа, как и ранее, вычисляет для нечетного d мультипликативное обратное число, хотя и требует для этого на одну итерацию больше.

Что касается количества итераций, выполняемых данной программой, то для нечетного d, не превышающего 20, требуется максимум три итерации; среднее их число равно 1.7. Для d порядка 1000 требуется максимум 11, а в среднем - шесть итераций.

Вычисление мультипликативного обратного по методу Ньютона

Хорошо известно, что при работе с действительными числами значение Ifd , где diQ, может быть вычислено с возрастающей точностью с помощью итеративного вычисления

x„,, = x„i2-dx„) (32)

при начальном приближении хо, достаточно близком к Ifd . Количество точных цифр в результате при каждой итерации примерно удваивается.

Однако гораздо менее известно, что данная формула может применяться для поиска мультипликативного обратного числа при использовании модульной арифметики с целыми числами! Например, для поиска мультипликативного обратного к 3 по модулю 256 начнем с JC = 1 (можно использовать любое нечетное число). Тогда

,=1(2-3.1) = -1,

, = -1(2-3(-1)) = -5,

=-5(2-3(-5)) = -85,

X, = -85(2 - 3(-85)) = -21845 = -85(mod 256).

Итерации достигли неподвижной точки по модулю 256, так что -85, или 171, и есть мультипликативное обратное числа 3 по модулю 256. Все приведенные вычисления выполнялись по модулю 256.

Почему работает этот метод? Поскольку если х„ удовлетворяет условию

dx sl(modm)

и x„+i определяется формулой (32), то

Л„, sl(nrad m).

Чтобы увидеть это, положим Л„ = 1 + fan. Тогда

dx„,,=dx„i2-dx„) =

= (l + toi)(2-(l + fan)) = = (l+fcm)(l-toi) = = l-fcW- = = l(modm-).

В нашем приложении т является степенью 2, скажем, 2. В этом случае, если

dx„ £l(mod2), то dx„,=l{mod2).

В этом смысле, если х„ рассматривается как некоторое приближение d , то каждая итерация (32) удваивает количество битов "точности" приближения.

Так случилось, что по модулю 8 мультипликативньпй обратным любого нечетного числа d является само это число. Таким образом, в качестве начального приближения можно взять Xe=d. Тогда по формуле (32) получим значения JC, JC2,..., такие, что

dx,=l(mod2), dx,sl{mod2"), dx,=l{mod2), rfc4 sl(mod 2) и т.д.

Таким образом, четырех итераций достаточно, чтобы найти мультипликативное обратное по модулю 2 (если хsl(mod 2"), то xsl(mod 2") для я<48). Это приводит нас

к программе на языке С (листинг 10.5), где все вычисления выполняются по модулю 2.

Листинг 10.5. Вычисление мультипликативного обратного по модулю 2 методом Ньютона

unsigned mulinv(unsigned d) d должно быть нечетно {

unsigned xn, t; xn = d; loop:

t = d*xn;

if (t == 1) return xn; xn = xn*(2 - t); goto loop;

Примерно для половины значений d этой программе требуется 4.5 итерации, т.е. девять умножений. Для другой половины (у которой "верны четыре бита" начального значения хп, т.е. d- = l(mod 16)) требуется, как правило, семь (или меньшее количество) умножений.

Таким образом, можно считать, что этот метод требует в среднем восьми умножений.

Один из вариантов этой программы состоит в простбм выполнении цикла четыре раза, независимо от значения d, что позволяет обойтись восемью умножениями и без команд управления циклом. Другой вариант предусматривает выбор в качестве начального приближения мультипликативного обратного "с точностью 4 бита", т.е. перед началом вычислений нужно найти хо, которое удовлетворяет условию dxg = l(mod 16). Тогда для

вычислений потребуется выполнить только три итерации цикла. Найти подходяшее начальное приближение можно, например, следующими способами:

Хо <-rf + 2((rf+l)&4) илн Xod+d-l.

Здесь умножение на 2 выполняется при помощи сдвига влево, а все вычисления производятся по модулю 2 (игнорируя переполнения). Поскольку во второй формуле используется умножение, ее применение позволяет сэкономить только одну такую команду.

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

Некоторые мультипликативные обратные

в завершение перечислим в табл. 10.3 некоторые мультипликативные обратные числа.

Таблица 10.3. Некоторые мультипликативные обратные числа

Вы можете заметить, что в ряде случаев (rf=3,5,9. И) мультипликативное обратное к d совпадает с магическим числом для беззнакового деления на d (см. раздел 10.14). Это в большей или меньшей мере случайность. Подобное происходит для тех чисел, для которых магическое число М равно множителю т, и эти величины имеют вид {Т. + \yd при /7 > 32 . В этом случае

Md =

2" + !

£f = l(mod2").

так что M=d(mod 2").

10.16. Проверка нулевого остатка при делении на константу

Мультипликативное обратное делителя d может использоваться для проверки равенства О остатка после деления на rf [21].

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

Сначала рассмотрим беззнаковое деление на нечетный делитель rf. Обозначим через d мультипликативное обратное к rf число. Тогда, поскольку dd =l(mod2"), где W-

размер машинного слова в битах, d также нечетно. Следовательно, d является взаимно простым с 2* и, как показано в доказательстве теоремы Ml в предыдущем разделе, если п представляет собой множество всех 2" различных чисел по модулю 2*, то rid также представляет собой множество всех 2 различных чисел по модулю 2*.

10.16. ПРОВЕРКА НУЛЕВОГО ОСТАТК\ ПРИ ДЕЛЕНИИ НА КОНСТАНТУ