13. [М25] Сравните генератор вычитания с заимствованием из упр. 3.2.1.1-12 с генератором Фибоначчи с запаздыванием, реализованным в программах этого рюдела.

► 14. [Л/55] (Будущее против прошлого.) Пусть ЛГп = (Ап-з?+Xn ioo) mod 2. Рассмотрим последовательность

{Oi ii. •.) = {Ао, Xi,..., А99, А200, А201,..., Хгээ, А400, Х401,..., А499, Аеоо, •..).

(Она соответствует неоднократно вызываемой программе ran.array(а,200), когда рассматриваются только младшие значащие двоичные разряды после отбрасывания половины элементов.) Следующий эксперимент был повторен один миллион раз с использованием последовательности (Уп): "Генерируем 100 случайных двоичных разрядов, затем, если 60 или более из них равны нулю, генерируем еще один и печатаем его". В результате было напечатано 14 527 нулей и 13 955 единиц, но вероятность того, что 28 482 случайных двоичных разряда содержат самое большее 13 955 единиц, равна приблизительно .000358. Дайте математическое объяснение, почему так много нулей будет на выходе.

► 15. [25] Напишите на языке С программу генерирования для случайных целых чисел, которые получаются с помощью программы гап-аггау, отбрасывая все, кроме первых 100, элементы из каждых 1 009 элементов, как рекомендуется в разделе.

ГЛАВА 4

АРИФМЕТИКА

в математической практике нет ничего более хлопотного (правы любезные студенты-математики), что более всего досаждало бы и мешало вычислителям, чем перемножение, деление или извлечение квадратных и кубических корней больших чисел. Выполнение этих операций не только приводит к значительным потерям времени, но и сопряжено с такой массой скрытых ошибок, что я начал размышлять о поисках надежного и удобного средства устранения подобных помех.

- ДЖОН НЕПЕР (J. NAPIER [NEPAIR]) (1616)

Терпеть не могу складывать. Самая большая ошибка - считать арифметику точное наукой. Существуют... тайные законы Чисел, которые может постигнуть только ум, подобный моему. К примеру, при сложении чисел в столбик сначала снизу вверх, а затем наоборот вы всегда получите разные суммы.

- М. п. ЛА ТУШ (М. Р. LA ТОиСНЕ) (1878)

Не могу представить, чтобы кому-нибудь понадобилось выполнять умножение со скоростью 40 ООО или даже 4 ООО операций в час; такое радикальное средство, как переход к восьмеричной системе счисления, не следует навязывать всему человечествуради нескольких личностей.

- Ф. X. УЭЙЛС (F. X. WALES) (1936)

Большинство специалистов в теории чисел не проявляют интереса к арифметике.

- Б. ПАРЛЕТТ (В. PARLETT) (1979)

Основное назначение этой главы - тщательный анализ четырех основных действий арифметики: сложения, вычитания, умножения и деления. Арифметику многие считают тривиальной дисциплиной, которой обучают детей, а арифметические действия - уделом компьютеров; но мы увидим далее, что арифметика - это увлекательный предмет с множеством интересных аспектов. Она лежит в основе многих важных компьютерных приложений, поэтому необходимо самым тщательным образом изучить эффективные методы вычислительных операций над числами.

На самом деле, арифметика - это живая и все еще успешно развивающаяся отрасль науки, сыгравшая важную роль в мировой истории. В этой главе будут проанализированы алгоритмы выполнения операций над различными типами величин: числами с "плавающей точкой", очень большими числами, дробями (рациональными числами), полиномами и степенными рядами. Кроме того, здесь будут рассмотрены связанные с ними вопросы, такие как преобразование из одной системы счисления в другую, разложение чисел на множители и операции над полиномами.

4.1. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

Способ выполнения арифметических операций тесно связан со способом представления чисел, над которыми выполняются операции. Поэтому резонно начать изучение предмета с обсуждения принципиальных подходов к представлению чисел.

Позиционное представление с основанием Ь (или по основанию Ь) определяется правилом

(...03020100.a ia 2 )ь

= • • • + озЬ 4- оаЬ 4- OlЬ + оо + o lЬ~ 4- о 2Ь~ 4- • • •; (1)

например, (520.3)б = 5 • 6 4- 2 • 6 4- О 4- 3 • 6~ = 192. Традиционная десятичная система - это, разумеется, частный случай, когда Ь равно десяти, а значения Ok выбираются из "десятичных цифр" О, 1, 2, 3, 4, 5, 6, 7, 8, 9; в этом случае индекс Ь в (1) может быть опущен.

Простейщие обобщения десятичной системы получаются, когда в качестве Ь берется целое число, большее 1, а в качестве o;t-целые числа из интервала О < ak < Ь. Таким образом приходим к стандартной двоичной (6 = 2), троичной (6 = 3), четверичной (6 = 4), пятеричной (6 = 5), ... системам счисления. В общем случае в качестве 6 можно взять любое ненулевое число, а числа Ok выбирать из произвольного заранее заданного ряда чисел. Как мы увидим далее, это приводит к некоторым интересным ситуациям. Точка между оо и o i в (1) называется позиционной или разделяющей. (Если 6 = 10, точка также называется десятичной; в случае, когда 6 = 2, она иногда называется двоичной точкой и т. д.). В странах Европейского континента (Великобритания, как известно, себя к таковым не относит) вместо разделяющей точки часто используется запятая.

Числа Ok в (1) называются цифрами представления. Цифру ajt с большим к называют более значимой, чем ojt с меньшим к; крайнюю слева, или "ведущую", цифру называют наиболее значимой, а крайнюю справа, или "хвостовую",--наименее значимой. В стандартной двоичной системе двоичные цифры зачастую называют битами; в стандартной шестнадцатеричной системе (с основанием шестнадцать) шестнадцатеричные цифры от нуля до пятнадцати обычно обозначаются так:

О, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F.

История развития способов представления чисел - увлекательная повесть, так как их развитие происходит параллельно развитию самой цивилизации. Однако при подробном рассмотрении этой истории мы ушли бы далеко в сторону от главной темы; тем не менее полезно конспективно изложить основные ее моменты.

Наиболее ранние формы представления чисел, обнаруженные в древних цивилизациях, обычно основываются на использовании групп пальцев, кучек камней и т. п. с дополнительными соглашениями о замене некоторой группы, скажем, из пяти или десяти объектов одним объектом специального вида или объектом, расположенным в специальном месте. Подобные системы естественно приводят к наиболее ранним из известных способам представления чисел в письменном виде, таким как вавилонские, египетские, греческие, китайские и римские числа, но такого рода обозначения чрезвычайно неудобны для выполнения арифметических операций, кроме разве что простейших случаев.