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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Robesper3411
14 / 14 / 1
Регистрация: 20.02.2012
Сообщений: 437
Записей в блоге: 1
#1

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

27.07.2014, 00:48. Просмотров 1203. Ответов 17
Метки нет (Все метки)

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

Найти сумму максимально отрицательного и максимально положительного элемента массива - C++
Ребята, помогите, плиз)) найти суму максимально отрицательного и максимально положительного элемента массива

Выбрать вариант не имеющий ошибки и к каждому написать почему этот вариант правильный/неправильный - C++
Прошу помогите, я плохо понимаю c++, да и простите если не в той теме, в общем, дали задание: Выбрать вариант не имеющий ошибки и к...

Как бы вы написали кусок программы, Вариант 1 или Вариант 2? - C++
Как бы вы написали кусок программы Вариант 1 или Вариант 2 ? Вариант 1. double Value0 = value0 / 100; switch (i){ case 1: ...

Более быстрый вариант сравнения фотографий - C#
Всем привет. Нужно сравнить на идентичность несколько сотен фотографий, чтобы убрать повторяющиеся(одинаковые). Посоветуйте, каким...

Запрос данных с экрана максимально быстрый - C++ Builder
Товарищи приветствую Вас! Помогите с проблемой Дело в том что, я раньше запрашивал пиксель на экране через: В Windows XP это...

Посоветуйте, пожалуйста, максимально бюджетный вариант - Офисный компьютер
Камрады, здравствуйте! Задался целью собрать себе недорогой компьютер для следующих целей: 1) просмотр потокового видео на телевизоре +...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
all_angarsk
749 / 256 / 44
Регистрация: 13.12.2009
Сообщений: 961
27.07.2014, 05:38 #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));
        }
    }
}
1
gray_fox
What a waste!
1520 / 1223 / 70
Регистрация: 21.04.2012
Сообщений: 2,560
Завершенные тесты: 3
27.07.2014, 07:50 #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
1
MasterOfOrion
Заблокирован
27.07.2014, 07:58 #4
А в чём прикол то ? Функция sinf не устраивает? Её ж тоже не дураки писали
Не думаю что даже на уровне ассемблера под Intel можно что - то улучшить ....

