М19. Максимальная кратность значения зацепления, которая может встретиться при вычислении разности гаммы шифрмашины "Хагелин"

Рассмотрим колесо с w штифтами, имеющее зацепление k. При взятии разности на любом расстоянии d, не кратном w, есть четыре возможности, показанные в таблице A.1:

Таблица А.1

Наибольшие значения разности оказываются равными k. Если теперь мы возьмем разность повторно, на любом расстоянии, не кратном w, то наибольшие значения разности гаммы, которые могут встретиться, равны

k-(-k)=2k,

и, в случае отрицательных величин,

-k-(+k)=-2k.

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

2^(n-1)k.

Похожая ситуация возникает при реализации численных методов; там она принимает следующую форму:

единичная ошибка в таблице значений распространяется по "конусу ошибок"; максимальное значение ошибки после n операций взятия разности будет равно произведению величины исходной ошибки и максимального коэффициента в разложении (1+x)ⁿ.

Так, например, после шести операций взятия разности единичная ошибка распространится, и в центре шестой строки "конуса ошибок" будет в 20 раз больше по абсолютной величине. Более подробно об этом можно прочитать в [10.3].