Главная Промышленная автоматика.

8.6. ПРИМЕНЕНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ

8.6. ПРИМЕНЕНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ

Изучим задачу преобразования модульного представления целого числа в его позиционное представление Пусть даны попарно взаимно простые модули ро, Ри . . ., p*-i и вычеты «о, Ui, . . ., Uk-u где /г=2*; надо найти такое целое число и, что «<-»(ио, «i, . . ., Это можно сделать с помощью целочисленного аналога интерполяционной формулы Лагранжа для полиномов.

Лемма 8.2. Пусть Ci- произведение всех pj, кроме pt (т. е. Ci= ft-1

=p/Pi, где P=IIpj)- Положим di=cj mod p( (m. e. diCil (mod рЛ и 0dt<Pi). Тогда

<г-1

«= (modp). (8.20)

Доказательство. Поскольку числа ру попарно взаимно просты, то, как известно (упр. 7.9), числа di существуют и единственны. Кроме того, Ci делится на р, при /#t, так что CidiUi =0 (modp;) при Поэтому

CjdiUiCjdjU/ (modpy).

Гак как Cfdj\ (mod p), то

2 CidfUf = Uf (mod Pj).

Так как pi делит p, то эти соотношения выполняются даже тогда, когда все арифметические операции производятся по модулю р. Таким образом, (8.20) верно. □

Наша задача состоит в эффективном вычислении (8.20). Сразу трудно увидеть, как можно вычислять по Pi, не прибегая к методу проб и ошибок. Позже мы увидим, что эта задача не так уж трудна, если использовать алгоритм Евклида из разд. 8.8 и его быструю реализацию из разд 8.10. В данном разделе мы изучим только ту форму китайской задачи об остатках, которая основана на "предварительной обработке". Если часть входных данных фиксирована для ряда задач, то все величины, зависящие только от этой фиксированной части, можно вычислить заранее и считать частью входа. Алгоритм, в котором сделаны такие предварительные вычисления, называют алгоритмом с предварительной (работкой данных

) Процесс восстановления числа по его остаткам был известен китайцам более 2000 лет назад, и потому соответсгвующую теорему называют китайской теоремой об остатках.



Для китайского алгоритма с предварительной обработкой данных входом будут служить не только вычеты и модули pi, но и обратные к ним (числа di). Эта ситуация не является нереальной. Если часто применять китайский алгоритм для перевода чисел, представленных вычетами по фиксированному множеству модулей, то разумно заранее вычислить те функции от этих модулей, значения которых используются в алгоритме. В следствии теоремы 8.21 мы увидим, что на оценку сложности наличие предварительной обработки (или ее отсутствие) влияет весьма скромно.

Анализируя (8.20), замечаем, что слагаемые CidiUi при разных i имеют много общих сомножителей. Например, CidiUt имеет сомножителем число ро pi . . . Pk/2-i если и число pk/2 Pfc/2+1 . . • ...Pft i, если i<k/2. Поэтому можно записать (8.20) в виде

Гк/г-х \ fc-i / к-х \ к/з-х

«=( 2с;й,-ы, X II pi+[ П c:diUi)x и. Pi.

где ci - это произведение ро рх • • Рк/2-\ без Pi, ас] - произведение pfc/2 Pft/2+i • . -Pk-i без Pi. Это наблюдение должно подсказать прием "разделяй и властвуй", аналогичный тому, что применялся при вычислении вычетов. Находим произведения

Яц = II Рт

(как в алгоритме 8.4), а затем - целые числа Sij= П QijdmUjPm-

т - i

Если /=0, то Sio=diUi. Если />0, то вычисляем Sij по формуле i/ = i,/-xQi+2l-,/-x + i+i-./-x Qi,J-l-Наконец, получаем s„t=u, что и нужно для (8.20).

Алгоритм 8.5. Быстрый китайский алгоритм с предварительной обработкой данных

Вход.

1. Попарно взаимно простые целочисленные модули ро, pi, . . . . • •. Рк-х, где k=2* для некоторого t.

2. Множество "обратных" к ним чисел do, di, . . ., dk-x, т. е.

таких, что di={p/pt)-= mod Pi, где p=Ylpi.

3. Последовательность вычетов («о, «i, . • ., «t-i).

Выход. Единственное целое число и, 0u<ip, для которого

Ы«->(«о, Ui, . . ., Uk-x). 330



8.6. ПРИМЕНЕНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ

begin

1. for t-<-О until k-l do s,„-<-

2. for yl until t do

3. for i*-0 step 2 until k-l do

4. s,y <- Sij .*qi+2J-. I- 1+SC+2J-K I-\*qi,/-i\

5. write modot end

Рис. 8.4. Программа вычисления целого числа по его модульному представлению.

1+2-\

Метод. Сначала вычисляем qij=Ji p„, как в алгоритме 8.4

Затем запускаем программу на рис. 8.4 в предположении, что в ней

1 + 2-1

Пример 8.6. Пустьро, Рь Рг. Рз равны соответственно 2, 3, 5, 7 и («о, «ь иг, из)={1, 2, 4 ,3). Тогда 9,o=Pi Для 0<i<4, oi=6, 21=35 и 02=P=210. Далее,

do = (3*5*7)-1 mod2= 1, поскольку 1*105=1 (mod 2),

di = (2*5*7)-i mod3=l, поскольку 1*70 =1 (mod3),

Й2 = (2*3*7)-1 mod 5 = 3, поскольку 3*42 =1 (mod 5),

йз = (2*3*5)~* mod7 = 4, поскольку 4*30 =1 (mod 7).

Таким образом, в строке 1 вычисляются

Soo=l*l= 1, Sio=l*2= 2, s„j = 3*4 = 12, 5зо = 4*3 = 12,

Затем выполняется цикл в строках 3, 4 с /=1. Здесь / принимает значения О и 2; следовательно,

«01 = Soo*9io + Sio*/oo = 1*3 + 2*2 = 7, «21 = S2o*?3o + 5зо*/2о = 12*7 + 12*5 = 144.

Далее выполняется цикл в строках 3, 4 с /=2, а i принимает только значение 0. Получаем

«02 = «01*21 + S2i*9oi = 7*35 + 144*6 = 1109.

Заметим, что числа qij зависят только от чисел р;. Можно включить их во входные данные, а не вычислять, ибо разрешается предварительная обработка. Но легко показать, что на порядок времени работы не влияет, вычислены заранее эти qij или нет.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 [106] 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0037