Добавлено через 1 минуту
Да и вообще ТС юзает шарп или по крайней мере CLR, что к данному трею никакого отношения не имеет
0
all_angarsk
749 / 256 / 44
Регистрация: 13.12.2009
Сообщений: 961
27.07.2014, 08:33 #5
нужно подставить функцию sinf и проверить результат. В чем трудность не пойму???
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
27.07.2014, 11:42 #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
}
1
Evg
Эксперт CАвтор FAQ
17808 / 6014 / 388
Регистрация: 30.03.2009
Сообщений: 16,525
Записей в блоге: 26
27.07.2014, 13:54 #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-игрушек) это слишком жирно. Вместо этого можно получить менее точное значение (ибо в определённых классах задач вполне хватает и с точностью до сотых), но в несколько раз быстрее. Для этого и используют таблицы, где все значения заранее вычислены
1
VTsaregorodtsev
353 / 334 / 48
Регистрация: 19.02.2010
Сообщений: 1,414
27.07.2014, 21:40 #8
Цитата Сообщение от Evg Посмотреть сообщение
Синус и косинус вычисляется через разложение в ряд или что-то типа того.
На всех процах х86-платформы, начиная собственно с родителя (вернее, с сопроцессора 8087), вычисляются отдельными процессорными командами. Если внутри соотв. мат.функций библиотеки какого-то компилятора лежит разложение в ряд - то это, похоже, диагноз для тех прогеров.
Начиная с ПняПро или Пня2 - есть и команда fsincos, вычисляющая для одного значения сразу 2 названных функции, что экономит время вдвое (для тех программ, где нужны сразу оба значения функций для одного и того же аргумента).
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
27.07.2014, 21:58 #9
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
вычисляются отдельными процессорными командами
Команды-то не магические, и методы их работы всё те же (да ещё и с ограничениями - большую таблицу в процессор не зашьёшь), а вот точность не задаётся, да и не векторизуются они...
0
VTsaregorodtsev
353 / 334 / 48
Регистрация: 19.02.2010
Сообщений: 1,414
27.07.2014, 22:00 #10
Цитата Сообщение от Somebody Посмотреть сообщение
да и не векторизуются они...
Так и таблица не будет векторизоваться
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
27.07.2014, 22:30 #11
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Так и таблица не будет векторизоваться
Так при умеренном использовании таблиц вычисления всё равно остаются. А если таблицу сделать большую и плотную или если точность нужна небольшая, так тогда даже вопросов не должно быть по производительности.
0
Robesper3411
14 / 14 / 1
Регистрация: 20.02.2012
Сообщений: 437
Записей в блоге: 1
27.07.2014, 23:48  [ТС] #12
я вот только все равно не понял - в чем суть задания. Что должно быть "на входе", а что - "на выходе". Вычислять синус и косинус - это без проблем. Но, что сделать нужно здесь?!
0
CyberSolver
101 / 74 / 17
Регистрация: 23.07.2014
Сообщений: 686
Записей в блоге: 1
28.07.2014, 05:53 #13
Robesper3411, так это не к нам вопрос Но если я правильно понимаю логику таких задач, таблица у вас уже есть/кем-то задана (списана с какой-нибудь книжки 50-х). Для промежуточных значений - интерполяция, можно хоть линейную.
0
Evg
Эксперт CАвтор FAQ
17808 / 6014 / 388
Регистрация: 30.03.2009
Сообщений: 16,525
Записей в блоге: 26
28.07.2014, 11:17 #14
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
На всех процах х86-платформы, начиная собственно с родителя (вернее, с сопроцессора 8087), вычисляются отдельными процессорными командами
Чисто на всякий случай. Если программа короткая, то она совсем необязательно работает быстро. Программа из одной аппаратной операции fsin будет работать 200 тактов, а не 1, как может показаться на первый взгляд. Что явно медленнее, чем вычисление короткого ряда

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

Ну и топикстартеру. Может, стоит переделать алгоритм/задачу так, чтобы синус-косинус не вычислять. Вернее, чтобы взамен аргумента этих функций получались сразу индексы в таблице. Т.е., например, получались углы в градусах. И хорошо, если они будут получаться в виде целых значений - чтобы затем не округлять, а то округление плавучки тоже бывает тормозным: я, например, при работе с компилятором от Борланда/Ембаркадеро в критических местах в явную вписываю вызов своей собственной функции FtoI(val) вместо округления через приведение типа, т.е. через (int)val - а то Борланд реализует приведение типа (и округление) через вызов дольше работающей функции с именем ftol или где-то рядом.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2014, 21:44
Привет! Вот еще темы с ответами:

Максимально бюджетный вариант стримерского игрового ПК - Игровой компьютер
Всем привет! Ребят,особо не шарю,поэтому прошу помощи у вас Помогите пожалуйста собрать компьютер в основном для игрушек с возможностью...

Максимально быстрый способ добавления миллионов объектов в коллекцию - Java SE
Всем привет. Собственно имеем объекты содержащие два поля long, double; таких объектов свыше 50_000_000. на данный момент такой объем...

Хочу собрать максимально быстрый конфиг, бюджет ограничен (3500грн-4500грн) - Выбор компьютера
Добрый вечер.хочу собрать пк,знаю что собрать что-то крутое не получится,но хочу чтоб было все максимальное по минимальным ценам и...

Как в Excel организовать максимально быстрый поиск среди миллиона значений ? - VBA
Пришлось делать поиск на листе Экселя. Однако записей там около миллиона и данные в четырёх столбцах. Функция Find работает медленно,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.08.2014, 21:44
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru