Pull to refresh

Comments 66

UFO landed and left these words here
Рейтрейсер напишите без тригонометрии, это веселее :-) Основы те же самые :-)
В рейтрейсере тригонометрия будет необходима при вычислении координат текстуры для сферы, цилиндра,…
UFO landed and left these words here
Не знаком со способом трассирования лучей? Какие ещё треугольники в сфере?
Зачем это мне? Я прекрасно знаю про этот метод, т.к. писал его ещё в 1999 году
Извините, промахнулся. Это для Horse, с трИугольниками в сфере. :)
любой учебник аналитической геометрии вам все расскажет о пространствах, матрицах и их геометрическом смысле.
Тригонометрия часто нужна тем кто пишет игры и различные редакторы для окон мебели и прочее а всем остальным она скорее всего и не нужна…
Сеошникам и создателям дейтинг-стартапов точно не нужна!
На чём основывается утверждение, что sin(0.3) считается медленее, чем 1.2/0.33? И то и то FPU.
Синусы считаются с помощью разложения в ряд, так что FPU придется произвести деление много раз, прежде чем получится результат. Сомневаюсь, что в современных FPU используются тригонометрические таблицы. Или все же используются?
П.С. По опыту олимпиад очень хорошо знаю, что решения на векторной алгебре практически всегда быстрее.
Ну вы просто заставляете меня сделать тесты самому.

1.c:

#include <stdio.h>
#include <math.h>
void main(){
double a;
double b;
for(a=0;a<1000000000;a++){
        b=sin(a);
}
}


time ./a.out

real 0m1.412s
user 0m1.400s
sys 0m0.012s

2.c
#include <stdio.h>
#include <math.h>
void main(){
double a;
double b;
for(a=0;a<1000000000;a++){
        b=a/0.3;
}
}


time ./a.out

real 0m1.413s
user 0m1.408s
sys 0m0.004s

Итого — синус и деление выполняются за строго ОДИНАКОВОЕ время.
кэш процессора активно работает здесь.
как мне кажется — точнее было бы использовать разные коэфициенты, дабы исключить особенности процессоров
При чём тут кеш? О чём вы? Это строго одинаковый код, в котором в одном случае выполняется инструкция fdiv, а во втором fsin. Какие особенности каких процессоров?

Если вы хотите предложить свой метод сравнить скорость деления и вычисления sin на современных FPU, приводите.
>>> def sinus():
… last = time.clock()
… for i in xrange(1000000):
… x = math.sin(i)
… return time.clock() — last

>>> print sinus()
0.436118277602

>>> def delit():
… last = time.clock()
… for i in xrange(1000000):
… x = i/0.3
… return time.clock() — last

>>> print delit()
0.15221040663

В питонах деление быстрее

Это всего лишь означает, что в питоне хреновая работа с float стилем. В gсс sin и / для double просто разворачивается в ассемблерную инструкцию. Что происходит в питоне — одному богу известно, а на скорость выполнения программы может влиять, например, смена [] на функцию map и т.д.

Вот ассемблерный код для 1.c (синус):
в идеале должно разворачиваться в машинные коды, а не в ассемблерную инструкцию.
Упс, вчитался в ассемблер. Был неправ, гцц просто сожрало ненужную инструкцию.
Вы не учитываете:
а) оптимизацию компилятора, который может отсекать некоторые ветви кода, когда видит, что результат нигде не используется;
б) то что у вас результат накапливается в переменной b, которая быстро стремится к нулю. Функция sin(x) обрабатывает ноль как особый случай.
Попробуйте потестировать следующие примеры:
#include <stdio.h>
#include <math.h>

void main(){
	int a;
	double b = 1;
	for(a=0;a<50000000;a++){
		if(a&1) {
			b = sin(b);
		}
		else {
			b = sin(1-b);
		}
	}
	printf("%lf\n", b);
}


#include <stdio.h>
#include <math.h>

void main(){
	int a;
	double b = 1;
	for(a=0;a<50000000;a++){
		if(a&1) {
			b = b/0.3;
		}
		else {
			b = 0.3/b;
		}
	}
	printf("%lf\n", b);
}
real 0m1.534s
user 0m1.520s
sys 0m0.016s

real 0m0.306s
user 0m0.308s
sys 0m0.000s

Да, ок, убедили, был неправ.
кстати, причина даже не в fdiv, а в том, что при делении gcc юзает mmx во все поля:

.L9:
        addl    $1, %eax
        divsd   %xmm1, %xmm0
        cmpl    $50000000, %eax
        je      .L8
