How to become an author
Search
Write a publication
Pull to refresh

Comments 67

UFO just landed and posted this here
Рейтрейсер напишите без тригонометрии, это веселее :-) Основы те же самые :-)
Total votes 4: ↑4 and ↓0+4
В рейтрейсере тригонометрия будет необходима при вычислении координат текстуры для сферы, цилиндра,…
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Не знаком со способом трассирования лучей? Какие ещё треугольники в сфере?
Total votes 4: ↑3 and ↓1+2
Зачем это мне? Я прекрасно знаю про этот метод, т.к. писал его ещё в 1999 году
This comment wasn’t rated yet0
Извините, промахнулся. Это для Horse, с трИугольниками в сфере. :)
Total votes 1: ↑1 and ↓0+1
любой учебник аналитической геометрии вам все расскажет о пространствах, матрицах и их геометрическом смысле.
Total votes 1: ↑1 and ↓0+1
Тригонометрия часто нужна тем кто пишет игры и различные редакторы для окон мебели и прочее а всем остальным она скорее всего и не нужна…
This comment wasn’t rated yet0
а графические редакторы и ГИС?
This comment wasn’t rated yet0
Сеошникам и создателям дейтинг-стартапов точно не нужна!
Total votes 3: ↑2 and ↓1+1
На чём основывается утверждение, что sin(0.3) считается медленее, чем 1.2/0.33? И то и то FPU.
Total votes 14: ↑7 and ↓70
Синусы считаются с помощью разложения в ряд, так что FPU придется произвести деление много раз, прежде чем получится результат. Сомневаюсь, что в современных FPU используются тригонометрические таблицы. Или все же используются?
П.С. По опыту олимпиад очень хорошо знаю, что решения на векторной алгебре практически всегда быстрее.
Total votes 16: ↑12 and ↓4+8
Ну вы просто заставляете меня сделать тесты самому.

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

Итого — синус и деление выполняются за строго ОДИНАКОВОЕ время.
Total votes 21: ↑10 and ↓11-1
кэш процессора активно работает здесь.
как мне кажется — точнее было бы использовать разные коэфициенты, дабы исключить особенности процессоров
Total votes 12: ↑8 and ↓4+4
При чём тут кеш? О чём вы? Это строго одинаковый код, в котором в одном случае выполняется инструкция fdiv, а во втором fsin. Какие особенности каких процессоров?

Если вы хотите предложить свой метод сравнить скорость деления и вычисления sin на современных FPU, приводите.
Total votes 18: ↑7 and ↓11-4
>>> 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

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

Total votes 5: ↑4 and ↓1+3
Это всего лишь означает, что в питоне хреновая работа с float стилем. В gсс sin и / для double просто разворачивается в ассемблерную инструкцию. Что происходит в питоне — одному богу известно, а на скорость выполнения программы может влиять, например, смена [] на функцию map и т.д.

Вот ассемблерный код для 1.c (синус):
Total votes 13: ↑6 and ↓7-1
в идеале должно разворачиваться в машинные коды, а не в ассемблерную инструкцию.
Total votes 4: ↑0 and ↓4-4
Упс, вчитался в ассемблер. Был неправ, гцц просто сожрало ненужную инструкцию.
Total votes 7: ↑5 and ↓2+3
Вы не учитываете:
а) оптимизацию компилятора, который может отсекать некоторые ветви кода, когда видит, что результат нигде не используется;
б) то что у вас результат накапливается в переменной 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);
}
Total votes 18: ↑18 and ↓0+18
real 0m1.534s
user 0m1.520s
sys 0m0.016s

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

Да, ок, убедили, был неправ.
Total votes 16: ↑13 and ↓3+10
кстати, причина даже не в 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
Total votes 8: ↑4 and ↓40
добавь -ffast-math -m32 — получишь fsin и никаких xmm, а всё равно синус медленнее.
Total votes 2: ↑2 and ↓0+2
Надо все же понимать как оптимизируют компиляторы, прежде чем приводить такие тесты.
И зачем double? Если float быстрее и часто достаточен.
Total votes 5: ↑4 and ↓1+3
А-а-а! Хочу такой же процессор, как у Вас, чтобы миллиард синусов вычислял за 1 секунду! :))
А то мой Core i7 сто миллионов итераций секунд 5 крутит!

Если серьезно, боюсь, Ваш тест неправилен. Похоже, компилятор выкинул неиспользуемые вычисления в обоих случаях. На самом деле, тест с синусом работает в 6-7 раз медленнее, чем с делением.
Total votes 4: ↑4 and ↓0+4
а вы уверены, что Ваши программы вообще работают?
в этих программах вычисляемое значение «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);
}

