AOP_Tom2 (1021737), страница 90
Текст из файла (страница 90)
8. атаев)се!), опубликованной в журнале Ргас. АСМ №6 СопГ. 19 (РЬ1!ас1е!р1г!а, 1964), Е1.4. Важно отметить, что представление (25) па смешанному основанию пригодно для сравнения величин двух чисел, заданных в модулярном представлении. Так, если известно, что 0 < и с т и 0 < и' < т, можно сказать, будет ли и с и', если сначала выполнить переход к (е„..., е,) и к (е',,..., е„'), а затем в соответствии с лексикографическим правилом проверить выполнение неравенств е, < е,' или е„= е', и е„< е'„и т, д, Нет необходимости переходить к двоичной или десятичной системе счислении, если нужно всего лишь выяснить, будет ли (и„..., и,) меньше, чем (и,',....
и„'). Операции сравнения двух чисел или определения знака числа при модулярнам представлении интуитивно понятны и очень просты, поэтому можно было бы ожидать, что удастся найти значительно более легкий способ выполнения такого сравнения, чем переход к представлению со смешанным основанием. Но из приводимой ниже теоремы следует, что шансов на поиск существенно более легкого метода мало, поскольку величина числа в модулярном представлении существенным образом зависит от всех битов всех остатков (им..., и„). Теорема Я (Николаш Сабо (%сЬо1аэ БгаЬо), 1961). Используя введенные выше обозначения, предположим, что тг < ~/т, н пусть Т,— пронзвальное значение, удовлетворяющее неравенству (27) тг <Е<т — ты Пусть д — произвольная фу'нкцня, такая, что ряд (д(0), д(1),..., д(тг — 1)) содержит меньше значений, чем ты Тогда существуют такие числа и и е, что д(и тос1 тг) = д(е шос1 тг), и тос1 т = е тос1 тз при 2 < у < г; (28) (29) 0 < и < Е < е < т.
Докаэагнельсгава. Так как согласно предположению должны существовать числа и Ф е, удовлетворяющие (28), д должно принимать одинаковые значения для двух различных остатков. Пусть (и, е) — пара таких значений, удовлетворяющая равенству (28) при 0 < и < е < т, для которых и минимально. Поскольку и' = и — тг и е' = е — гпг также удовлетворяют равенству (28), в силу минимальности и мы должны получить и' < О. Отсюда следует, что и < тг < Е, и, если неравенство (29) не выполняется, получаем е < Е.
Но е > и, а е — и кратно тт... гп, = т/гпг, так что е > е — и > т/тг > тг. Поэтому, если неравенство (29) для (и, е) не выполняется, оно будет удовлетворяться для пары (и",ен) = (е — тг, и+ гп — тг). 1 Разумеется, подобный результат может быть доказан для любого тг вместо тг ,' можно было бы также заменить неравенство (29) условием а < и < а+ Е < е < а+ т, внеся при этом незначительные изменения в доказательство.
Таким образом, теорема Б показывает, что многие простые функции не могут использоваться для определения области, которой принадлежит число в модулярном представлении. Напомним теперь главные моменты, которые рассматривались в этом разделе. Применение модулярной арифметики может дать значительное преимущество в приложениях, в которых основная доля вычислений приходится на точное умножение (или возведение в степень) больших чисел в сочетании со сложением и вычитанием, но в которых очень редко появляется необходимость в делении либо сравнении чисел илн не нужно проверять, не "выходят" ли промежуточные результаты за предсгчы области.
(Важно не забывать последней оговорки; существуют методы проверки принадлежности числа данной области (один из них рассмотрен в упр. 12), но они настолько сложны, что сводят на нет все преимущества модулярной арифметики.) Некоторые приложения вычислений с применением модулярной арифметики рассмотрены Х. Такахаси (Н. ТайаЬаэ1) и Й. Ишибаши (гг. 1эЬ1ЬаэЬ1) в работе, опубликованной в 1пгогтасюп Ргос.!и Ларап 1 (1961), 28 — 42. Примером такого приложения является точное решение линейных уравнений с рациональными коэффициентами.
По различным причинам в этом случае удобно предположить, что модули тг, тт,..., т„являются простыми числами; линейные уравнения могут решаться независимо по каждому модулю т . Эта процедура была подробно исследована И. Борошем (1. ВогоэЬ) и А. С, Френкелем (А.
Б. Ргаеп1се1) (МасЬ. Сошр. 20 (1966), 107 — 112) и в дальнейшем усовершенствована А. С. Френкелем и Д. Левенталем (1у. 1 оегчепсЬа1) [Х Неэ. №с!опл1 Вигеаи оЕ Всапс(агс(э 76В (1971), 67 — 75), При помощи этого метода на компьютере С)УС 1604 меньше чем за 20 мин было получегэ 9 независимых решений системы из 111 линейных уравнений со 120-ю неизвестными. Та же процедура полезна и для решения систем линейных уравнений, когда коэффициенты представлены в формате с плавающей точкой, а матрица коэффициентов плохо обусловлена. В таком виде коэффициенты трактуются как точные рациональные числа. Модульный способ дает более быстрый метод вычисления истинных результатов быстрее, чем традиционные методы могут дать лриближенный ответ! Последующие достижения в этой области опубликованы в работе М.
Т. МсС!е!1ап, 1АСМ 20 (1973), 563-588. Исследования, посвященные ограничениям в применении этого метода, опубликованы в работе Е. Н. Ваге)ва, 1. 1пзГ. Ма1Ь. апс! Арр!. 10 (1972)„68-104. Опубликованная литература по модулярной арифметике ориентирована, главным образом, на разработку компьютеров, так как свойства свободного переноса модулярной арифметики делают ее привлекательной с точки зрения быстродействующих операций. Эта идея впервые была опубликована А. Свободой (А.
8чоЬоба) и М. Валахом (М. Ча1асЬ) в чехословацком журнале Нгго!е па сргасотап! 1пуоппаср' (1п1огтагюп Ргосезейпб Маей!пеа) 3 (1955), 247 295, а затем независимо — Х. Л. Гарнером (Н. Е. Сагпег) [1НЕ Тгапв. ЕС-8 (1959), 140 — 147]. Использование модулей 2" — 1 было предложено А. С.
Френкелем в работе 1АСМ8 (1961), 87-96, а некоторые преимущества модулей такого нида продемонстрированы А. Шенхаге (А. 8сЬбпЬайе) [Согпрпбщ 1 (1966), 182 — 196]. Дополнительную информацию и исчерпывающую библиографию по этому вопросу можно найти в книге Н. 8. 8хаЬо, Н. 1. Тапа)га Неа!г(не АПбйгпеск апр! !гз Арр!!габона го Сотрнгег?есбпо!ойу (Нек Ъог)с МсОгаюН111, 1967). В 1968 году опубликована книга И. Я. Акинского и Д. И. Юдицкого, в которую включена глава, посвященная комплексным модулям [см.
Нею Нонтагпе р)е Ма!И. Рнгев ег Арр!. 15 (1970), 159 — 160]*. Обсуждение модулярной арифметики будет продолжено в разделе 4.З.ЗВ. Сообщение нэ доске объявлений гласило, что он находится в комнате 423, но при взгляде нэ план системы нумерапии, с виду логичной, складывалось впечатление, будто ее разрабатывал либо лунатик, либо математик. — РОБеРт БЗРнАРд (РОВепт ВАггнАггО), тпе сазе ог гпе ынгйпд Вгопгй (19вз) УПРАЖНЕНИЯ 1. [20[ Найдите все целые числа и, удовлетворяющие всем следующим условиям: и шор! 7 = 1, и тор) 11 = б, и ирой 13 = 5, 0 ( и С 1000. 2.
[Мйб] Будет ли теорема С па-прежнему справедливой, если допустить, что а, ир, ит,... ..., и, и и — произвольные вещественные числа (а не только целые)7 ° 3. [Мйб] (Обобщенная китайская тпеарема об астарпкаю) Пусть тр, тр,,, т, — положительные целые числа, т — наимеиыяее общее кратное чисел тр,тю..., т, и пусть а,ир,ир,...,и„- -произвольные целые числа. Докажите, чта имеется точно одно целое число и, удовлетворяющее соотношениям а(иса+т, и = ир (па модулю т, ), 1(У(т, при условии, чта и, = ир (по модУлю йсР)(т„тр)), 1 (1 (! ( т, и чта если посрреднее условие не выполняется, то такого целого числа и не существует.
ч Слр. Акинсккй И. Я. и рСляцкнй Д. И. Машинная арифметика в остаточных «лассах. — Едз Саа. радин, 1909.— 440 с. (1970). — Прим. нерея. 4. [20[ Продолжите процесс, представленный в (13). Чему будут равны тп гпв, тэ, . ? 5. [Мдд[ Предположим, что метод, определенный в (13), продолжен до того момента, когда уже нельзя выбрать ни одного нового числа т . Получим ли мы этим "вульгарным" методом наибольшее возможное значение произведения т1тз... т„такое, что все т; будут положительными целыми числами, меньшими 100, и попарно взаимно простымиу О.
[Мдд[ Пусть е, / и д — неотрицательные целые числа. а) Покажите> что 2' ш 2г (по модулю 2з — 1) в там и только в том случае, когда е вз / (по модулю д). Ь) Для заданных е шой / = й и се пзой / = 1 докажите тождество ((1+ 2 + - + 20 0 ) (2' — 1)) тай(2~ — 1) = 1. (Таким образом, получена сравнителыю простая формула длв величины, обратной 2' — 1, па модулю 2г — 1, как это н требуется в (23).) 7. [М21[ Покажите, что (24) можно переписать следующим образом: е, +- и1 пюйты ез +- (из — е1 ) си пзой гпз, ез +- (из — (е1 + т1ез)) с~зсгз гаой тз, ńŠ— (и, — (Е1 + т~(ЕЗ+ тэ(ЕЗ+ +те-ЗЕ, 1)...))) СЫ, ..См п„нэайт„. Если это сделать, то вместо г(г — 1)/2 констант с,, как в (24), потребуется только г — 1 констант С~ = сп ... сп О, гной тз.
Оцените с точки зрения вычислений на компьютере достоинства и недостатки настоящего варианта формулы (24) по сравнению с ее исходным вариантам. 8. [Мд
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
