1 | |
Максимально быстрый вариант вычисления sinf/cosf27.07.2014, 00:48. Показов 5165. Ответов 17
Метки нет (Все метки)
Вопрос, возможно, не в ту ветку форума, но решение предполагается на с++, поэтому просьба расшифровать задание.
Текст такой: Напишите пред-расчетный (максимальность быстрый) вариант вычисления sinf/cosf по таблице с точностью до сотых. Вопрос - что нужно сделать?! А то я не понял.
0
|
27.07.2014, 00:48 | |
Ответы с готовыми решениями:
17
Более быстрый вариант сравнения фотографий Запрос данных с экрана максимально быстрый Быстрый поиск максимально похожего слова Максимально бюджетный вариант стримерского игрового ПК |
761 / 268 / 57
Регистрация: 13.12.2009
Сообщений: 1,101
|
||||||
27.07.2014, 05:38 | 2 | |||||
Sin он и в Африке Sin;
1
|
What a waste!
1607 / 1299 / 180
Регистрация: 21.04.2012
Сообщений: 2,727
|
||||||
27.07.2014, 07:50 | 3 | |||||
Думаю что-то вроде этого (об оптимальности не говорю):
Кликните здесь для просмотра всего текста
1
|
Заблокирован
|
|
27.07.2014, 07:58 | 4 |
А в чём прикол то ? Функция sinf не устраивает? Её ж тоже не дураки писали
Не думаю что даже на уровне ассемблера под Intel можно что - то улучшить .... Добавлено через 1 минуту Да и вообще ТС юзает шарп или по крайней мере CLR, что к данному трею никакого отношения не имеет
0
|
761 / 268 / 57
Регистрация: 13.12.2009
Сообщений: 1,101
|
|
27.07.2014, 08:33 | 5 |
нужно подставить функцию sinf и проверить результат. В чем трудность не пойму???
0
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
27.07.2014, 11:42 | 6 | |||||
1
|
27.07.2014, 13:54 | 7 |
Сообщение было отмечено Robesper3411 как решение
Решение
Я не сильно разбираюсь в алгоритмах, но, думается, смысл задания следующий. Синус и косинус вычисляется через разложение в ряд или что-то типа того. Реализацию в glibc можно посмотреть
https://sourceware.org/git/?p=... .c;hb=HEAD https://sourceware.org/git/?p=... .c;hb=HEAD функция sin является как бы обёрткой, которая произвольное значение аргумента сводит к диапазону [0, pi/4] (и отсекает кривые случаи), а функция ksinf уже вычисляет синус для аргумента [0, pi/4]. Внутри ksinf'а есть вычисление ряда. Думается, если из формулы выкинуть хвост, то результат получится менее точный, но зато более быстро вычисляемый Добавлено через 47 секунд Тьфу блин, не заметил про таблицу Добавлено через 3 минуты Вот есть таблица синусов http://www.webmath.ru/poleznoe/table_sinus.php статически заполняешь этими значениями массив данных. Затем, на пальцах, если тебе нужно вычислить синус от нуля градусов, то возвращаешь нулевой элемент таблицы, если синус одного градуса - первый элемент таблицы и т.п. Если нужно вычислить синус от 1.6 градуса, то вычисляешь значение, предполагая, что между 1 и 2 градусами имеем линейную зависимость. При таком раскладе как раз попадёшь в требуемую точность. Ну и надо учесть, что тебе аргумент будет в радианах передаваться, а не в градусах Добавлено через 6 минут "Стандартный" синус вычисляет с точностью до 7 или 8 знака (в десятичной системе) и работает порядка сотен машинных тактов. Для каких-нибудь систем, работающих в реальном времени (например, обрабатывающих данные с локатора или 3d-игрушек) это слишком жирно. Вместо этого можно получить менее точное значение (ибо в определённых классах задач вполне хватает и с точностью до сотых), но в несколько раз быстрее. Для этого и используют таблицы, где все значения заранее вычислены
2
|
1485 / 1412 / 240
Регистрация: 19.02.2010
Сообщений: 3,913
|
|
27.07.2014, 21:40 | 8 |
На всех процах х86-платформы, начиная собственно с родителя (вернее, с сопроцессора 8087), вычисляются отдельными процессорными командами. Если внутри соотв. мат.функций библиотеки какого-то компилятора лежит разложение в ряд - то это, похоже, диагноз для тех прогеров.
Начиная с ПняПро или Пня2 - есть и команда fsincos, вычисляющая для одного значения сразу 2 названных функции, что экономит время вдвое (для тех программ, где нужны сразу оба значения функций для одного и того же аргумента).
0
|
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
27.07.2014, 21:58 | 9 |
Команды-то не магические, и методы их работы всё те же (да ещё и с ограничениями - большую таблицу в процессор не зашьёшь), а вот точность не задаётся, да и не векторизуются они...
0
|
1485 / 1412 / 240
Регистрация: 19.02.2010
Сообщений: 3,913
|
|
27.07.2014, 22:00 | 10 |
0
|
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
27.07.2014, 22:30 | 11 |
Так при умеренном использовании таблиц вычисления всё равно остаются. А если таблицу сделать большую и плотную или если точность нужна небольшая, так тогда даже вопросов не должно быть по производительности.
0
|
28.07.2014, 05:53 | 13 |
Robesper3411, так это не к нам вопрос Но если я правильно понимаю логику таких задач, таблица у вас уже есть/кем-то задана (списана с какой-нибудь книжки 50-х). Для промежуточных значений - интерполяция, можно хоть линейную.
0
|
28.07.2014, 11:17 | 14 |
Сообщение было отмечено Robesper3411 как решение
Решение
Чисто на всякий случай. Если программа короткая, то она совсем необязательно работает быстро. Программа из одной аппаратной операции fsin будет работать 200 тактов, а не 1, как может показаться на первый взгляд. Что явно медленнее, чем вычисление короткого ряда
Здесь нужно вычислять синус и косинус. Но сделать это быстро. Т.е. быстрее, чем стандартная реализация в библиотеке. А быстрее она должна работать за счёт того, что будет работать с меньшей точностью. Как уже писалось, один из вариантов быстрых вычислений - это вычислить заранее значения синусов в N точках (например, создать таблицу синусов для углов 0, 1, 2, ... 90 градусов). Затем при вызове синуса, например, от 37.3 градуса, взять из таблицы готовое заранее вычисленное значение для 37 градусов. Оно будет не очень точным, зато быстро
0
|
1485 / 1412 / 240
Регистрация: 19.02.2010
Сообщений: 3,913
|
|
03.08.2014, 21:44 | 15 |
Лезем в оффтопик (для сишного раздела форума) - ну да ладно.
Не 200 - а порядка 100 (если не брать огрызки типа Атомов). В общем, у Агнера Фога в мануале по проц.командам хорошо расписаны растактовки для кучи процессоров. Во вторых - я и не утверждал, что короткая прога всегда будет более быстрой. Просто при таблицах - будет как минимум одно деление (тоже времязатратная команда), и если этап с делениями ещё и можно будет векторизовать - то потом по таблице всё равно для каждого индекса придётся бегать по-отдельности (тут могу и ошибаться - может, где-нить в SSE4 и есть нужная команда, но в таком случае рискуем потерять портируемость на вполне ещё пригодные для работы компутеры с процами на пару поколений назад). Просто син-кос - довольно скользкий для оптимизации пример (макс. выигрыш - ну, будет ускорение в разы, а вокруг ускоренного фрагмента же лежит неускоренная остальная программа, и весь выигрыш может замаскироваться (ну, будет прога работать 99 сек вместо 100 - толку от этого?)). Вот если бы была exp() - там да, её можно аппроксимировать и векторизовать всего несколькими командами, и ничего сложнее умножения при этом не будет (рецепт опубликован буржуинами в статьях 1999 и 2008годов, у меня работает - но никому подробности не расскажу, ибо ускорение выходит во многие десятки раз, и ноу-хау поэтому пусть остаётся скрытым для ширнармасс). Таблиц при аппроксимации exp() в данном случае нет, аппроксимация тоже идёт не через приближение полиномами (или чем-то иным) - а совсем на иной идее. Ну и топикстартеру. Может, стоит переделать алгоритм/задачу так, чтобы синус-косинус не вычислять. Вернее, чтобы взамен аргумента этих функций получались сразу индексы в таблице. Т.е., например, получались углы в градусах. И хорошо, если они будут получаться в виде целых значений - чтобы затем не округлять, а то округление плавучки тоже бывает тормозным: я, например, при работе с компилятором от Борланда/Ембаркадеро в критических местах в явную вписываю вызов своей собственной функции FtoI(val) вместо округления через приведение типа, т.е. через (int)val - а то Борланд реализует приведение типа (и округление) через вызов дольше работающей функции с именем ftol или где-то рядом.
0
|
03.08.2014, 23:06 | 16 |
Вместо этого можно сделать умножение, которое работает намного быстрее (грубо говоря, деление на 100 есть умножение на 0.01)
Пойми ты простую вещь. Товарищу не надо писать программу для военного радара. Ему всего лишь нужно выполнение вполне себе конкретного задания для вполне себе конкретного преподавателя, которые ожидает вполне себе конкретный вариант решения Ты сейчас пытаешься придумать задачу, которую никто не ставил. Речь идёт о вычислении синуса и косинуса, больше ни о чём
0
|
1485 / 1412 / 240
Регистрация: 19.02.2010
Сообщений: 3,913
|
|
10.08.2014, 21:18 | 17 |
Гарантируете, что аргументы пойдут внутри всего одного периода син/кос?
Под делением имел в виду idiv именно для впихивания (округлённого до целого) результата умножения в один период (в размер таблицы) Ладно, всё, закончили.
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,512
|
||||||
10.08.2014, 21:29 | 18 | |||||
если ключевое слово таблица
то нужно создать таблицу синусов(косинусов) а потом к ней обращаться,по моему так например синус от 0 до 90 с шагом 1 градус
0
|
10.08.2014, 21:29 | |
10.08.2014, 21:29 | |
Помогаю со студенческими работами здесь
18
Посоветуйте, пожалуйста, максимально бюджетный вариант Максимально быстрый способ добавления миллионов объектов в коллекцию Хочу собрать максимально быстрый конфиг, бюджет ограничен (3500грн-4500грн) Как в Excel организовать максимально быстрый поиск среди миллиона значений ? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |