Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 89
Текст из файла (страница 89)
При таком допущении операции сложения и вычитания по модулю т выполняются следующим образом: и. Е с = ((и, + с ) шоб 2и) + (иу + оу > 2" ). (16) извоз — — (и оэ пкк12") В (изс~/2"'). (17) (Здесь ~Э я оэ указывают на действия, которые с учетом условия (16) должны быть выполнены с отдельными компонентами (им..., и„) к (сы..., о,) при сложении яли умножении соответственно.) При вычитании можно пользоваться и соотношеннем (12). Можно также использовать условие ио В оз = ((из — о ) пкк(2и) — (из < оу).
(18) Эти операции могут быть эффективно вь|полнены, даже если 2ю больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 или разделить число на степень 2. В (17) имеем сумму "верхней половины" и "нижней половины" произведения, как в разделе 3,2.1.1-8. Для работы с модулями вида 2'~ -1 необходимо знать, при каких условиях число 2' — 1 является взаимно простым с числом 21 — 1. Е счастью, для этого существует очень простое правило: Всб(2' — 1, 27 — ц = г""1"~ — 1.
(19) Данная формула утверждает, в частности, что э! 2' — 1 и 2У вЂ” 1 взаимно просты тогда и только тогда, когда взаимно просты с н (. Уравнение (19) следует из алгоритма Евклида и тождества (2' — 1) пюб (2г — 1) = 2' ~" 7 — 1. (20) (См. упр. 6.) Поэтому на компьютере с длиной слова 2зэ можно выбрать т1 = 2зэ -1, тэ = 2э' — 1, тэ = 2эо — 1, т4 = 2~~ — 1, тэ = 2ээ — 1, что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до т1тэтэт4то > 2'4э Как мы уже заметили, операции преобразования в модулярное представление и обратно очень важны.
Модулярное представление (иы..., и,) для заданного числа и может быть получено посредством деления и на ты ..., т; с запоминанием остатков. В случае, когда и = (о о 1... оо)м возможно применение более подходящего способа, который состоит в том, чтобы, используя модулярную арифметику, вычислить полинам (... (о Ь+ о,)Ь+ ..) Ь+со.
Если Ь = 2 и модули т имеют специальный вид 2и — 1, оба подхода сводятся к совсем простому способу. Рассмотрим двоичное представление числа и с блоками е. бит: и = а1А'+ас 1А' '+ ° +а1А+ао (21) гдеА=2и иО<аь <2' приО<Ь<а Тогда и гн ос + а~ э+ "+ а1+ ао (по модулю 2'~ — 1), поскольку А гя 1. Поэтому и вычисляются, как и в (16), путем сложения е -битовых чисел а, Ю ° ° ° Ю а1 6~ ао.
Этот процесс аналогичен уже знакомому процессу "выбрасывания девяток", который использовался для определения и шоб 9 в случае, когда и выражалось в десятичной системе. Обратный переход от модулярного представления к позиционной системе счисления выполняется немного сложнее. В связи с этим интересно отметить, как изучение способов вычисления приводит к пересмотру критериев оценок математических доказательств. В теореме С утверждается, что возможен переход от (иы..., и„) к н, и приводятся два доказательства.
Первое из рассмотренных доказательств считается классическим; оно основывается лишь на самых простых понятиях, а именно: !) любое число, кратное тм тю ... и ш„, должно быть кратным гл1гпз... т„, если числа тт попарно взаимно просты; И) если т предметов поместить в т ящиков так, чтобы ни в каком ящике не было двух предметов одновременно, то в каждом ящике должно быть по одному предмету. Согласно традиционным понятиям математической эстетикк зто, несомненно, наилучший способ доказательства теоремы С. Но с точки зрения вычислительной он никуда не годится! Это все равно что сказать: "Попробуйте перебирать и = а, а+ 1,..., пока не найдете значение, для которого и гя и1 (по модулю тг),...., в = н, (по модулю т„)".
Второй способ доказательства теоремы С более конкретен. Он показывает, как вычислить г новых констант Мы..., М„и получить решение, выражаемое через данные константы, с помощью формулы (9). В этом доказательстве используются более сложные понятия (например, теорема Эйлера), но с вычислительной точки зрения оно гораздо более удовлетворительно, поскольку константы Мы..., М„определвются только один раз.
С другой стороны, определение констант М при помощи уравнения (8) является нетривиальной задачей, так как вычисление Эйлеровой д-функции а общем случае т!нюует факторизации, т. е. разложения чисел т на простые сомножители. Существует много способов вычисления Му, лучших, чем использование (8). В связи со сказанным можно снова подчеркнуть разницу между математической элегантностью и вычислительной эффективностью. Но даже после нахождения М» при помощи лучшего из возможных способов можно столкнуться с фактом, что М слишком велико. Таким образом, использование (9) приводит к большому числу вычислительных операций с высокой точностью, а именно этого нам хотелось бы избежать 'прежде всего. Поэтому, чтобы найти действительно пригодный для практического применения метод перехода от (пы..., и„) к и„необходимо иметь лучшее доказательство теоремы С.
Такое доказательство предложено в 1958 году Х. Л. Гарнером (Н. 1. Оагпег). Оно основано на использовании (';) констант с; для 1 < ! < ! < г, где (23) с; т; гя 1 (по модулю т ). Константы сО легко вычисляются при помощи алгоритма Евклида, так как алгоритм 4.5.2Х для заданных ! и ! позволяет определить а и 6, такие, что ат; + Ьту = 8сб(тот ) = 1, и можно положить с;, = а. ПРостой метод опРеделениЯ с; длЯ модулей специального вида 2" — 1 приведен в упр. б.
Так как с, удовлетворяет ушювию (23), можно выполнить присвоения и~ ь- и| шоп гпм из ь — (из — щ) сш шоп гпз, сз ч- ((из — н~) с~з — нз) сзз птоп гпз, (24) и, +- (... ((и, — и~)см — из)сз, — . — н, ~) с1, О, пкк1гп,. Тогда число ~ъгпг-1 ° глзнт1 + ' ' ' + сагпзгп1 + изш! + и1 (25) будет удовлетворять условиям 0<и<та, иази (помодулюту) для1<з<г.
(26) (См. упр. 8; другой способ записи формул (24), не требующий такого большого количества констант, приведен в упр. 7.) Формула (25) — это представление ио смешанномр основанию числа и, которое можно перевести в двоичный либо десятичный формат„используя методы, описанные в разделе 4.4. Если интервал 0 < и < тп не является пеобхолимым, то после завершения процесса перевода к нему можно добавить (или вычесть из него) соответствующее число„кратное т. Преимущество метода, представленного в (24), состоит в том, что для вычисления и используется только арифметика по модулю гп, которая уже встроена в алгоритмы этого класса.
Более того, соотношения (24) позволяют выполнять вычисления параллельно. Ыожно начать с присвоения (щ,..., н„) ~ — (и~ шоб шм ..., и, щи т„), затем в момент 1' при 1 < у < г сразу же получить нь <- (иь — из) сьь шод гпь для з < й < г. Другой способ вычисления представления числа по смешанному основанию., обеспечивающий возможность достижения параллелизма, рассматривается в интересной статье А, С. Френкеля (А. 5. Ггаепйе1), опубликованной в журнале Ргос. АСАХ%за СопЕ 19 (РЬ11абе1рЬ)а, 1964), Е1.4.
Важно отметить, что представление (25) по смешанному основанию пригодно для сравнения величин двух чисел, заданных в модулярном представлении. Так, если известно, что 0 < и < тп и 0 < и' < гл, можно сказать, будет ли и < и', если сначала выполнить переход к (и„..., и,) и к (о',,..., т„'), а затем в соответствии с лексикографическим правилом проверить выполнение неравенств и„< н'„или и„= и,'.
и е„, < и„' ~ и т. д. Нет необходимости переходить к двоичной или десятичной системе счисления, если нужно всего лишь выяснить, будет ли (и„...,и„) меньше, чем (и'„...,и',). Операции сравнения двух чисел или определения знака числа при модулярном представлении интуитивно понятны и очень просты, поэтому можно было бы ожидать, что удастся найти значительно бвпе легкий способ выполнения такого сравнения, чем переход к представлению со смешанным основанием. Но из приводимой ниже теоремы следует, что шансов на поиск существенно более легкого метода мало, поскольку величина числа в молулярном представлении существенным образом зависит от всех битов всех остатков (им..., и„).
Теорема Я (Николаш Сабо (%сЬо1вв ЗхаЬА), 1961). Иглользуя введенные выше обозначения, предположим, что гл~ < ~/т, н пусть ь — произвольное значение, удовлетворяющее неравенству (27) пт1 < Е < гп — 1пм Пусть д — произвольная функция, такая, что ряд (д(0), д(1),..., д(т1 - 1) 1 содержит меньше значений, чем тв~. Тогда существуют такие числа и н с, что д(ишос(пт~) = д(пшодпт1), ишобгпу = ешобгпт при 2 <1 < 1.; (28) (29) 0 < и < В < с < га. Доказательство.
Так как согласно предположению должны существовать числа и ~ п, удовлетворяющие (28), д должно принимать одинаковые значения для двух различных остатков. Пусть (и, с) — пара таких значений, удовлетворяющая равенству (28) при 0 < и < с < т, для которых и минимально. Поскольку и' = и — гп1 и с' = с — пт1 также удовлетворяют равенству (28), в силу минимальности и мы должны получить и' < О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