Total votes 2: ↑1 and ↓10
Предполагать, что либо подобное заранее не имеет смысла. Оптимизировать нужно только тогда, когда профайлер Вам показал, что sin есть узкое место. Вы не можете знать как преобразует Ваш код компилятор, а следовательно и делать заявления, что этот код отработает быстрее, чем вот этот.
Total votes 2: ↑1 and ↓10
Это справедливо только тогда, когда написание более эффективного алгоритма требует больше усилий от программиста или же больший обьем кода. Если вы выбираете между двумя алгоритмами с одинаковой сложностью реализации — почему бы не реализовать тот, который, очевидно, будет работать быстрее. Кроме того, существует целый класс вычислительных задач, в которых сразу и без профайлера видно узкие места.
This comment wasn’t rated yet0
Статья не о низкоуровневой оптимизации, а о грамотном выборе алгоритмов. Из вас получится очень плохой архитектор.
Total votes 1: ↑1 and ↓0+1
Ну следующий шаг развития — целочисленные алгоритмы построения графики. Очень советую двинуться в этом направлении. Обещаю — вам понравится. Успехов! Отличная статья!
Total votes 7: ↑5 and ↓2+3
Почему-то был уверен что в статье будет задача — определить выпуклость многоугольника. Простая задача, решив которую каждый поймет профит от использования векторов.
Total votes 1: ↑1 and ↓0+1
напомните решение?
This comment wasn’t rated yet0
Для каждой вершины многоугольника компонента Z векторного произведения векторов выходящих из этой вершины в две соседние имеет один и тот же знак.
Total votes 1: ↑1 and ↓0+1
Да, векторное произведение векторов — тоже очень нужная штука, просто я не хотел перегружать статью :-)
This comment wasn’t rated yet0
Забыл добавить: следует выбрать направление обхода вершин, и векторное произведение всегда брать в одном порядке, например вектор смотрящий против направления обхода умножать на вектор смотрящий по направлению.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Хорошая статья, но мне кажется, что программисты должны одинаково владеть обеими подходами,
и выбирать их в зависимости от требований задач. Бывают классы задач, которые удобно решать в полярных или сферических координатах, например.
This comment wasn’t rated yet0
Спасибо за статью :) В последнее время веб-программирование утомляет и превращается в рутину, решил для разнообразия сделать игру в свободное время. И столкнулся с тем, что позабыл большую часть геометрии и алгебры :(

Кто-нибудь может посоветовать книги, статьи, сайты по алогоритмам в играх и 2D графике? В 3D пока не лезу, делаю 2D, но в целом хочется и красивых частиц туда добавить и другие интересные фишки типа теней, света и т.д.
Total votes 2: ↑2 and ↓0+2
404 страницы не существует
This comment wasn’t rated yet0
С помощью основного тригонометрического тождества вы сможете однозначно определить синус по косинусу и наоборот лишь в некоторых случаях, когда нам, например, известно, что угол от -pi/2 до pi/2. В общем случае вы не сможете определить знак другой функции…

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

Lookup tables — это тоже очень хорошо.
Total votes 2: ↑2 and ↓0+2
Как один из тех программистов который любит использовать тригонометрию:) Автору спасибо за статью, пойду векторную алгебру вспоминать:)
Total votes 1: ↑1 and ↓0+1
Я бы посоветовал аналитическую геометрию, а не векторную алгебру. Во всяком случае нас учили решать задачки по геометрии и тригонометрии векторами именно там, а на алгебре были совсем другие материи, не смотря на то, что одно тесно связанно с другим.
This comment wasn’t rated yet0
Спасибо за совет.
This comment wasn’t rated yet0
Ох, прям в тему пришлось, сейчас увлекся анаморфной живописью. Воспользовался предложением использовать векторы вместо тригонометрии — преобразования вышли более наглядны, а программа на их основе работает несколько быстрее своего аналога.
This comment wasn’t rated yet0
а угол вектора (0,0) -> (x,y) можно как-то вычислить не прибегая к atan2?
This comment wasn’t rated yet0
Главный вопрос — не можно ли, а нужно ли. Как правило, в большинстве случаев не нужно. Если вам кажется, что нужно, возможно, вы что-то не учли.
This comment wasn’t rated yet0
Можно обойтись не только без геометрии, но и без векторов, матриц, скалярных с векторными умножениями и всего такого — просто используя комплексные числа. Вот, например, так рисуется стрелка
в Mathematica


Значение для поворота (и масштабирования при необходимости) r тоже можно задать константно (например, как 1+i) или получить его в результате операций над другими комплексными числами.

Отражённый луч ещё проще считается: a*сonjugate(b/a) (где a это отражающий вектор и неважно, в какую именно сторону он направлен), и не менее легко это всё алгебраически упрощается при цепочке преобразований.
Total votes 1: ↑1 and ↓0+1
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr