20 / 19 / 3
Регистрация: 20.02.2012
Сообщений: 526
Записей в блоге: 1
1

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

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

Author24 — интернет-сервис помощи студентам
Вопрос, возможно, не в ту ветку форума, но решение предполагается на с++, поэтому просьба расшифровать задание.
Текст такой:
Напишите пред-расчетный (максимальность быстрый) вариант вычисления sinf/cosf по таблице с точностью до сотых. Вопрос - что нужно сделать?! А то я не понял.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.07.2014, 00:48
Ответы с готовыми решениями:

Более быстрый вариант сравнения фотографий
Всем привет. Нужно сравнить на идентичность несколько сотен фотографий, чтобы убрать...

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

Быстрый поиск максимально похожего слова
Добрый день! Есть словарь строк List<string>, отсортированный по алфавиту. Есть некое слово,...

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

17
761 / 268 / 57
Регистрация: 13.12.2009
Сообщений: 1,101
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
What a waste!
1607 / 1299 / 180
Регистрация: 21.04.2012
Сообщений: 2,727
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
Заблокирован
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
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
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
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 минут
Цитата Сообщение от MasterOfOrion Посмотреть сообщение
А в чём прикол то ? Функция sinf не устраивает?
"Стандартный" синус вычисляет с точностью до 7 или 8 знака (в десятичной системе) и работает порядка сотен машинных тактов. Для каких-нибудь систем, работающих в реальном времени (например, обрабатывающих данные с локатора или 3d-игрушек) это слишком жирно. Вместо этого можно получить менее точное значение (ибо в определённых классах задач вполне хватает и с точностью до сотых), но в несколько раз быстрее. Для этого и используют таблицы, где все значения заранее вычислены
2
1485 / 1412 / 240
Регистрация: 19.02.2010
Сообщений: 3,913
27.07.2014, 21:40 8
Цитата Сообщение от Evg Посмотреть сообщение
Синус и косинус вычисляется через разложение в ряд или что-то типа того.
На всех процах х86-платформы, начиная собственно с родителя (вернее, с сопроцессора 8087), вычисляются отдельными процессорными командами. Если внутри соотв. мат.функций библиотеки какого-то компилятора лежит разложение в ряд - то это, похоже, диагноз для тех прогеров.
Начиная с ПняПро или Пня2 - есть и команда fsincos, вычисляющая для одного значения сразу 2 названных функции, что экономит время вдвое (для тех программ, где нужны сразу оба значения функций для одного и того же аргумента).
0
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
27.07.2014, 21:58 9
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
вычисляются отдельными процессорными командами
Команды-то не магические, и методы их работы всё те же (да ещё и с ограничениями - большую таблицу в процессор не зашьёшь), а вот точность не задаётся, да и не векторизуются они...
0
1485 / 1412 / 240
Регистрация: 19.02.2010
Сообщений: 3,913
27.07.2014, 22:00 10
Цитата Сообщение от Somebody Посмотреть сообщение
да и не векторизуются они...
Так и таблица не будет векторизоваться
0
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
27.07.2014, 22:30 11
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Так и таблица не будет векторизоваться
Так при умеренном использовании таблиц вычисления всё равно остаются. А если таблицу сделать большую и плотную или если точность нужна небольшая, так тогда даже вопросов не должно быть по производительности.
0
20 / 19 / 3
Регистрация: 20.02.2012
Сообщений: 526
Записей в блоге: 1
27.07.2014, 23:48  [ТС] 12
я вот только все равно не понял - в чем суть задания. Что должно быть "на входе", а что - "на выходе". Вычислять синус и косинус - это без проблем. Но, что сделать нужно здесь?!
0
102 / 75 / 17
Регистрация: 23.07.2014
Сообщений: 877
Записей в блоге: 1
28.07.2014, 05:53 13
Robesper3411, так это не к нам вопрос Но если я правильно понимаю логику таких задач, таблица у вас уже есть/кем-то задана (списана с какой-нибудь книжки 50-х). Для промежуточных значений - интерполяция, можно хоть линейную.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
28.07.2014, 11:17 14
Лучший ответ Сообщение было отмечено Robesper3411 как решение

Решение

Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
На всех процах х86-платформы, начиная собственно с родителя (вернее, с сопроцессора 8087), вычисляются отдельными процессорными командами
Чисто на всякий случай. Если программа короткая, то она совсем необязательно работает быстро. Программа из одной аппаратной операции fsin будет работать 200 тактов, а не 1, как может показаться на первый взгляд. Что явно медленнее, чем вычисление короткого ряда

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

Ну и топикстартеру. Может, стоит переделать алгоритм/задачу так, чтобы синус-косинус не вычислять. Вернее, чтобы взамен аргумента этих функций получались сразу индексы в таблице. Т.е., например, получались углы в градусах. И хорошо, если они будут получаться в виде целых значений - чтобы затем не округлять, а то округление плавучки тоже бывает тормозным: я, например, при работе с компилятором от Борланда/Ембаркадеро в критических местах в явную вписываю вызов своей собственной функции FtoI(val) вместо округления через приведение типа, т.е. через (int)val - а то Борланд реализует приведение типа (и округление) через вызов дольше работающей функции с именем ftol или где-то рядом.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
03.08.2014, 23:06 16
Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
Просто при таблицах - будет как минимум одно деление (тоже времязатратная команда)
Вместо этого можно сделать умножение, которое работает намного быстрее (грубо говоря, деление на 100 есть умножение на 0.01)

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

Цитата Сообщение от VTsaregorodtsev Посмотреть сообщение
а вокруг ускоренного фрагмента же лежит неускоренная остальная программа, и весь выигрыш может замаскироваться (ну, будет прога работать 99 сек вместо 100 - толку от этого?)
Ты сейчас пытаешься придумать задачу, которую никто не ставил. Речь идёт о вычислении синуса и косинуса, больше ни о чём
0
1485 / 1412 / 240
Регистрация: 19.02.2010
Сообщений: 3,913
10.08.2014, 21:18 17
Цитата Сообщение от Evg Посмотреть сообщение
Вместо этого можно сделать умножение, которое работает намного быстрее
Гарантируете, что аргументы пойдут внутри всего одного периода син/кос?
Под делением имел в виду idiv именно для впихивания (округлённого до целого) результата умножения в один период (в размер таблицы)

Ладно, всё, закончили.
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,512
10.08.2014, 21:29 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];
}
0
10.08.2014, 21:29
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.08.2014, 21:29
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru