Войти
ФлеймФорумПрограммирование

Буст pow2 (2 стр)

Страницы: 1 2 3 Следующая »
#15
14:54, 5 мар. 2018

FordPerfect
> Я думал, что в ядре одна делилка
Подозреваю что деление сделано микрокодом через умножение/сложение


#16
14:55, 5 мар. 2018

FordPerfect
> LUT[delta and $7F]
Точнее да, про скорость хз

#17
14:57, 5 мар. 2018

FordPerfect
> Хочется написать аппроксимацию pow2 (в стандарте C известной как exp2f).
Уточни условия. Какая нужна точность, какой диапазон применения, поддерживаются ли +-0, +-inf, NaN?
Просто какую-то сферическую функцию в вакууме писать не стоит, т. к. она уже есть в стандартной библиотеке.

#18
15:03, 5 мар. 2018

Поскреб по сусекам и откопал одну версию, но она работает хуже std::exp2:

+ код

Древний компьютер и K=10000:
g++ -Ofast -mtune=native
Function      |         Tacts/call|   Max. rel. error
--------------+-------------------+------------------
movss         |                3.0|                 -
divss         |                5.0|                 -
std::exp2     |               14.0|                 0
pow2_try1     |                3.7|            0.0615
pow2_try2     |                7.1|            0.0054
pow2_try3     |                7.1|            0.0054
pow2_try4     |               14.1|           0.00019
pow2_asm      |                6.3|            0.0054
g++ -O3 -mtune=native
Function      |         Tacts/call|   Max. rel. error
--------------+-------------------+------------------
movss         |                3.0|                 -
divss         |                5.0|                 -
std::exp2     |               40.0|                 0
pow2_try1     |                3.7|            0.0615
pow2_try2     |                7.5|            0.0054
pow2_try3     |                7.1|            0.0054
pow2_try4     |               14.1|           0.00019
pow2_asm      |                6.3|            0.0054

FordPerfect
> Возможно -O3 включает ffast-math и автовекторизацию.
Автовекторизацию, кажется, да, а вот -ffast-math — нет, надо использовать -Ofast.

CD
> Подозреваю что деление сделано микрокодом через умножение/сложение
Тоже склоняюсь к этому.

#19
15:25, 5 мар. 2018

1 frag / 2 deaths
А можешь замерить? Мне интересно, в контексте твоего рендера. В синтетике, небось, фаза луны другая будет.

CD
> Подозреваю что деление сделано микрокодом через умножение/сложение
Мой вопрос о том, может ли одновременно выполняться более одного деления?

Panzerschrek[CN]
Так вроде в #0 написано.
На +-inf, NaN забить.
С +-0 проблем вроде нет.
Диапазон |x|<50. За пределами - можно выдавать любую фигню.

Задачка так пришла в голову, без прямой цели.
Но контекст, в котором пришла - нужна почти любая непрерывная функция, которая уводила бы выражение в 0 при x->inf. Ну например для potential field. Можно exp(-r^2), можно 1/(1+x^2).
Соответственно - хочется быстрее деления.
Ну и деление всё-таки медленнее убывает, чем хочется.

Соответственно - точность достаточно единиц процентов, можно хуже.

}:+()___ [Smile]
Спасибо.
Это он std::exp2 распараллелил что-ли? Или переключился на другую реализацию?

#20
(Правка: 15:34) 15:33, 5 мар. 2018

FordPerfect
> А можешь замерить? Мне интересно, в контексте твоего рендера.
В контексте рендера текущей точности хватает. Экпоненту я ввёл не потому что эстет дофига, а потому что очень надо, чтобы ТУМАН(цвет, а+б) равнялось ТУМАН(ТУМАН(цвет, а), б), в случае неравенства будет заметен резкий переход в таких местах
screen | Буст pow2
(а и б - это толщина двух стенок тумана, которые пересекает правый "луч зрения", а+б это толщина одной стенки тумана, пересекаемой левым "лучом")

с такой експонентой переход незаметен

#21
16:01, 5 мар. 2018

FordPerfect
> Соответственно - точность достаточно единиц процентов, можно хуже.
На мой взгляд, в этом случае, на точность можно, вообще, забить, а вот требование гладкости — добавить.

> Это он std::exp2 распараллелил что-ли? Или переключился на другую реализацию?
Cудя по профайлеру, при -ffast-math std::exp2 вызывает __exp2f_finite, а на -O3 вызывает __exp2f, которая внутри вызывает __exp2f_finite, а потом делает пачку проверок.

#22
17:07, 5 мар. 2018

}:+()___ [Smile]
> На мой взгляд, в этом случае, на точность можно, вообще, забить, а вот требование гладкости — добавить.
Согласен. Собственно, этим параметром мне и не нравится кусочно-линейная pow2_try1.