.L4:
        testb   $1, %al
        jne     .L9
        movapd  %xmm1, %xmm2
        addl    $1, %eax
        cmpl    $50000000, %eax
        divsd   %xmm0, %xmm2
        movapd  %xmm2, %xmm0
        jne     .L4
.L8:
        movl    $.LC2, %edi
        movl    $1, %eax
        jmp     printf


сравнить с sin-версией, у которой таки call sin.

.L4:
        testb   $1, %bl
        jne     .L7
        movsd   .LC0(%rip), %xmm1
        subsd   %xmm0, %xmm1
        movapd  %xmm1, %xmm0
.L7:
        addl    $1, %ebx
        call    sin
        cmpl    $50000000, %ebx
        jne     .L4
        popq    %rbx
        movl    $.LC1, %edi
        movl    $1, %eax
        jmp     printf
        .cfi_endproc
добавь -ffast-math -m32 — получишь fsin и никаких xmm, а всё равно синус медленнее.
Надо все же понимать как оптимизируют компиляторы, прежде чем приводить такие тесты.
И зачем double? Если float быстрее и часто достаточен.
А-а-а! Хочу такой же процессор, как у Вас, чтобы миллиард синусов вычислял за 1 секунду! :))
А то мой Core i7 сто миллионов итераций секунд 5 крутит!

Если серьезно, боюсь, Ваш тест неправилен. Похоже, компилятор выкинул неиспользуемые вычисления в обоих случаях. На самом деле, тест с синусом работает в 6-7 раз медленнее, чем с делением.
а вы уверены, что Ваши программы вообще работают?
в этих программах вычисляемое значение «b» в конечном итоге нигде не используется. Компилятор вполне мог скомпилировать программу без цикла вообще.

сделайте хотя бы вот так:

#include <stdio.h>
#include <math.h>
void main(){
double a;
double b=0;
for(a=0;a<1000000000;a++){
b=b+a/0.3;
}
printf("%f\n",b);
}

Предполагать, что либо подобное заранее не имеет смысла. Оптимизировать нужно только тогда, когда профайлер Вам показал, что sin есть узкое место. Вы не можете знать как преобразует Ваш код компилятор, а следовательно и делать заявления, что этот код отработает быстрее, чем вот этот.
Это справедливо только тогда, когда написание более эффективного алгоритма требует больше усилий от программиста или же больший обьем кода. Если вы выбираете между двумя алгоритмами с одинаковой сложностью реализации — почему бы не реализовать тот, который, очевидно, будет работать быстрее. Кроме того, существует целый класс вычислительных задач, в которых сразу и без профайлера видно узкие места.
Статья не о низкоуровневой оптимизации, а о грамотном выборе алгоритмов. Из вас получится очень плохой архитектор.
Ну следующий шаг развития — целочисленные алгоритмы построения графики. Очень советую двинуться в этом направлении. Обещаю — вам понравится. Успехов! Отличная статья!
Почему-то был уверен что в статье будет задача — определить выпуклость многоугольника. Простая задача, решив которую каждый поймет профит от использования векторов.
Для каждой вершины многоугольника компонента Z векторного произведения векторов выходящих из этой вершины в две соседние имеет один и тот же знак.
Да, векторное произведение векторов — тоже очень нужная штука, просто я не хотел перегружать статью :-)
Забыл добавить: следует выбрать направление обхода вершин, и векторное произведение всегда брать в одном порядке, например вектор смотрящий против направления обхода умножать на вектор смотрящий по направлению.
Хорошая статья, но мне кажется, что программисты должны одинаково владеть обеими подходами,
и выбирать их в зависимости от требований задач. Бывают классы задач, которые удобно решать в полярных или сферических координатах, например.
Спасибо!

