AOP_Tom2 (1021737), страница 89
Текст из файла (страница 89)
э. Дальнейшее развитие эта задача получила в работах математиков средневековой Индии, предложивших методы куттака (Ьи(1айа) (см. раздел 4.5.2). Однако в общем виде теорема С впервые была сформулирована и доказана Чин Чжу-Шао в работе Яш ЯЬп СЬш СЬапб (1247), в которой рассмотрен также случай, когда модули могут иметь общие множители (как в упр. 3). [См. 3. ХеебЬаш, Яс)енсе апд Сйгш)хайоп ш СЬ1па 3 (СашЬг168е Еп1чегз11у Ргезз, 1959), 33-34, 119-120; У. Ь1 апй 8. Пи, С)плеве МасЬеша11ск (Ох(огб: С1агепс1оп, 1987), 92-94, 105, 161-166; К.
ЯЬеп, АгсЬте Гог НЫогу ог" Ехасс Яс1епсез 38 (1988), 285-305.] Многочисленные исследования, посвященные этой теории, обобщены Л. Ю. Диксоном (Ь. Е. Ейс1сзоп) в книге Н!нсогу ог" ФЬе ТЬеогу ог 7чшпЬегк 2 (Сагпе81е 1пзс. оГ ЪЧазЬ1пйсоп, 1920), 57-64, Как следует из теоремы С, модулярное представление можно использовать для чисел в любом соответствующем интервале гп = т1тз...гп, целых чисел. Например, можно в (6) взять а = 0 и работать только с неотрицательными целыми числами и, меньшими т.
С другой стороны, при выполнении операций сложения и вычитания, так же„как н умножения, обычно удобнее всего предположить, что все модули ты тю ..., т„являются нечетными числами, так что и т = т1тз... т„ тоже нечетное, и работать с целыми числами из интервала т т — — <и< —, (10) 2 2' симметричного относительно нуля. Для выполнения основных операций, перечисленных в (2)-(4), необходимо вычислить (и, +из) шойт, (и — е ) той т и и е пюйт при 0 < име; < т .
Если т — число однократной точности, то лучше всего формировать и,е, пюй т путем умножения н последующего деления. Что касается операций сложения и вычитания, то здесь ситуация проще, так как не требуется деление; удобно рассматривать следующие формулы: (и +е.)гпойт =и +е.— т (иу+е,)т ). (и; — ез)гпойт =и — е +т(и,<е). (См. раздел 3.2.1.1.) Поскольку желательно„чтобы ш было как можно большим, проще всего принять т1 наибольшим нечетным числом, соответствующим машинному слову, в качестве т2 принять наибольшее нечетное число < тм взаимно простое с тм а в качестве тз — наибольшее нечетное числа < тз, взаимно простое как с тм так и с тю и т. д., пока не наберется столько т,, сколько будет достаточно для образования нужного т. Способы эффективного определения, являются ли два числа взаимно простыми, рассматриваются в разделе 4.5.2.
В качестве простого примера предположим, чтб имеется десятичный компьютер со словом, содержащим две цифры, так что размер слова равен 100. Тогда в результате только что описанной процедуры получаем тг = 99, тг = 97, тз = 95, т4 — — 91, тл = 89, тл — — 83 (13) и т. д. При работе на двоичных компьютерах иногда желательно выбирать модули т иным образом: 2е, (14) Другими словами, значение каждого модуля на единицу меныпе очередной степени 2. Такой выбор значения модуля т; зачастую упрощает выполнение основных арифметических операций, нбо выполнять вычисления с числами, представленными по модулю 2'~ — 1, несколько проще, чем с числами, представленными в обратном коде. После того как значении модулей выбраны таким образом, полезно несколько ослабить условие 0 < и < т, и потребовать только, чтобы (15) и ш и (по модулю 2'~ — 1).
0<и~ <2", Таким образом, значение и = т. = 2' — 1 принимается в качестве оптимального вместо иу = О, поскольку это, с одной стороны, не влияет на справедливость теоремы С, а с другой — означает, что и; может быть любым е -битовым двоичным числом. При таком допущении операции сложения н вычитания по модулю т, выполняются следующим образом: и. 9 с.
= ((и + о ) той 2" ) + (и + ву > 2' ']. (16) и, З су = (иову шо42") Ю (изо~/2"!. (17) (Здесь Оз и З указывают на действия, которые с учетом условия (15) должны быть выполнены с отдельными компонентами (и,,..., и,) н (иы., ., о„) при сложении или умножении соответственно.) При вычитании можно пользоваться и соотношением (12). Можно также использовать условие и Ю и = ((и~ — о ) шос$2") — (из <су). (18) Эти операции могут быть эффективно выполнены, даже если 2'~ больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 нли разделить число на степень 2. В (17) имеем сумму "верхней половины" и "нижней половины" произведения, как в разделе 3.2.1.1 — 8. Для работы с модулями вида 2' — 1 необходимо знать„прн каких условиях число 2' — 1 является взаимно простым с числом 2У вЂ” 1.
К счастью, для этого существует очень простое правило: йсй(2' — 1, 2г — 1) = 2з' 1'П вЂ” 1. (19) Данная формула утверждает, в частности, что о! 2' — 1 и 2г — 1 взаимно просты тогда и только тогда, когда взаимно просты е и /. Уравнение (19) следует из алгоритма Евклида и тождества (2' — 1) тос1(2à — 1) = 2' '~ — 1. (20) (... (и„,Ь+ о 1)Ь+ .) Ь+ оо. Если Ь = 2 и модули ту имеют специальный вид 2' — 1, оба подхода сводятся к совсем простому способу.
Рассмотрим двоичное представление числа и с блоками е, бит: и = азА' + аз — зАз + . + а1А+ ао, (21) где А = 2" и 0 < аь С 2ю при 0 ( /с ( а Тогда и = аз +а, з + . + аз +аз (по модулю 2" — 1), (22) поскольку А = 1. Поэтому и, вычисляются, как и в (16), путем сложения е -битовых чисел аз Ю . Ю а1 б ао. Этот процесс аналогичен уже знакомому процессу (См. упр. 6.) Поэтому на компьютере с длиной слова 2з' можно выбрать т1 —— 2зз — 1 тз = 2зч — 1, тз = 2зо — 1 тз — — 2з' — 1 т = 2зз — 1, что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до т|тзтзтзтз > 2'~з.
Как мы уже заметили, операции преобразования в молулярное представление и обратно очень важны. Молулярное представление (иы..., и„) для заданного числа и может быть получено посредством деления и на ты ..., гп, с запоминанием остатков. В случае, когда и = (и в з...оо)ы возможно применение более подходящего способа, который состоит в том, чтобы, используя модулярную арифметику, вычислить полинам "выбрасывания девяток", который использовался для определения и шог1 9 в случае, когДа и выражалось в десятичной системе. Обратный переход от модулярного представления к позиционной системе счисления выполняется немного сложнее. В связи с этим интересно отметить, как изучение способов вычисления приводит к пересмотру критериев оценок математических доказательств.
В теореме С утверждается, что возможен переход от (иг,...,иг) к иг и приводятся два доказательства. Первое из рассмотренных доказательств считается классическим; оно основывается лишь на самых простых понятиях, а именно: г) любое число„кратное тг, пгэ, ... и т„, должно быть кратным пггтз...гп,, если числа пг попарно взаимно просты; й) если т предметов поместить в т ящиков так, чтобы ни в каком ящике не было двух предметов одновременно, то в каждом ящике должно быть по одному предмету. Согласно традиционным понятиям математической эстетики это, несомненно, наилучший способ доказательства теоремы С. Но с точки зрения вычислительной он никуда не годится! Это все равно что сказать: "Попробуйте перебирать и = а, а+1,..., пока не найдете значение, для которого и = иг (по модулю тг ),..., и = иг 1по модУлю пгг)".
Второй способ доказательства теоремы С более конкретен. Он показывает., как вычислить г новых констант Мг,..., М„и получить решение, выражаемое через данные константы, с помощью формулы (9). В этом доказательстве используются более сложные понятия (например, теорема Эйлера), но с вычислительной точки зрения оно гораздо более удовлетворительно, поскольку константы Мг,..., ЛХ, определяются только один раз. С другой стороны, определение констант ЛХХ при помощи уравнения (8) является нетривиальной задачей, так как вычисление Эйлеровой ггг-функции в общем случае требует факторизации, т. е, разложения чисел т, на простые сомножители.
Сугцествует много способов вычисления М, лучших, чем использование (8). В связи со сказанным можно снова подчеркнуть разницу между математической элегантностью и вычислительной эффективностью. Но даже после нахождения М при помощи лучшего из возможных способов можно столкнуться с фактом, что ЛХ, слишком велико. Таким образом, использование (9) приводит к большому числу вычислительных операций с высокой точностью, а именно этого нам хотелось бы избежать 'прежде всего. Поэтому, чтобы найти действительно пригодный для практического применения метод перехода от (и„..., и„) к гг, необходимо иметь лучшее доказательство теоремы С. Такое доказательство предложено в 1958 году Х.
Л, Гарнером (Н. 1.. Оагпег). Оно основано на использовании (тг) констант с, для 1 < г < Х < г, где (23) со тг = 1 (гго модулю тп ). Константы с; легко вычисляются при помощи алгоритма Евклида, так как алгоритм 4.5.2Х для заданных г и Х позволяет определить а и 5, такие, что апг, + бтг —— йсг1(гп„го,) = 1, и можно положить с; = а. Простой метод определения сгу для модулей специального вида 2" — 1 приведен в упр. 6. Так как сО удовлетворяет условию (23), можно выполнить присвоения ег +- иг шоб»пм ег +- (иг — ег) сш шад тг, ез +- ((из — ег) сгг — ег) сгг шоб тз, (24) е»»- ( - ((и» вЂ” е~) с㻠— ег) с㻠— — е, г) с1„О, шабт„.
Тогда число и = е»т, г тгтг + ' '+ гитгтг + ег»пг + ег (25) будет удовлетворять условиям 0<и<т, и:— и. (по модулю ту) для 1 < у < г. (26) (См. упр. 8; другой способ записи формул (24), не требующий такого большого количества констант, приведен в упр. 7.) Формула (25) — это предсгпаеление но смешанному основанию числа и, которое можно перевести в двоичный либо десятичный формат, используя методы, описанные в разделе 4.4. Если интервал 0 < и < т не является необходимым, то после завершения процесса перевода к нему можно добавить (или вычесть из него) соответствуюшее число, кратное т.
Преимущество метода, представленного в (24), состоит в том, что для вычисления е используется только арифметика по модулю т з которая уже встроена в алгоритмы этого класса. Более того, соотношения (24) позволяют выполнять вычисления параллельно. Можно начать с присвоения (ем..., е„) < — (иг шоб ты ..., и„шод т,), затем в момент у при 1 < г < г сразу же получить еь < — (еь — еу)с,ь шад та для г < й < г. Другой способ вычисления представления числа по смешанному основанию. обеспечивающий возможность достижения параллелизма, рассматривается в интересной статье А. С. Френкеля (А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
