Форум программистов, компьютерный форум CyberForum.ru

Максимально быстрый вариант вычисления sinf/cosf - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Robesper3411
 Аватар для Robesper3411
13 / 13 / 1
Регистрация: 20.02.2012
Сообщений: 430
Записей в блоге: 1
27.07.2014, 00:48     Максимально быстрый вариант вычисления sinf/cosf #1
Вопрос, возможно, не в ту ветку форума, но решение предполагается на с++, поэтому просьба расшифровать задание.
Текст такой:
Напишите пред-расчетный (максимальность быстрый) вариант вычисления sinf/cosf по таблице с точностью до сотых. Вопрос - что нужно сделать?! А то я не понял.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.07.2014, 00:48     Максимально быстрый вариант вычисления sinf/cosf
Посмотрите здесь:

Как бы вы написали кусок программы Вариант 1 или Вариант 2 ? C++
Быстрый вызов C++
Быстрый почтальон C++
Найти сумму максимально отрицательного и максимально положительного элемента массива C++
C++ быстрый xor
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
all_angarsk
747 / 254 / 43
Регистрация: 13.12.2009
Сообщений: 954
27.07.2014, 05:38     Максимально быстрый вариант вычисления sinf/cosf #2
Sin он и в Африке Sin;
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
 
namespace Sin
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
 
        private void button1_Click(object sender, EventArgs e)
        {
            double s = Convert.ToDouble(textBox1.Text);
            double d = Math.Sin(s * Math.PI / 180);
            textBox2.Text = Convert.ToString(Math.Round(d,3));
        }
 
        private void button2_Click(object sender, EventArgs e)
        {
            double s = Convert.ToDouble(textBox1.Text);
            double d = Math.Cos(s * Math.PI / 180);
            textBox2.Text = Convert.ToString(Math.Round(d, 3));
        }
    }
}
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
27.07.2014, 07:50     Максимально быстрый вариант вычисления sinf/cosf #3
Думаю что-то вроде этого (об оптимальности не говорю):
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <cstddef>
#include <cmath>
 
 
auto const pi = std::acos(-1.f);
 
struct sin_table {
    
   explicit sin_table(float const step) : step(step) {
      auto const size = static_cast<std::size_t>(2 * pi / step);
      
      table.resize(size);
      
      for (std::size_t i = 0; i != size; ++i) {
         table[i] = std::sin(i * step);
      }
   }
   
   float operator ()(float const arg) const {
      auto const pos = static_cast<std::size_t>(std::abs(arg / step)) % table.size();
      auto const value = table[pos];
      return std::signbit(arg) ? -value : value;
   }
 
private:
   float const step;
   std::vector<float> table;
};
 
 
int main() {
   sin_table const sin(.01f);
   
   std::cout << sin(.0f)            << std::endl;
   std::cout << sin(pi / 2)         << std::endl;
   std::cout << sin(pi)             << std::endl;
   std::cout << sin(3 * pi / 2)     << std::endl;
   std::cout << sin(5 * pi / 2)     << std::endl;
   std::cout << sin(-pi / 2)        << std::endl;
   std::cout << sin(-3 * pi / 2)    << std::endl;
   std::cout << sin(-5 * pi / 2)    << std::endl;
}
http://ideone.com/DqytmG
MasterOfOrion
Заблокирован
27.07.2014, 07:58     Максимально быстрый вариант вычисления sinf/cosf #4
А в чём прикол то ? Функция sinf не устраивает? Её ж тоже не дураки писали
Не думаю что даже на уровне ассемблера под Intel можно что - то улучшить ....

Добавлено через 1 минуту
Да и вообще ТС юзает шарп или по крайней мере CLR, что к данному трею никакого отношения не имеет
all_angarsk
747 / 254 / 43
Регистрация: 13.12.2009
Сообщений: 954
27.07.2014, 08:33     Максимально быстрый вариант вычисления sinf/cosf #5
нужно подставить функцию sinf и проверить результат. В чем трудность не пойму???
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,653
27.07.2014, 11:42     Максимально быстрый вариант вычисления sinf/cosf #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
/////////////////////////////////////////////////////////////////////////////////////////
//Напишите предрасчетный (максимальность быстрый) вариант вычисления sinf/cosf по таблице 
//с точностью до сотых.
/////////////////////////////////////////////////////////////////////////////////////////
#include <cmath>
#include <iostream>
#include <map>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::map    < float,    float   >   T_sin_cos_of;
/////////////////////////////////////////////////////////////////////////////////////////
const   float   PI      =   acos( -1.0f );
const   float   _2_PI   =   PI * 2.0f;
/////////////////////////////////////////////////////////////////////////////////////////
T_sin_cos_of    fill_and_get_sin_of()
{
    T_sin_cos_of    sin_of;
 
    for( float  sin_x = 0.0; sin_x <= 1.0; sin_x += 0.01f )
    {
        float  x   =   asin( sin_x );
        float  x1  =   PI - x;
 
        sin_of[ x       ]   =   sin_x;
        sin_of[ x + PI  ]   =   -sin_x;
 
        sin_of[ x1      ]   =   sin_x;
        sin_of[ x1 + PI ]   =   -sin_x;
    }
 
    return  sin_of;
}
/////////////////////////////////////////////////////////////////////////////////////////
float  input_and_get_x()
{
    std::cout   <<  "x = ";
    float   x;
    std::cin    >>  x;
    return  x;
}
/////////////////////////////////////////////////////////////////////////////////////////
float   get_table_sin( float    x )
{
    static  const   T_sin_cos_of    sin_of  =   fill_and_get_sin_of();
 
    if( x < 0 )
    {
        return  -get_table_sin(-x);
    }
 
    auto    it  =   sin_of.lower_bound
                        (
                            fmod( x, _2_PI )
                        );
 
    return  it  ==  sin_of.end()
                ?   sin_of.rbegin()->second
                :   it->second;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_sin_cos_of    fill_and_get_cos_of()
{
    T_sin_cos_of    cos_of;
 
    for( float  cos_x = -1.0; cos_x <= 1.0; cos_x += 0.01f )
    {
        float  x   =   acos( cos_x );
        float  x1  =   _2_PI - x;
 
        cos_of[ x   ]   =   cos_x;
        cos_of[ x1  ]   =   cos_x;
    }
 
    return  cos_of;
}
/////////////////////////////////////////////////////////////////////////////////////////
float   get_table_cos( float    x )
{
    static  const   T_sin_cos_of    cos_of  =   fill_and_get_cos_of();
 
    x   =   abs(x);
 
    auto    it  =   cos_of.lower_bound
                        (
                            fmod( x, _2_PI )
                        );
 
    return  it  ==  cos_of.end()
                ?   cos_of.rbegin()->second
                :   it->second;
}
/////////////////////////////////////////////////////////////////////////////////////////
void    test_sin()
{
    float   delta       =   0;
    float   delta_max   =   0;
 
    for( float  x = -100.0f; x <= 100.0; x += 0.001f )
    {
        delta   =   abs (
                            sin(x)  -   get_table_sin(x)
                        );
 
        if( delta > delta_max )
        {
            delta_max   =   delta;
        }
    }//for
 
    std::cout   <<  "Максимальная погрешность табличного синуса составляет\t\t"
                <<  delta_max
                <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
void    test_cos()
{
    float   delta       =   0;
    float   delta_max   =   0;
 
    float   x_for_max   =   0;
 
    for( float  x = -100.0; x <= 100.0; x += 0.001f )
    {
        delta   =   abs (
                            cos(x)  -   get_table_cos(x)
                        );
 
        if( delta > delta_max )
        {
            delta_max   =   delta;
            x_for_max   =   x;
        }
    }//for
 
    std::cout   <<  "Максимальная погрешность табличного косинуса составляет\t\t"
                <<  delta_max
                <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    test_sin();
    test_cos();
 
    for(;;)
    {
        float   x       =   input_and_get_x     ();
        float   sit_x   =   get_table_sin       (x);
        float   cos_x   =   get_table_cos       (x);
 
        std::cout   <<  "sin("
                    <<  x
                    <<  ") = "
                    <<  sit_x
                    <<  std::endl
                    <<  "cos("
                    <<  x
                    <<  ") = "
                    <<  cos_x
                    <<  std::endl
                    <<  "sin^2 + cos^2 = "
                    <<  sit_x * sit_x + cos_x * cos_x
                    <<  std::endl
                    <<  std::endl;
    }//for
}
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,123
Записей в блоге: 26
27.07.2014, 13:54     Максимально быстрый вариант вычисления sinf/cosf #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Я не сильно разбираюсь в алгоритмах, но, думается, смысл задания следующий. Синус и косинус вычисляется через разложение в ряд или что-то типа того. Реализацию в glibc можно посмотреть

https://sourceware.org/git/?p=glibc....sinf.c;hb=HEAD
https://sourceware.org/git/?p=glibc....sinf.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 минут
Цитата Сообщение от MasterOfOrion Посмотреть сообщение
А в чём прикол то ? Функция sinf не устраивает?
"Стандартный" синус вычисляет с точностью до 7 или 8 знака (в десятичной системе) и работает порядка сотен машинных тактов. Для каких-нибудь систем, работающих в реальном времени (например, обрабатывающих данные с локатора или 3d-игрушек) это слишком жирно. Вместо этого можно получить менее точное значение (ибо в определённых классах задач вполне хватает и с точностью до сотых), но в несколько раз быстрее. Для этого и используют таблицы, где все значения заранее вычислены
VTsaregorodtsev
293 / 273 / 35
Регистрация: 19.02.2010
Сообщений: 1,205
27.07.2014, 21:40     Максимально быстрый вариант вычисления sinf/cosf #8
Цитата Сообщение от Evg Посмотреть сообщение
Синус и косинус вычисляется через разложение в ряд или что-то типа того.
На всех процах х86-платформы, начиная собственно с родителя (вернее, с сопроцессора 8087), вычисляются отдельными процессорными командами. Если внутри соотв. мат.функций библиотеки какого-то компилятора лежит разложение в ряд - то это, похоже, диагноз для тех прогеров.
Начиная с ПняПро или Пня2 - есть и команда fsincos, вычисляющая для одного значения сразу 2 названных функции, что экономит время вдвое (для тех программ, где нужны сразу оба значения функций для одного и того же аргумента).
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
27.07.2014, 21:58     Максимально быстрый вариант вычисления sinf/cosf #9
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
вычисляются отдельными процессорными командами
Команды-то не магические, и методы их работы всё те же (да ещё и с ограничениями - большую таблицу в процессор не зашьёшь), а вот точность не задаётся, да и не векторизуются они...
VTsaregorodtsev
293 / 273 / 35
Регистрация: 19.02.2010
Сообщений: 1,205
27.07.2014, 22:00     Максимально быстрый вариант вычисления sinf/cosf #10
Цитата Сообщение от Somebody Посмотреть сообщение
да и не векторизуются они...
Так и таблица не будет векторизоваться
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
27.07.2014, 22:30     Максимально быстрый вариант вычисления sinf/cosf #11
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Так и таблица не будет векторизоваться
Так при умеренном использовании таблиц вычисления всё равно остаются. А если таблицу сделать большую и плотную или если точность нужна небольшая, так тогда даже вопросов не должно быть по производительности.
Robesper3411
 Аватар для Robesper3411
13 / 13 / 1
Регистрация: 20.02.2012
Сообщений: 430
Записей в блоге: 1
27.07.2014, 23:48  [ТС]     Максимально быстрый вариант вычисления sinf/cosf #12
я вот только все равно не понял - в чем суть задания. Что должно быть "на входе", а что - "на выходе". Вычислять синус и косинус - это без проблем. Но, что сделать нужно здесь?!
CyberSolver
 Аватар для CyberSolver
101 / 74 / 17
Регистрация: 23.07.2014
Сообщений: 686
Записей в блоге: 1
28.07.2014, 05:53     Максимально быстрый вариант вычисления sinf/cosf #13
Robesper3411, так это не к нам вопрос Но если я правильно понимаю логику таких задач, таблица у вас уже есть/кем-то задана (списана с какой-нибудь книжки 50-х). Для промежуточных значений - интерполяция, можно хоть линейную.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,123
Записей в блоге: 26
28.07.2014, 11:17     Максимально быстрый вариант вычисления sinf/cosf #14
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
На всех процах х86-платформы, начиная собственно с родителя (вернее, с сопроцессора 8087), вычисляются отдельными процессорными командами
Чисто на всякий случай. Если программа короткая, то она совсем необязательно работает быстро. Программа из одной аппаратной операции fsin будет работать 200 тактов, а не 1, как может показаться на первый взгляд. Что явно медленнее, чем вычисление короткого ряда

Цитата Сообщение от Robesper3411 Посмотреть сообщение
я вот только все равно не понял - в чем суть задания. Что должно быть "на входе", а что - "на выходе". Вычислять синус и косинус - это без проблем. Но, что сделать нужно здесь?!
Здесь нужно вычислять синус и косинус. Но сделать это быстро. Т.е. быстрее, чем стандартная реализация в библиотеке. А быстрее она должна работать за счёт того, что будет работать с меньшей точностью. Как уже писалось, один из вариантов быстрых вычислений - это вычислить заранее значения синусов в N точках (например, создать таблицу синусов для углов 0, 1, 2, ... 90 градусов). Затем при вызове синуса, например, от 37.3 градуса, взять из таблицы готовое заранее вычисленное значение для 37 градусов. Оно будет не очень точным, зато быстро
VTsaregorodtsev
293 / 273 / 35
Регистрация: 19.02.2010
Сообщений: 1,205
03.08.2014, 21:44     Максимально быстрый вариант вычисления sinf/cosf #15
Цитата Сообщение от Evg Посмотреть сообщение
Чисто на всякий случай. Если программа короткая, то она совсем необязательно работает быстро. Программа из одной аппаратной операции fsin будет работать 200 тактов
Лезем в оффтопик (для сишного раздела форума) - ну да ладно.
Не 200 - а порядка 100 (если не брать огрызки типа Атомов). В общем, у Агнера Фога в мануале по проц.командам хорошо расписаны растактовки для кучи процессоров.
Во вторых - я и не утверждал, что короткая прога всегда будет более быстрой. Просто при таблицах - будет как минимум одно деление (тоже времязатратная команда), и если этап с делениями ещё и можно будет векторизовать - то потом по таблице всё равно для каждого индекса придётся бегать по-отдельности (тут могу и ошибаться - может, где-нить в SSE4 и есть нужная команда, но в таком случае рискуем потерять портируемость на вполне ещё пригодные для работы компутеры с процами на пару поколений назад).
Просто син-кос - довольно скользкий для оптимизации пример (макс. выигрыш - ну, будет ускорение в разы, а вокруг ускоренного фрагмента же лежит неускоренная остальная программа, и весь выигрыш может замаскироваться (ну, будет прога работать 99 сек вместо 100 - толку от этого?)). Вот если бы была exp() - там да, её можно аппроксимировать и векторизовать всего несколькими командами, и ничего сложнее умножения при этом не будет (рецепт опубликован буржуинами в статьях 1999 и 2008годов, у меня работает - но никому подробности не расскажу, ибо ускорение выходит во многие десятки раз, и ноу-хау поэтому пусть остаётся скрытым для ширнармасс). Таблиц при аппроксимации exp() в данном случае нет, аппроксимация тоже идёт не через приближение полиномами (или чем-то иным) - а совсем на иной идее.

Ну и топикстартеру. Может, стоит переделать алгоритм/задачу так, чтобы синус-косинус не вычислять. Вернее, чтобы взамен аргумента этих функций получались сразу индексы в таблице. Т.е., например, получались углы в градусах. И хорошо, если они будут получаться в виде целых значений - чтобы затем не округлять, а то округление плавучки тоже бывает тормозным: я, например, при работе с компилятором от Борланда/Ембаркадеро в критических местах в явную вписываю вызов своей собственной функции FtoI(val) вместо округления через приведение типа, т.е. через (int)val - а то Борланд реализует приведение типа (и округление) через вызов дольше работающей функции с именем ftol или где-то рядом.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,123
Записей в блоге: 26
03.08.2014, 23:06     Максимально быстрый вариант вычисления sinf/cosf #16
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Просто при таблицах - будет как минимум одно деление (тоже времязатратная команда)
Вместо этого можно сделать умножение, которое работает намного быстрее (грубо говоря, деление на 100 есть умножение на 0.01)

Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
и если этап с делениями ещё и можно будет векторизовать - то потом по таблице всё равно для каждого индекса придётся бегать по-отдельности
Пойми ты простую вещь. Товарищу не надо писать программу для военного радара. Ему всего лишь нужно выполнение вполне себе конкретного задания для вполне себе конкретного преподавателя, которые ожидает вполне себе конкретный вариант решения

Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
а вокруг ускоренного фрагмента же лежит неускоренная остальная программа, и весь выигрыш может замаскироваться (ну, будет прога работать 99 сек вместо 100 - толку от этого?)
Ты сейчас пытаешься придумать задачу, которую никто не ставил. Речь идёт о вычислении синуса и косинуса, больше ни о чём
VTsaregorodtsev
293 / 273 / 35
Регистрация: 19.02.2010
Сообщений: 1,205
10.08.2014, 21:18     Максимально быстрый вариант вычисления sinf/cosf #17
Цитата Сообщение от Evg Посмотреть сообщение
Вместо этого можно сделать умножение, которое работает намного быстрее
Гарантируете, что аргументы пойдут внутри всего одного периода син/кос?
Под делением имел в виду idiv именно для впихивания (округлённого до целого) результата умножения в один период (в размер таблицы)

Ладно, всё, закончили.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2014, 21:29     Максимально быстрый вариант вычисления sinf/cosf
Еще ссылки по теме:

Быстрый поиск C++
Быстрый сплит C++
C++ Быстрый аллокатор

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
10.08.2014, 21:29     Максимально быстрый вариант вычисления sinf/cosf #18
Цитата Сообщение от Robesper3411 Посмотреть сообщение
Напишите пред-расчетный (максимальность быстрый) вариант вычисления sinf/cosf по таблице с точностью до сотых. Вопрос - что нужно сделать?!
если ключевое слово таблица
то нужно создать таблицу синусов(косинусов) а потом к ней обращаться,по моему так
например синус от 0 до 90 с шагом 1 градус

C++
1
2
3
4
5
6
7
8
9
10
11
12
double tbSin[91];
 
void InitSin()
{
 for(int i=0;i<=90;i++)
   tbSin[i]=sin((double)i*3.1415 /180.0);
}
 
double MySin(int ag)
{
return  tbSin[ag];
}
Yandex
Объявления
10.08.2014, 21:29     Максимально быстрый вариант вычисления sinf/cosf
Ответ Создать тему
Опции темы

Текущее время: 17:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru