От издателей русского перевода   1

О книге "Искусство программирования"  2

От редактора перевода 4

ПРЕДИСЛОВИЕ 5

Предисловие к третьему изданию 6

ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ 8

УПРАЖНЕНИЯ 10

ГЛАВА 3

СЛУЧАЙНЫЕ ЧИСЛА 11

3.1. ВВЕДЕНИЕ 11

УПРАЖНЕНИЯ 17

3.2.ГЕНЕРИРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ

СЛУЧАЙНЫХ ЧИСЕЛ 21

3.2.1. Линейный конгруэнтный метод 21

УПРАЖНЕНИЯ 22

3.2.1.1. Выбор модуля. 23

УПРАЖНЕНИЯ 26

3.2.1.2. Выбор множителя.28

УПРАЖНЕНИЯ 33

3.2.1.3. Потенциал. 35

УПРАЖНЕНИЯ 37

3.2.2. Другие методы 38

УПРАЖНЕНИЯ 49

3.3. СТАТИСТИЧЕСКИЕ КРИТЕРИИ 54

3.3.1. Основные: критерии проверки случайных наблюдений 55

С. История, библиография и теория. 68

УПРАЖНЕНИЯ 71

3.3.2. Эмпирические критерии 74

УПРАЖНЕНИЯ 90

3.3.3. Теоретические критерии 95

УПРАЖНЕНИЯ (часть 1) 105

УПРАЖНЕНИЯ (часть 2) 107

3.3.4. Спектральный критерий 108

А. Идеи, служащие обоснованием критерия. 108

*В. Дальнейшее исследование критерия. 112

С. Обоснование вычислительных методов. 113

*D. Как выполнить спектральный критерий. 117

Е. Рейтинги различных генераторов. 120

*F. Связь с критерием серий. 125

G.  Историческая справка. 130

УПРАЖНЕНИЯ 131

3.4. ДРУГИЕ ВИДЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ 135

3.4.1. Численные распределения 135

УПРАЖНЕНИЯ  156

3.4.2. Случайные выборки и перемешивания 160

УПРАЖНЕНИЯ 164

*3.5. ЧТО ТАКОЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ 167

А. Вводные замечания.167

С. Эквивалентно ли понятие ∞-распределенности понятию случайности? 177

D. Существование случайных последовательностей. 182

F. Псевдослучайные числа. 190

УПРАЖНЕНИЯ 200

3.6. ВЫВОДЫ 205

УПРАЖНЕНИЯ 210

ГЛАВА 4

АРИФМЕТИКА 216

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

УПРАЖНЕНИЯ 233

4.2. АРИФМЕТИКА ЧИСЕЛ С ПЛАВАЮЩЕЙ ТОЧКОЙ 239

4.2.1. Вычисления с однократной точностью 239

А. Обозначение чисел с плавающей точкой. 239

В. Нормализованные вычисления. 240

С. Аппаратная реализация арифметических действий над числами

с плавающей точкой. 249

D. История и библиография. 251

УПРАЖНЕНИЯ 253

4.2.2. Точность арифметических операций с плавающей точкой 256

А. Аксиоматический подход. 257

В. Арифметические действия над ненормализованными числами

с плавающей точкой. 265

С. Арифметика интервалов. 267

D. История и библиография. 268

УПРАЖНЕНИЯ 269

*4.2.3. Вычисления с удвоенной точностью 273

УПРАЖНЕНИЯ 280

4.2.4. Распределение чисел в формате с плавающей точкой 281

А. Программы сложения и вычитания. 281

В. Дробные части. 282

УПРАЖНЕНИЯ 291

4.3. АРИФМЕТИКА МНОГОКРАТНОЙ ТОЧНОСТИ  294

4.3.1. Классические алгоритмы 294

УПРАЖНЕНИЯ 311

*4.3.2. Модулярная арифметика 315

УПРАЖНЕНИЯ 323

*4.3.3. Насколько быстро можно выполнять умножение 325

*В. Модулярный метод. 334

С. Умножение при помощи дискретного преобразования Фурье. 337

Е. Умножение в реальном времени. 345

УПРАЖНЕНИЯ 348

4.4. ПРЕОБРАЗОВАНИЕ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ 351

А. Четыре основных метода. 351

В. Преобразование с однократной точностью. 352

С. Вычисления вручную. 355

D. Преобразование чисел с плавающей точкой. 358

