Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 90
Текст из файла (страница 90)
Отсюда следует, что и < ти~ < 1,, и, если неравенство (29) не выполняется, получаем и < Е. Но е > и, а с — и кратно твт... т„= тв/гпы так что и > и — и > ш/ш1 > 1пы Поэтому, если неравенство (29) для (и, е) не выполняется, оно будет удовлетворяться для пары (и", вл) = (е — там и+ пт — ти1). $ Разумеется, подобный результат может быть доказан для любого га вместо гп1, можно было бы также заменить неравенство (29) условием а < и < а + Е < с < а+ гп, внеся при этом незначительные изменения в доказательство.
Таким образом, теорема Б показывает, что многие простые функции не могут использоваться для определения области, которой принадлежит число в молуляриом представлении. Напомним теперь главные моменты, которые рассматривались в этом разделе. Применение модулярной арифметики может дать значительное преимущество в приложениях, в которых основная доля вычислений приходится на точное умножение (нли возведение в степень) больших чисел в сочетании со сложением и вычитанием, но в которых очень редко появляется необходимость в делении либо сравнении чисел нлн не нужно проверять, не "выходят" ля промежуточные результаты за пределы областл.
(Важно не забывать последней оговорки; существуют методы проверки принадлежности числа данной области (один из них рассмотрен в упр. 12), но онн настолько сложны, что сводят на нет все преимущества модулярной арифметики.) Некоторые приложения вычислений с применением модулярной арифметики рассмотрены Х. Такахаси (Н. ТайаЬал1) и Й. Ишибаши (У. 1эЬ|ЬаэЬ1) в рабзте, опубликованной в 1пгогтапоп Ргос. ш Хчрап 1 (1961), 28 — 42. Примером такого приложения является точное решение линейных уравнений с рациональными коэффициентами.
По Различным причинам в этом случае удобно предположить, что модули ты гпт, ..., п1, являются простыми числами; линейные уравнения могут решаться независимо по каждому модулю гнз. Эта процедура была подробно исследована И. Ворошем (1. ВогоаЬ) и А. С. Френкелем (А. Б. Ргаепйе1) [Магй. Сошр. 20 (1966), 107-112) и в дальнейшем усовершенствована А.
С. Френкелем и Д. Левенталем (П. 1.оенепсЬа)) [Х Внь Ханова) Вигеаи оГ Бсапоагс(э 78В (197Ц, 67-75). При помощи этого метода на компьютере СПС 1604 меньше чем эа 20 мин было получего 9 независимых решений системы из 111 линейных уравнений со 120.ю неизвестными. Та же процедура полезна и для решения систем линейных уравнений, когда коэффициенты представлены в формате с плавающей точкой, а матрица коэффициентов плохо обусловлена. В таком виде коэффициенты трактуются как точные рациональные числа.
Модульный способ дает более быстрый метод вычисления исгпиниых результатов быстрее„чем традиционные методы могут дать приближениыц ответ! Последующие достижения в этой области опубликованы в работе М. Т. МсС!е!1ап,,74СЛХ 20 (1973), 563-588. Исследования, посвященные ограничениям в применении этого метода, опубликованы в работе Е. Н. Ваге)зз, .!. Хпвк ЛХасЬ.
апс«Арр!. 10 (1972), 68 — 104. Опубликованная литература по модулярной арифметике ориентирована, главным образом, .на разработку компьютеров, так как свойства свободного переноса модулярной арифметики делают ее привлекательной с точки зрения быстродействующих операций. Эта идея впервые бьща опубликована А. Свободой (А, БчоЬойа) и Ы.
Валахом (М, Ча«асЬ) в чехословацком журнале 81го1е п» Ергасотап! ХпуоггпасХ (Хпуоггпагюп Ргосевв!пя ЛХасЫпев) 3 (1955), 247-295, а затем независимо — Х. Д. Гарнером (Н. 1. Свгпег) [ХНЕ Тгапз. ЕС-8 (1959), 140 — 147[. Использование модулей 2кч — 1 было предложено А. С. Френкелем в работе,!АСЛХ8 (1961), 87-96, а некоторые преимущества модулей такого вида продемонстрированы А.
Шенхаге (А. ВсЬопЬайе) [Соп1рнс)пй 1 (1966), 182-196[. Дополнительную информацию и исчерпывающую библиографию по этому вопросу ыожно найти в книге Х. 8. 8наЬб, Н. 1. Тапа)ьз НевЫпе Аг!151пе11с апд йв Арр)каНопз го Сошрнгсг Тсгйпо!оду (Нем Уог(с: МсбгажН1!1, 1967). В 1968 году опубликована книга И. Я. Акинского и Д. И. Юдицкого„в которую включена глава, посвященная комплексным модулям [см.
Нет. Нонгпа!пе 8е МаНь Рпгез ег Арр!. 15 (1970), 159-160!*. Обсуждение мццулярной арифметики будет продолжено в разделе 4.3.3В. Сообщение ма доске объявяеммй гласило, что ан макоднтся в комнате 423, но прм взгляде на алан системы нумерации, с виду логичной, складывалось впечатление. будто ее разрабатывал либо лунатик, либо математик. — РОБеРт БэРнАРд (РОВейт ВАпмАЙО), тле сазе о1'спе мйв!пд Вгопгй (1988) УПРАЖНЕНИЯ 1. [об[ Найдите нсе целые числа и, удовлетворяющие всем слелующим условиям: и шеб 7 = 1, и шоб 11 = б, и шаб 13 = 5, 0 < и < 1000. 2.
«Мкб[ Будет лм теорема С по-прежнему справедливой, если допустить, чта а, им иы... ..., и, н и — произвольные вещественные числа (а не только целые)? 3. [мкб[ (Обобщеимак китайская теоре.ма об остатках.) пусть тып1ы...,т,— положительюке целые числа, 1п — наименьшее общее кратное чисел ты тпы..., т„н пусть а, иы иы..., и„— произвольные целые числа. Докажите, что имеется точно одно целое число и, удовлетворяющее соотношениям и щ и.
(по модулю то), 1<Х<т, цри условии, что и, гам (по модулю йети(тит.)), 1 < 4 <! < г, и что если последнее условие не ныполннетсн, та такого целого числа и не существует. ь См. Акннскнй И. Я. н Юлнцкнй Д. И. Машнннкн арнфметнка и остаточных классах.
— Мх сон. радио, 1988.— 440 с. (1970).— прим. нерка. 4. [30] Продолжите процесс, представленный в (13). Чему будут равны тг, тз, тг, ...г б. [М33] Предположим, что метод, определенный в (13), продалжшг до того момента, когда уже нельзя выбрать нн одного нового числа гл .
Получим ли мы зтнм "вульгарным" методом наибольшее возможное значение произведения тгтг... т„такое, что все тг будут тположительными целыми числами, меньшими 100, и попарно взаимно простыми? 6. [МЯ3] Пусть е, / и у — неотрицательные целые числа. а) Покажите, что 2' ш 2г (по модулю 2г — 1) в том и только в том случае, когда е ш / (по модулю 0).
Ь) Ддя заданных е пнх1 / = И и се шог( / = 1 докажите тождество ((1+2'+" +2'-' ') (2" — Ц) 4(21 — Ц = . (Таким образом, получена сравнительно простая формула для величины, обратной 2' — 1, по модулю 2г — 1, как зто и требуется в (23).) У.
[М31] Покажите, что (24) можно переписать следующим образом: аг +- иг шог1 тм аг г- (иг — аг) с,г шоб пгг, аз +- (иг — (аг + тг сг)) сыеш шоб тг, а, Ф- (и, — (а, + тг(аз+ тг(аз + . + т, га„г), .. ))) сг,... ср гр шог)т,. Если зто сделать, то вместо г(г — 1)/2 констант сам как в (24), потребуется только г — 1 констант С'г = еп сп гл шос1 гп .
Оцените с точки зрения вычислений на компьютере достоинства и недосгвтки настоящего варианта формулы (24) по сравнению с ее исходным вариантом. В. [МЖ] Докажите, что число и, определенное формулами (24) и (25), удовлетворяет условию (20). 9. [М30] Покажите, как перейти от значений аг, ..., а„фигурирующих в уравнении (25) и представленных в нем в системе со смешанным основанием, обратно к исходным осгвткам иг, ... „и,.
используя для вычислений значений иу только арифметические операции вычисления остатка по модулю тл 10. [М33] Мелос число и, принадлежащее симметричной области (10), можно было бы представить при помощи чисел иг, ..., и„таких, что и ш из (по модулю тз), удовлетворягоппгх условию -пг,/2 < и < т./2 вместо условия 0 < и < т, как указано в тексте раздела.
Раеемотриге процедуры модулярной арифметики для такого симметричного представления, включая процедуру перевода (24). 11. «МЗЯ] Допустим, все числа т. — нечетные и известно, что и = (иг,..., и„) — четное число при 0 < и < гл. Используя мадулярную арифметику, найдите достаточно быстрый способ вычисления и/2.
Обратите внимание на тождество 21 гзу г ш Г (по модулю т). В общем случае, если а и т являются взаимно простыми, можно найти (по алгоритму Евклида) число а' = (аг',..., а„'), такое, что са' ш 1 (по модулю т), Далее, если известно, что и кратно а, то и/а = иа вычисляем при помощи малулярного умножения. Если а не является взаимно простым с т, то деление выполняется значительно сложнее.
12. [М10] Дагшжнте, что, если О < и, а < т, модулярное сложение чисел и н а приведет к переполнению (т. е. полученное число будет находиться за пределамн допустимой облети) тогда и только тогда, когда сумма меньше числа и. (Таким образом, проблема обнаружения переполнения зквивалентна проблеме сравнения.) зз = Х ~х«91 Длк О С й < и. «взий ов «««аз««««Ю эффективные алгоритмы лля плклической свертки будут рассмотрены в разделах 4.3.3 и 4.6.4. рассмотрим «7-битовые целые числа в и с, которые представлены в виде и = ) из21 з "«, з а и = Х ~ек21"Ы"1, з а где 0 < ямт С 20Ь+Наз"1 1мт~.
(Такое представление является смесью оснований 2ыз" 1 и 2«а« "1.) Используя полходяшую циклическую свертку, предложите хороший способ поиска представления числа (ье) тоб (2з 1) [Указание. Не бойтесь использовать вычисления в формате с плавающей точкой.[ «4.3.3, Насколько быстро можно выполнять умножение Для умножения т-разрядного числа на и-разрядное традиционным методом (алгоритм 4.3.1М) требуется приблизительно стп операций, где с — константа. Для простоты в этом разделе предположим, что т = и, и обсудим следующий вопрос Для любого ли обычного вычислительного алгоритма умножения двух и-разрядных чисел время выполнения пропорционально п~ по мере увеличения и? (В этом вопросе под термином "обычный" понимается алгоритм, воспринимающий в качестве входа число и и два произвольных и-разрядных числа в позиционной интерпретации и на выходе дающий произведение этих чисел также в позиционной интерпретации.
Безусловно, если бы можно было для каждого значения и выбрать свой алгоритм, вопрос не представлял бы интереса, так как для любого конкретного значения и умножение можно было бы выполнить, просто отыскав результат в некоторой огромной таблице. Под термином "вычислительный алгоритм' понимается алгоритм, пригодный для применения на цифровом компьютере, подобном М1Х, а время выполнения — зто время, затраченное на таком компьютере на получение результата по такому алгоритму.) ° 13. [М26) (Аетамарфм.) Десятичное и-разркдное число х > 1 математиками-шутниками называетск автоморфом, если последни» и цифр числа хз равиы х. К примеру, 9 376 есть 4-разрядный автоморф, так как 9376з = 87909376.
[См. ЯаелсИс Атепсал 218 (Лавцаху, 1968), 125.[ а) Докажите, что и-разрядиое число х > 1 есть аатоморф тогда я только тогда, когда хто«$5" = 0 (или 1) и хто62" т 1 (или О) соответственно. (Таким образом, если т« = 2" и тз = 5", то в (7) только числа М~ и Мз являются и-разрялиыми автоморфами.) Ь) Докажите, что если х есть и-разрядный автоморф, то (Зх — 2хз) той 10з" является 2п-разрядным автоморфом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
