В предыдущем номере газеты была опубликована статья Андрея Колесникова "Как заставить счетчик бегать по кругу, не используя условных конструкций". Хотелось бы сделать по этому поводу несколько дополнений.

Во-первых, посмотрим на предложенную формулу получения циклической последовательности от 1 до n:

i=i+1-(i div n)*n

и рассмотрим старую конструкцию:

if(i=n) then i=1 else i=i+1

которая является аналогом предыдущей формулы.

Старая конструкция состоит из следующих операций:

1. Сравнить i и n
2. Если они-неравны, то перейти к операции 5
3. Занести в i значение 1
4. Перейти к операции 6
5. Увеличить i на единицу
6. ...

причем операции 1, 2 выполняются при любом значении i, 3,4 - при i=n, и операция 5 - при i=[1..n-1]

То есть для генерации последовательности от 1 до n понадобится 2*n+2+1*(n-1)=3*n+1 операция

В случае предложенной формулы мы имеем следующие операции:

1. Получить результат от целочисленного деления i на n
2. Полученный результат умножить на n
3. Отнять от i полученный результат
4. Увеличить i на единицу

Причем все операции выполняются для каждого шага цикла.

То есть для генерации последовательности от 1 до n понадобится 4*n операций. При этом, заметьте, не учитывалось то, что операции целочисленного деления и умножения занимают больше тактов процессора, чем остальные.

А ведь можно было слегка видоизменить формулу:

i=i+1-(i div n)*n=1+i-(i div n)*n=1+(i-(i div n)*n)=1+(i mod n)

То есть с помощью элементарных преобразований получаем формулу

i=(i mod n)+1

где mod - это операция получения остатка от целочисленного деления.

Таким образом, получаем следующую последовательность операций:

1. Получить остаток от целочисленного деления i на n.
2. К полученному результату прибавить единицу.

То есть, для генерации последовательности от 1 до n требуется 2*n операции.

Нельзя однозначно сказать, что эта формула будет работать быстрее конструкции с условным оператором, так как операция получения остатка от целочисленного деления сравнима с самой операцией челочисленного деления. Для этого надо сравнивать операции по тактам. Но она будет работать примерно вдвое быстрее предложенной формулы. И ее можно (и нужно) использовать тогда, когда необходимо получать обсуждаемые последовательности.

Перейдем к следующему замечанию. Дело в том, что високосный год - это не тот год, который делится на 4. Ведь 1900-й не был високосным годом. А 2000-й, например, будет. На самом деле формула получения високосного года такая:

если год делится на 400

то

| год - високосный

иначе

| если год делится на 100

| то

| | год - не високосный

| иначе

| | если год делится на 4

| | то

| | | год - високосный

| | иначе

| | | год - не високосный

Формулу, определяющую количество дней в феврале без условных операторов, я указывать не буду. Сделаем так - имя того, кто пришлет самую быструю формулу, определяющую количество дней в феврале в зависимости от года, мы напечатаем в следующем выпуске газеты... Если такой найдется. Шлите письма в редакцию с пометкой "Формула-Февраль".

Вадим НАРЕЙКО,
[email protected],
www.belcaf.com