Е. Преобразование с многократной точностью. 359

F. История и библиография. 359

УПРАЖНЕНИЯ 360

4.5. АРИФМЕТИКА РАЦИОНАЛЬНЫХ ЧИСЕЛ 363

4.5.1. Дроби 363

УПРАЖНЕНИЯ 365

4.5.2. Наибольший общий делитель 367

Алгоритм Евклида. 368

Алгоритм Е (Оригинальный алгоритм Евклида). 370

Алгоритм А (Алгоритм Евклида в современной редакции). 370

Бинарный метод. 371

Алгоритм Х (Обобщенный алгоритм. Евклида). 376

Вычисление с высокой точностью. 379

Алгоритм L (Алгоритм Евклида для больших чисел). 381

УПРАЖНЕНИЯ 387

*4.5.3. Анализ алгоритма Евклида 391

УПРАЖНЕНИЯ 408

4.5.4. Разложение на простые множители 415

Деление и разложение на множители. 415

Разложение на простые множители с использованием псевдослучайных

циклов. 420

Метод Ферма. 423

Алгоритм Р (Вероятностная проверка, является ли число простым). 432

Разложение на простые множители при помощи цепных дробей. 434

*Теоретическая верхняя граница. 439

Секретные множители. 442

Самые большие известные простые числа. 446

УПРАЖНЕНИЯ 451

4.6. ПОЛИНОМИАЛЬНАЯ АРИФМЕТИКА 459

УПРАЖНЕНИЯ 461

4.6.1. Деление полиномов 461

Области единственного разложения на множители. 462

Наибольшие общие делители. 465

Алгоритм R (Псевдоделение полиномов). 467

Алгоритм Коллинза. 469

УПРАЖНЕНИЯ  476

*4.6.2. Разложение полиномов на множители 480

Разложение с различными степенями. 489

Наибольшие общие делители. 495

УПРАЖНЕНИЯ 497

4.6.3. Вычисление степеней 503

Уменьшение количества операций умножения. 505

Аддитивные цепочки. 507

Специальные классы цепочек. 509

Некоторые предположения. 519

УПРАЖНЕНИЯ 524

4.6.4. Вычисление полиномов 528

Табулирование значений полинома. 531

Производные и замена переменной. 532

.Цепочки полиномов (полиномиальные цепочки). 537

*Билинейные формы. 549

УПРАЖНЕНИЯ 558

*4.7. ОПЕРАЦИИ СО СТЕПЕННЫМИ РЯДАМИ 569

Алгоритм N (Обобщенное обращение степенного ряда методом Ньютона). 373

Итерация рядов. 574

Алгебраические функции. 577

УПРАЖНЕНИЯ 577

ОТВЕТЫ К УПРАЖНЕНИЯМ 582

РАЗДЕЛ 3.1 582

РАЗДЕЛ 3.2.1 587

РАЗДЕЛ 3.2.1.1 587

РАЗДЕЛ 3.2.1.2 592

РАЗДЕЛ 3.2.1.3 595

РАЗДЕЛ 3.2.2 595

РАЗДЕЛ 3.3.1 604

РАЗДЕЛ 3.3.2 607

РАЗДЕЛ 3.3.3 618

РАЗДЕЛ 3.4.1 630

РАЗДЕЛ 3.4.2 637

РАЗДЕЛ 3.5 639

РАЗДЕЛ 4.1 652

РАЗДЕЛ 4.2.1 659

РАЗДЕЛ 4.2.2 661

РАЗДЕЛ 4.2.3 665

РАЗДЕЛ 4.2.4 667

РАЗДЕЛ 4.3.1 671

РАЗДЕЛ 4.3.2 678

РАЗДЕЛ 4.3.3 681

РАЗДЕЛ 4.4 684

РАЗДЕЛ 4.5.1 687

РАЗДЕЛ 4.5.2 689

РАЗДЕЛ 4.5.3 696

РАЗДЕЛ 4.5.4  708

РАЗДЕЛ 4.6 724

РАЗДЕЛ 4.6.1 724

РАЗДЕЛ 4.6.2 731

РАЗДЕЛ 4.6.3 744

РАЗДЕЛ 4.6.4 751

РАЗДЕЛ 4.7 773

ПРИЛОЖЕНИЕ А

ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ  780

ПРИЛОЖЕНИЕ Б

 

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ 784