Формула "Февраль": результаты

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

Прочитав внимательно все письма, я посчитал, что будет нечестно, если бы был выбран и назван один победитель. Поэтому я решил рассказать про все письма, которые показались мне интересными.

Но для начала напомню проблему. Надо было написать формулу вычисления количества дней в феврале, учитывая, что каждый 4-ый год является високосным, при этом каждый 100-й является невисокосным, но каждый 400-й является високосным. Если на русском языке это выглядит немного непонятным, то на любом языке программирования все выстраивается в легко читаемую конструкцию. Кроме того, было выставлено условие, чтобы не использовались "условные конструкции".

По поводу "условных конструкций" очень хорошо написал в своем письме Виктор Рейников из Витебска. Он заметил неоднозначность определения термина "условная конструкция". Запрещается ли только использование "if ... else ..." и можно использовать "while ... do ..." или даже запрещены операторы отношений "<,>, <=,>=, <>, in". Кроме того, им же было замечено, что на уровне процессора в любом случае будет осуществляться проверка на деление на 0.

Но все же большинство читателей правильно поняли поставленное перед ними задание и сделали его. Дмитрий Иванов из Минска, студент 4го курса МГВРК, даже подумал, что я сомневался, что "кому-либо под силу решить эту простую задачу". К слову сказать, Дима представил одну из лучших реализаций данной задачи на языке Си.

В общем случае, задача решалась по одной из двух формул:

d=28+F(Y,400)-F(Y,100)+F(Y,4)
d=28+F(Y,400)+(1-F(Y,100))*F(Y,4)

где Y - номер года, а действие функции F(A,B) описывается следующим образом:

F(A,B)={

1, если остаток деления A на B = 0,

0, в обратном случае}

Многие смогли заметить, что (1-F(A,B) == !F(A,B), где ! (not) - операция логического отрицания. Но, кроме Евгения Ровнейко, практически никто не вспомнил, что операцию умножения можно заменить в данном случае на логическую операцию && (AND), а операцию сложения - на логическую операцию || (OR).

В этом случае вторая формула выглядела бы следующим образом:

d=28+F(Y,400)||!F(Y,100)) &&F(Y,4)

Вопрос встает в правильной реализации функции F(A,B).

Самым первым вариант прислал по электронной почте Евгений Ровнейко. Его формула выглядит следующим образом:

d:=28+Byte(((y mod 400) =0) or (((y mod 100)<>0) and ((y mod 4)=0)));

То есть F(A,B)=((A mod B)=0).

Руденя Виталий из Солигорска предложил использовать формулу округления:

F(A,B)=1-Trunc(1-(y mod 400)/399)

правда, его полная формула не была верна для всех значений y.

Олег Корбанов из г.п.Смиловичи Червенского района предложил следующий вариант:

y:=y-1;

d:=28+(y mod 400) div 399 - (y mod 100) div 99 + (y mod 4) div 3;

то есть F(A,B)=((A-1) mod B)div(B-1)

Вышеназванный Виктор Рейников вместо функции F(A,B) предложил использовать функцию 1-sgn(A mod B), где

sgn(X)={

1, X > 0,

0, X = 0,

-1, X <0}

возвращает знак числа X

В реализации на языке Pascal функция sgn(X) выглядит следующим образом:

sgn(X)=byte(X>0)-byte(X<0)

Немного особняком стоят реализации данной функции на языке Си. И Дмитрий Иванов, которого я упоминал выше, предложил следующую формулу:

d=28+!(y%400)+ !!(y%100)*!(y%4);

где F(A,B)=!(A%B)

Но основательнее всех к решению проблемы подошел Александр Фролов из Гомеля.

Он предложил следующие формулы:

1. d=28+!(y%400)-!(y%100)+!(y%4); F(A,B)=!(A%B)

после этого он заметил, что число 4 является степенью двойки, и поэтому операцию получения остатка от деления на 4 можно свести к операции побитового умножения:

(y%4)==(y&3)

2. d=28+!(y%400)-!(y%100)+!(y&3);

а после он заменил операцию логического отрицания:

3. d=28+!(y%400)-!(y%100)+((4-(y&3))>>2);

По скорости выполнения эти функции получили следующие результаты в интервале от 1 до 25000 года (каждый год по 4000 раз):

29.22с
20.71с
20.22с

Я хочу заметить, что лучшей производительности можно было бы добиться, используя побитовые операции вместо скалярных:

d=28+((!(y%400))|| (y%100)&&(!(y&3)));

кроме того, Александр заметил, что предложенная мною условная формула

a)

if((y%400)==0) d=29;

else if((y%100)==0) d=28;

else if((y%4)==0) d=29;

else d=28;

специально была дана неоптимальной, и что ее можно улучшить следующей перестройкой:

b)

if((y&3)==0)

if((y%100)==0)

if((y%400)==0) d=29;

else d=28;

else d=29;

else d=28;

Объяснение данной перестановки очень простое - на каждый год, не делящийся на 4, будет выполняться всего одно сравнение, на каждый год, делящийся на 4, но не делящийся на 100 - два сравнения и на все остальные - по три сравнения. Итого, с помощью обычной оптимизации Александр добился повышения производительности в среднем по выборке в семь раз.

Итак, места распределились следующим образом: