погрешность ЭВМ. При обращении матрицы Гильберта ведущим элементом всегда должен оказываться ; если же алгоритм выбирает в качестве ведущего элемент, лежащий ниже, то это означает, что погрешность уже очень велика.

(обратно)

31

Как здесь не отметить, что самую плодотворную идею по части быстрого умножения вы можете позаимствовать у кроликов. Их многочисленное потомство — тому порука.

(обратно)

32

Дадим небольшое пояснение к рисунку: long — длинный, stack — стек, control — управляющий pop … into — удалить вершину … и поместить в, abort — аварийное окончание. Остальные ключевые слова имеют тот же смысл, что в языке Паскаль. — Прим. перев.

(обратно)

33

В алгоритм, вероятно, необходимо внести следующие изменения:

a) на шаге 1 заменить max (m, 2n) на max (2m − 2n, 2n);

b) на шаге 4 заменить 2^3·2i на 2^3·2i−1.

Прежде чем приступать к программированию алгоритма Тоома—Кука или алгоритма деления, рекомендуем тщательно разобраться в них, ознакомившись с теорией, например по книге Кнута, неоднократно цитируемой здесь — Прим. перев.

(обратно)

34

На самом деле ai+1 = (ai/5²) · (2i − 1)/(2i + 1)). Чтобы не выполнять умножение, можно хранить кроме ai еще одно число bi, равное (2¹⁰⁰⁰ × 16)/5²ⁱ⁻¹. Тогда переход к следующему члену осуществляется по формулам: bi+1 = bi/5², ai+1 = bi+1/(2i + 1). — Прим. перев.

(обратно)

35

Эти алгоритмы для очень длинных чисел работают еще быстрее алгоритма Тоома—Кука, затрачивая на умножение n-разрядных чисел время, пропорциональное n log n log log n — Прим. перев.

(обратно)

36

В § 4.4 этой книги приведены алгоритмы перевода чисел в десятичную систему. — Прим. перев.

(обратно)

37

В журнале «Наука и жизнь» № 2, 1978, с. 150–151; № 8, 1978, с. 142—143, опубликован вариант этой игры под названием «Быки и коровы». — Прим. перев.

(обратно)

38

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

(обратно)

39

В оригинале, разумеется, все рассуждения проводятся для английского текста. — Прим. перев.

(обратно)

40

В криптографии используются некоторые слова, которые люди непосвященные часто употребляют не совсем правильно. Шифрование — это способ засекречивания сообщения путем замены или перемешивания букв, кодирование же подразумевает замену целых слов или фраз, а не отдельных букв. Лица, владеющие шифром или кодом, шифруют или кодируют свои сообщения, а получатели сообщений дешифруют или декодируют их. Лица, пытающиеся узнать чужой секрет, расшифровывают сообщения; различие между этими глаголами соответствует различию между знанием секрета шифра и попыткой разгадать его. Тот, кто составляет секретные сообщения, занимается криптографией, или тайнописью, а тот, кто стремится прочитать чужое секретное сообщение, занимается анализом криптограмм (cryptanalysis). Применяемые для этого методы составляют предмет науки, которая по-английски называется cryptology.

(обратно)

41

American Standart Code for Information Interchange—американский стандартный 8-разрядный код для обмена информацией. — Прим. перев.

(обратно)

42

Признак косвенной адресации, — Прим. перев.

(обратно)

43

Аббревиатуры от Register-Register (регистр-регистр), Register-Storage (регистр-память), IMmediate (непосредственная), CHaracter (байтовая). — Прим. перев.

(обратно)

44

На языке ассемблера разряд косвенной адресации задается звездочкой перед полем адреса, как, например, LN,R1 * A,R.2.

(обратно)

45

Аббревиатуры от Overflow (переполнение), Less than (меньше, чем), Greater than (больше, чем), Equal (равно). — Прим, перев.

(обратно)

46

При установке признака результата предполагается, что в операциях отношения слева стоит первый из указанных операндов, а справа — второй. То есть, если выработан признак «меньше, чем», значит, первый операнд меньше второго.

(обратно)

47

Хотя во всех командах Reverse значения двух операндов и меняются ролями, результат записывается туда же, куда и раньше.

(обратно)

48

Мнемоническим обозначениям команд арифметических операций с вещественными числами предшествует буква «F» в силу исторически сложившегося названия представления вещественных чисел как чисел с плавающей точкой (floating point). Это отражается также в мнемонике кодов операций FLOATR, FLOAT и FLOATI.

(обратно)

49

Эти команды обозначены FIXR, FIX и FIXI, поскольку представление целых чисел исторически называется представлением с фиксированной точкой (fixed point).

(обратно)

50

Счетчик сдвига, по абсолютной величине больший 32, определяет те же действия, что и соответствующий счетчик, по модулю равный или меньший 32. При выполнении команды сдвига большие значения счетчика заменяются меньшими

(обратно)

51

Такое многозначное употребление слова «литера» вновь возникнет при обсуждении загрузчика УМ. Постарайтесь четко уяснить разницу между литерами (байтами) в памяти и литерами во входном и выходном файлах. Во внутренней литере всегда содержится достаточно данных, чтобы представить одну внешнюю литеру, в то время как внешней литеры иногда недостаточно, чтобы закодировать одну внутреннюю литеру.

(обратно)

52

Вообще, если A есть начальный адрес текущего загружаемого модуля, то всегда выполняется соотношение САР — А = СОР. То есть САР и СОР при всех обстоятельствах изменяются согласованно, образуя тандем.

(обратно)

53

Чтобы вспомнить различие между внутренними и внешними литерами, перечитайте раздел о файле абсолютной загрузки в гл. 25.

(обратно)

54

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

(обратно)

55

В русском переводе приходится склонять нетерминальные символы грамматики. — Прим. перев.

(обратно)

56

Одной из главных трудностей при доказательстве правильности программ является выделение смысла программы из написанных программистом императивов. Поскольку правильность зависит от отображений желаемого в действительное, ценно все, что помогает вскрыть намерения. Вводимое в Мини разграничение функций и подпрограмм — шажок в этом направлении. Заметим также, что хороший программист