Еще по теме: некто Винни пишет о том же самом: что вместо сложных вычислений можно использовать простые и быстрые.
Угол между двумя векторами: users.livejournal.com/_winnie/237714.html
Пересечение двух отрезков: users.livejournal.com/_winnie/152327.html#cutid1
Спасибо за статью :) В последнее время веб-программирование утомляет и превращается в рутину, решил для разнообразия сделать игру в свободное время. И столкнулся с тем, что позабыл большую часть геометрии и алгебры :(

Кто-нибудь может посоветовать книги, статьи, сайты по алогоритмам в играх и 2D графике? В 3D пока не лезу, делаю 2D, но в целом хочется и красивых частиц туда добавить и другие интересные фишки типа теней, света и т.д.
С помощью основного тригонометрического тождества вы сможете однозначно определить синус по косинусу и наоборот лишь в некоторых случаях, когда нам, например, известно, что угол от -pi/2 до pi/2. В общем случае вы не сможете определить знак другой функции…

Для быстрого вычисления синуса и косинуса используется (и я использую) тангенс половинного угла, через который синус и косинус вычисляются с помощью обычных арифметических операций.
Да, вы правы. Результат вращения разный получится. Уберу про тождество.
А с тангенсом надо аккуратно — он в бесконечность может уйти, если поворачивать на 180°.
Эх, объясняли бы в школе и университете векторы подобным же образом. А то ведь, помню, зачем это нужно и где может применяться никто не удосуживался прояснить. В результате народ что-то зазубривал, сдавал, и благополучно забывал.
у нас в универе тут же был курс «ком. графики» где все эти матрицы и повороты показывали на примерах.
у нас был просто курс «высшей математики». правда, факультет экономический, и потому часть задач имела отношение к бизнесу, но вот векторы прошли чем-то совершенно оторванным от реальности. пост сейчас прочла с большим интересом.
И объясняют. Естественно, не на экономических факультетах.
Почему же «естественно»?
В хорошем учебном заведении любую излагаемую теорию должны иллюстрировать практикой. Если вам с учебным заведением/преподавателем повезло, я могу за вас лишь порадоваться.
Потому что это выходит за рамки курса линейной алгебры. Линейная алгебра это чистая теория, которая применима в очень многих областях. Одна из этих областей — компьютерная графика, по которой есть отдельный курс. И вполне логично, что его не читают экономистам.
Статистики под рукой нет, но большинство людей, насколько мне известно, плохо воспринимают «чистую теорию». Наверняка и у вас были одноклассники, например, возмущавшиеся, что им необходимо изучать физику/химию/биологию, если им при поступлении в ВУЗ экзамены по этим предметам все равно сдавать не придется. Предположить как им могут пригодиться полученные знания в реальной жизни они не могли. Между тем, если бы преподаватель химии взяла бутылку «Спрайта» и вместе с учениками «расшифровала» состав, а преподаватель биологии обсудила преимущества подсолнечного масла с рекламным слоганом «не содержит холестерина», глядишь, мотивация была бы выше.
Простите, а насколько часто экономистам приходится писать программы для рисования стрелочек? И почему вы считаете, что пример использования линейной алгебры должен быть именно в рамках компьютерной графики? Вы знаете, что курс линейной алгебры читается всем техническим специалистам? И разные специалисты в будущем могут применять её в разных областях. Так что, примеры во всех возможных областях приводить? И сколько тогда будет занимать курс?
А с чего вы решили, что я просила примеры программ для рисования стрелочек или в рамках компьютерной графики? Наоборот, если уж преподаете линейную алгебру экономистам, будьте добры, поясните, где и как они ее смогут применять. Но наглядных примеров не было вообще, ни из какой области. Хотя, скажем, у преподавателя теории вероятностей с этим проблем не было, несмотря на то что вел курс у самых разных факультетов.
Ну если вопрос стоит таким образом… С теорией вероятности как-то проще. А где применять линейную алгебру экономистам я, например, придумать не могу.
Увы, далеко не всегда и не везде возможно отказаться от синусов и косинусов… Когда нужно быстро молотить косинусы и синусы в цикле — использую только таблицы до сих пор, ибо как заметили выше, fsin и fcos — тормозные операции даже на современных CPU.
Вот кстати набросал пример небольшой — вращающийся тор. Вряд-ли можно вращать точки не через чинус-косинус: Пример 3D Tor
С помощью матриц вращения — легко. Конечно, зависит от того, как вы задаёте траекторию, но в любом случае вам нужно не больше одного синуса и одного косинуса на каждый кадр, а это уже нестрашно.

Lookup tables — это тоже очень хорошо.
Как один из тех программистов который любит использовать тригонометрию:) Автору спасибо за статью, пойду векторную алгебру вспоминать:)
Я бы посоветовал аналитическую геометрию, а не векторную алгебру. Во всяком случае нас учили решать задачки по геометрии и тригонометрии векторами именно там, а на алгебре были совсем другие материи, не смотря на то, что одно тесно связанно с другим.
Ох, прям в тему пришлось, сейчас увлекся анаморфной живописью. Воспользовался предложением использовать векторы вместо тригонометрии — преобразования вышли более наглядны, а программа на их основе работает несколько быстрее своего аналога.
а угол вектора (0,0) -> (x,y) можно как-то вычислить не прибегая к atan2?
Главный вопрос — не можно ли, а нужно ли. Как правило, в большинстве случаев не нужно. Если вам кажется, что нужно, возможно, вы что-то не учли.
Only those users with full accounts are able to leave comments. Log in, please.