алгоритм, вероятно, необходимо внести следующие изменения:
a) на шаге 1 заменить max (m, 2n) на max (2m − 2n, 2n);
b) на шаге 4 заменить 23·2i на 23·2i−1.
Прежде чем приступать к программированию алгоритма Тоома—Кука или алгоритма деления, рекомендуем тщательно разобраться в них, ознакомившись с теорией, например по книге Кнута, неоднократно цитируемой здесь — Прим. перев.
(обратно)
34
На самом деле ai+1 = (ai/5²) · (2i − 1)/(2i + 1)). Чтобы не выполнять умножение, можно хранить кроме ai еще одно число bi, равное (21000 × 16)/52i−1. Тогда переход к следующему члену осуществляется по формулам: 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.
(обратно)