#23
4:38, 6 мар. 2018

Точность ладно, но асимптотика убывания exp мне нравится.

К слову, исторически мантиссой называли дробную часть логарифма числа (в смысле - логарифм того, что называют сейчас).
См. https://en.wikipedia.org/wiki/Mantissa . Забавно. Т. е. термин подразумевает логарифмическую запись, а не полулогарифмическую, как в IEEE754.

}:+()___ [Smile]
> требование гладкости
Требования f(0)=1; f(1)=2; f'(1)=2*f'(0) определяют многочлен 2-й степени однозначно: 1+(2/3)*x+(1/3)*x^2.
Кстати, ошибка <0.35%.

#24
6:25, 6 мар. 2018

Очевидный код:

static inline float pow2_try5(float x)
{
    x=x+127.0f;
    int32_t n=int32_t(x);
    x=x-float(n);
    x=1.0f+0.33333333f*x*(2.0f+x);
    return bits2float(uint32_t(n)<<23)*x;
}
Но скорость хотелось бы улучшить. float->int->float быстрые, но не бесплатные.

Чуть менее очевидный код по ссылке:
http://rextester.com/RVIUE7368

Идеи приветствуются.
Замеры можно постить сюда тоже.

На всякий случай, если кому интересно попробовать, смысл выражений:
Пусть наш аргумент - число x. Обозначим [cht]n=\lfloor \log_2 x \rfloor[/cht], [cht]t=x-\lfloor x \rfloor[/cht], bits1=float2bits(x+639.0f)<<9, bits2=float2bits(x+383.0f)<<8.
Тогда:
bits2float(bits1) = [cht] 2^n \cdot (1+t)[/cht]
bits2float(bits2) = [cht] - 2^n \cdot (1+t)[/cht] (точнее на один бит сигнификанда)
bits2float(bits&0x7F800000u) = [cht]2^n[/cht] (bits1 или bits2)
bits2float((bits&0x007FFFFFu)|0x3F800000u) = [cht]1+t[/cht] (bits1 или bits2)
bits2float(bits1^0x007FFFFFu) = [cht]2^n \cdot (2-t)[/cht]
bits2float(bits2^0x007FFFFFu) = [cht]-2^n \cdot (2-t)[/cht]
bits2float(~bits1) = [cht]-2^{-n-1} \cdot (2-t)[/cht]
bits2float(~bits2) = [cht]2^{-n-1} \cdot (2-t)[/cht]

#25
(Правка: 6:55) 6:53, 6 мар. 2018

FordPerfect
> Очень быстрое деление?

На вещественных давно же уже деление делали как вычисление 1/x, а потом умножение на него. Там и команда такая была где-то то ли в ФПУ, то ли в ССЕ - 1/x.
Поэтому сложилась забавная ситуация - вещественные деления стали работать заметно быстрее целочисленных.

#26
10:56, 6 мар. 2018

mix2pix
> ССЕ - 1/x.
А как он 1/x так быстро берёт?

#27
11:16, 6 мар. 2018

В SSE есть приблизительный 1/x - rcpss/rcpps (отн. ошибка <= 1.5*2-12).
Как реализовано внутри деление - хз (по-разному, видимо). Но если делать через y*(1/x), то промежуточная точность видимо заметно повыше, чем у результата.

См. напр. Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessor:
https://pdfs.semanticscholar.org/c85c/30159f9af9b814b20bbac175326a52e4f272.pdf .

#28
11:25, 6 мар. 2018

> забавная ситуация - вещественные деления стали работать заметно быстрее целочисленных
Вроде обычно деление 64:32 делается той же железкой, что и FPU деление (80 бит). Тупо логистика разная, из-за чего вещественное несколько быстрее. А беззнаковое - медленнее знакового.
Делению float32 нужно выполнять меньше работы. Целочисленному меньшего размера - мне интересно.

> https://pdfs.semanticscholar.org/c85c/30159f9af9b814b20bbac175326a52e4f272.pdf
Здесь да - берут приблизительный rcp и дорабатывают напильником. Алгоритм близкий для деления и корня.

#29
14:30, 6 мар. 2018

FordPerfect
> Чуть менее очевидный код по ссылке:
Результаты с нормального компьютера:

+ результаты

Надо макросы заменить на noinline функции, а то в ассемблерном коде мешанина, разобрать какой вариант где невозможно.

1 frag / 2 deaths
> А как он 1/x так быстро берёт?
Таблица в микрокоде + итерации Ньютоном.

Страницы: 1 2 3 Следующая »
ФлеймФорумПрограммирование