понедельник, 22 ноября 2010 г.

Floor через Trunc

Продолжаем наши игры с плавающими точками (начало тут).

Кто-то заметил, что ENTIER (floor) это такая королевская функция, функция всех функций, из из которой легко получаются все остальные. И что мол Вирт выбрал её именно поэтому, мол самый базисный базис.

Однако я позволил себе в этом несколько усомниться. И на то были причины. Во-первых Trunc (отбрасывание дробной части) давно и успешно применяется в Си, и никто по этому поводу не плачет, во-вторых Trunc явно проще, а следовательно, скорее всего, первичней, ну и наконец, в своем последнем творении -- Оберон-07 Вирт закопал таки EITHER и заменил его на Trunc (обозвав его почему-то словом FLOOR).

Посему я задался вопросом, а как бы мне получить из Trunc'a Floor? Попил чайку, и в результате получилась вот такая вот функция:
int Floor(float a)
{
int b = (int)a;
if (a>=0 || (a-b) == 0) return b;
else return b-1;
}
Причем она почему-то работает быстрее чем стандартная floorf. При чем, если включить sse инструкции то начинает работать ещё раза в два быстрее.

Итак, мы получили свой любимый Floor/ENTIER а дальше можем спокойно сделать с ним всё что угодно. Получать из него Ceil, Round и т.п.

Т.о. функция отбрасывающая дробную часть является таки базисной, основополагающей. И Вирт был прав когда отказался от ENTIER её пользу в Обероне-07. Также были правы создатели тёплых ламповых Сей. Правда они сделали это на десятилетия раньше Вирта. А те кто фанатеют от каждого решения Вирта в своих языках -- не правы. Он тоже может ошибаться.

8 комментариев:

toiama комментирует...

> и заменил его на Trunc (обозвав его почему-то словом FLOOR).

Да, те, кто знаком с математическим значением floor, будут путаться на этом месте.

> Т.о. функция отбрасывающая дробную часть является таки базисной, основополагающей.

И это серьёзное заключение? : )

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

valexey комментирует...

Вообще то выводится. И математически и алгоритмически. Как из Trunc получить Floor алгоритмически, я показал.

А вот тут как получить обратное математически: http://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Truncation

Правда нам понадобится ещё модуль, и сигнум :-)

Но базисность я имел ввиду именно с алгоритмической точки зрения. Получить просто целую часть числа, отбросив всю дробную проще чем получить максимальное целое число не большее данного.

По кр. мере в тех представлениях чисел с плавающей точкой это именно так.

Есть ли такое представление, чтобы при прочих равных (т.е. без деградации производительности на всех прочих операциях), Floor был бы быстрее чем Trunc?

Romiras комментирует...

> Т.о. функция отбрасывающая дробную часть является таки базисной, основополагающей.
Всё относительно. С помощью Floor также получается Trunc, как и наоборот. Соответственно, имея Floor, можем получить и Ceil, Round и Trunc.

> Trunc проще Floor
Заявление "Trunc проще Floor" неубедительно. Если не считать дополнительного сравнения у Trunc, они равносильны как с математической точки зрения, так и в количестве машинных инструкций.

int truncate_int (double x)
{
assert (x > static_cast (INT_MIN / 2) – 1.0);
assert (x < static_cast (INT_MAX / 2) + 1.0);
const float
round_towards_m_i = -0.5f;
int i;
__asm
{
fld x
fadd st, st (0)
fabs
fadd round_towards_m_i
fistp i
sar i, 1
}
if (x < 0)
{
i = -i;
}
return (i);
}

valexey комментирует...

Вы слишком высокоуровнево смотрите. Возьмите IEEE 754 и посмотрите что проще из такого представления числа получить.

Число инструкций впринципе значения не имеет, имеет значение их совокупный вес. И имеет значение что у нас будет, если конвертация float->int не поддерживается железякой (что бывает довольно часто).

Romiras комментирует...

Утверждения без математического доказательства не принимаются. Раз вы утверждаете, то потрудитесь обосновать это математически.

valexey комментирует...

Боюсь что чисто математического доказательства тут будет не достаточно, по понятным причинам.

toiama комментирует...

> Есть ли такое представление, чтобы при прочих равных (т.е. без деградации производительности на всех прочих операциях), Floor был бы быстрее чем Trunc?

Если к результату работы Trunc добавить значение последнего бита исходного числа (это знак округляемого числа), то получится Floor, а если из Floor вычесть этот бит, то получится Trunc. Так кто кого базовее? : ).

Так что формула Trunc + SignBit = Floor имеет право на жизнь. Или формула Trunc - SignBit = Floor (в зависимости от того, к абсолютной величине она будет применяться или уже к готовому целому со знаком).

Например, для чисел 13,3 и -13,3:
Trunc = 13
SignBit = 0
Floor = 13
13 + 0 = 13

Trunc = -13
SignBit = 1
Floor = -14
-(13 + 1) = -14
(или -13 - 1 = -14)

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


PS1.
А на остальные операции реализация данной операциивлиять не должна.

PS2.
По поводу эквивалентности, я немного соврал. Однако, из школьного курса математики помню, что если из одного можно вывести другое и наоборот, то эти две штуки эквивалентны. Другое дело, что в данном конкретном случае эти штуки не полноценные Trunc и Floor.

valexey комментирует...

Кстати, в (e)glibc для arm можно выставлять только один режим, режим округления (round) никаких floor, trunc там нет.

Я пока не знаю то ли это у разработчиков eglibc руки кривые, то ли арм этого не может. Вообще arm имеет модульную архитектуру и там может быть до 15ти сопроцессоров. И есть как минимум штуки три типа сопроцессоров которые что-то там умеют с плавающей точкой (по моему, чистый и не порочный arm плавающую точку не умеет вообще). В общем дело темное, но факт есть факт, в eglibc, т.е. считайте в линухе под армом, под рукой будет только операция округления.