Этюды для программистов

  long integer [n, u], [n, v];

  integer K, Q, R, q [0: 10], r [0: 10];

  long integer stack C, U, V, W;

  control stack code;

  integer k, p, s, t, i, j;

  long integer X, Y, Z, w;

  control A;

  Шаг 1;

  Шаг 2;

  while code не пуст do

    while k > 1 do

      шаг 5; шаг 6; шаг 7; шаг 8;

    end;

    шаг 9;

    pop code into A; while А = интерполировать do

      шаг 11;

      for i=1 to 2t do шаг 13;

      for i=2t − 1 downto 1 do шаг 15;

      шаг 16;

    end;

    if A = стоп then return [m, w];

    if A = сохранить then шаг 18; else abort;

  end; * главного цикла *

end; * алгоритма Тоома—Кука *

Рисунок 22.1. Управляющая схема алгоритма Тоома—Кука.

2. (Таблицы размеров.) Значения массивов, вычисленные на шаге 2, показаны в табл. 22.1; число в колонке n_k равно наибольшему числу битов, которое может быть обработано алгоритмом при K = k. Очевидно, что предельное значение 10 для K не является очень серьезным ограничением. При желании этот предел можно повысить.

Таблица 22.1. Значения q, r и n
k	qk	rk	nk
0	16	4
1	16	4	32
2	64	4	80
3	256	4	320
4	1024	8	1280
5	8192	8	9216
6	65536	16	73728
7	1048576	16	1114112
8	16777216	16	17825792
9	268435456	32	285212672
10	8589934592	32	8858370038

3. (Глубина стеков в первом цикле.) Максимальная глубина стеков U и V на шагах с 5-го по 8-й равна 2(r_K−1 + 1). Глубина стека С может возрастать до .

4. (Глубина стеков во втором цикле.) Общая глубина стека W может достигать . Управляющий стек может достигать глубины . На шагах 14, 15 и 16 верхняя часть стека W используется как массив. Этот массив может содержать максимум 2r_k−1 + 2 элементов.

5. (Размер исходных данных.) Для любого числа битов n в диапазоне n_i−1 + 1 ≤ n ≤ n_i алгоритм Тоома—Кука требует одинакового времени вычислений. Таким образом, сложность вычислений весьма негладко зависит от размера исходных данных. Поэтому при выполнении длинных вычислений имеет смысл подбирать число битов вблизи верхнего конца одного из диапазонов для n. Учитывайте, что для представления одной десятичной цифры требуется примерно 3⅓ бита.

6. (Как умножить два 32-разрядных числа?) На шаге 9 требуется умножить два 32-разрядных числа, получив 64-разрядное произведение, причем оба сомножителя обязательно положительны. На многих ЭВМ имеется аппаратная возможность такого умножения, но результат нельзя получить, пользуясь языками высокого уровня. Ну и, конечно, некоторые ЭВМ не имеют подобней аппаратуры. Поэтому для выполнения этого умножения нужно написать подпрограмму, причем она должна быть эффективной, поскольку время работы алгоритма определяется главным образом временем умножения 32-разрядных чисел. Вероятно, достаточно хорошим методом будет разбиение чисел на части и моделирование ручного способа умножения. Тем не менее если нужно получить произведение uv и число и записано в виде u₁·2¹⁶ + u₀, a v — в виде v₁·2¹⁶ + v₀, то произведением будет

(2³² + 2¹⁶)u₁v₁ + 2¹⁶(u1 − u0)(v0 − v1) + (2¹⁶ + 1)u₀v₀.

Вычисление по этой формуле выполняется при помощи только 16-битовых вычитаний и умножений, а также некоторых сдвигов и сложений. Обратите внимание, что одно умножение сэкономлено.

Что можно сказать относительно деления?

При вычислении предложенных рядов наряду с умножением используется деление чисел высокой точности. К счастью, при помощи алгоритма умножения удается выполнять деление почти так же быстро, как умножение. Для нахождения частного нужно приблизительно угадать число, обратное к делителю, скорректировать его, чтобы обратное стало точным, и затем умножить на делимое. Уточнение обратного осуществляется по методу Ньютона. Даны два числа [m, u] и [n, v]; мы считаем, что u ≥ v (хотя это предположение несущественно) и что n-й бит v равен 1 (т. е. у v нет старших нулей). Чем больше разница размеров и и v, тем более точным будет частное; разницу можно увеличить, умножая и на степень двойки. Отметим, что алгоритм деления будет неоднократно вызывать алгоритм умножения. Для нескольких первых из этих умножений можно воспользоваться обычной операцией умножения коротких чисел. Кроме того, все умножения и деления на степень двойки суть фактически сдвиги влево и вправо.

1. (Выбор размера обратного.) Найти наименьшее j, такое, что 2^j ≥ max (m, 2n). Присвоить к значение 2^j−1.

2. (Нормализация v.) Присвоить [k, v] значение 2^k−n [n, v]. На этом шаге мы сдвигаем v влево, чтобы оно заняло k битов, причем левый бит был бы равен 1. Присвоить [2, а] значение [2, 2].