Рассчитана на широкий круг программистов.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Второй том монографии Д. Кнута, содержащий две главы: „Случайные числа" и „Арифметика", посвящен теории алгоритмов, составляющих область, пограничную между традиционными численными методами и программированием для ЭВМ. Как и в первом томе, исследуемые алгоритмы описываются полуформальным способом и большое место в изложении занимают вопросы эффективности алгоритмов.
Общеизвестно, сколь большое значение для развития науки имела хорошая система счисления, и великолепную шестидесяте-ричную систему счисления для целых чисел и дробей мы находим уже в древнем Вавилоне. Казалось бы, за истекшие тысячелетия в чем-чем, а в том, что касается систем счисления и техники счета, наука уже давно получила окончательные и наилучшие решения. Оказывается, совсем нет! Возникновение ЭВМ побудило заново пересмотреть вопросы о системах счисления, об оптимальных способах выполнения арифметических операций над целыми числами, об операциях в системах с плавающей точкой и т. п. И здесь мы сталкиваемся с совершенно замечательными и неожиданными фактами. Так, например, распространенное и казавшееся правдоподобным мнение, что сложность „школьного" метода умножения чисел не может быть уменьшена, было опровергнуто в начале шестидесятых годов. Это не единственный сюрприз, который ожидает читателя в главе „Арифметика". К этому нужно добавить, что исследование среднего времени выполнения некоторых алгоритмов, например алгоритма Евклида нахождения общего наибольшего делителя двух чисел, приводит к очень красивым построениям и вскрывает глубокие связи с теоретической математикой.
В главе „Случайные числа", занимающей лишь треть книги, рассматриваются различные алгоритмы генерирования случайных последовательностей, организация тестов на случайность и т. п. Заканчивается эта глава обсуждением вопроса о том, какую бесконечную последовательность можно считать случайной. И здесь автор вынужден выйти далеко за пределы алгоритмической стороны дела.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода................... 5
Предисловие ............................ 7
Замечания об упражнениях..................... 10
Глава 3. | Случайные числа............. 13
3.1. Введение .......................•. . 13
3.2. Выработка равномерно распределенных случайных чисел . . 22
3.2.1. Линейный конгруэнтный метод..........г . 22
3.2.1.1. Выбор модуля................. 24
3.2.1.2. Выбор множителя.............. 28
3.2.1.3. Мощность.................. 36
3.2.2. Другие методы ................... 40
3.3. Статистические тесты ................... 52
3.3.1. Универсальные тесты для анализа случайных последовательностей.................... 53
3.3.2. Эмпирические тесты................. 75
*3.3.3. Теоретические тесты................. 91
3.3.4. Спектральный тест ................. 105
3.4. Другие виды случайных величин.............. 126
3.4.1. Числовые распределения.............. 127
3.4.2. Случайная выборка и перемешивание . . ...... 151
*3.5. Что такое случайная последовательность?.....- .... 158
3.6. Выводы........................ 193
Глава 4. | Арифметика................ 200
4.1. Позиционные системы счисления.............. 201
4.2. Арифметика чисел с плавающей точкой........... 225
4.2.1. Вычисления с однократной точностью ........ 225
4.2.2. Точность выполнения арифметических действий в системе с плавающей точкой.............. 243
4.2.3. Вычисления с двойной точностью........... 260
4.2.4. Статистическое распределение ............ 268
4.3. Арифметика многократной точности ............ 282
4.3.1. Классические алгоритмы............... 282
*4.3.2. Модулярная арифметика............... 303
4.3.3. Как быстро можем мы умножать?.......... 314
4.4. Преобразование из одной системы счисления в другую . , . 342
4.5. Арифметика рациональных чисел.............. 354
4.5.1. Дроби ....................... 354
4.5.2. Наибольший общий делитель............. 356
*4.5.3. Анализ алгоритма Евклида............. 384
4.5.4. Разложение на простые множители.......... 409
4.6. Полиномиальная арифметика . . •.............. 437
4.6.1. Деление многочленов................ 440
723
4.6.2. Разложение многочленов на простые множители ... 461
4.6.3. Вычисление степеней ................ 482
4.6.4. Вычисление многочленов ..........., . . 510
*4.7. Работа со степенными рядами............... 538
Ответы к упражнениям....................... 546
Приложение A. MIX........................ 661
A.I. Описание MIX...................... 661
А.2. Автокод машины MIX................... 684
Приложение В. Таблицы числовых величин............. 699
Приложение С. Указатель обозначений............... 703
Именной указатель......................... 707
Предметный указатель........................ 715
Глоссарий . ;........................... 720
Цена: 300руб.
