Модераторы: bsa

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Sin быстрее чем из math.h 
:(
    Опции темы
Staskot
Дата 3.2.2012, 17:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.2.2012

Репутация: нет
Всего: нет



ребят, вообщем мне задали написать программу которая считала синус быстрее чем из math.h ) скорость должна достигаться путем потери точности) Я вот написал код который(как я думаю должен быстрее работать) но на деле не вижу что он быстрее) подтолкните кто нить)
Код

#include <iostream>
#include <conio.h>
#include <math.h>
#include <windows.h>
const int N=100000;
void main(void)
{int i;
double x1,x2,y,z;
x1=1.0; x2=2.0-1.0e-10;// вот здесь я обрезаю точность до 10 знаков 
y=(x2-x1)/N;
LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);

LARGE_INTEGER time1;
QueryPerformanceCounter(&time1);
for(i=0,z=x1;i<N;i++,z+=y)
{
sin(z);
}
LARGE_INTEGER time2;
QueryPerformanceCounter(&time2);
time2.QuadPart -= time1.QuadPart;
double span = (double) time2.QuadPart / freq.QuadPart; 
printf( "for sin time: %f seconds\n", span );
getch();
} 

PM MAIL   Вверх
borisbn
Дата 3.2.2012, 17:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135



Цитата(Staskot @  3.2.2012,  17:21 Найти цитируемый пост)
// вот здесь я обрезаю точность до 10 знаков 

Здесь ты изменяешь шаг аргумента функции sin, да и то, по-моему, неправильно. Функция sin всё равно вызывается N раз. И (самое главное) тебе ж сказали

Цитата(Staskot @  3.2.2012,  17:21 Найти цитируемый пост)
написать программу которая считала синус быстрее чем из math.h 

а ты берёшь функцию sin из этого самого math.h  smile 

Короче, тебе нужно написать свою функцию вычисления синуса. Погугли "разложение синуса в ряд с заданной точностью". Ну или что-то в этом роде.


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
Фантом
Дата 3.2.2012, 18:27 (ссылка) |    (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


Профиль
Группа: Участник Клуба
Сообщений: 1516
Регистрация: 23.3.2008

Репутация: 4
Всего: 49



Цитата(Staskot @  3.2.2012,  18:21 Найти цитируемый пост)
ребят, вообщем мне задали написать программу которая считала синус быстрее чем из math.h ) скорость должна достигаться путем потери точности)

А более точной формулировки задания нет? А то ведь можно написать 
Код

float sin(float x)
{
return 0.0;
}

и это будет быстро и с абсолютной погрешностью не больше единицы.  smile 
PM   Вверх
borisbn
Дата 3.2.2012, 18:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135



Фантом, у тебя погрешность м.б. больше единицы, т.к. ты преобразуешь double в float (return 0.0;)
Надо
Цитата

float sin(float x)
{
return 0.0f;
}

 smile 
прикалываюсь, ессно


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
Фантом
Дата 3.2.2012, 20:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


Профиль
Группа: Участник Клуба
Сообщений: 1516
Регистрация: 23.3.2008

Репутация: 4
Всего: 49



Цитата(borisbn @  3.2.2012,  19:30 Найти цитируемый пост)
т.к. ты преобразуешь double в float (return 0.0;)

Именно для нуля не страшно.  smile 
PM   Вверх
feodorv
Дата 3.2.2012, 21:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Цитата(Staskot @  3.2.2012,  17:21 Найти цитируемый пост)
Я вот написал код

Гм. Приведённый код считает производительность стандартной функции sin, но нет даже намёка на собственную
Цитата(Staskot @  3.2.2012,  17:21 Найти цитируемый пост)
программу которая считала синус

 smile 


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
volatile
Дата 3.2.2012, 23:48 (ссылка) |    (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85



Единственно, где есть какая-то надежда обогнать math.h,  это табличный синус.
Да и то я сомневаюсь, что получится обогнать.
Там синус вычисляет мат.сопроцессор. вычисление синуса - его внутренняя комманда.

PM MAIL   Вверх
feodorv
Дата 4.2.2012, 00:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Вот здесь, по-моему, просили вычислить синус с заданной точностью...

Цитата(volatile @  3.2.2012,  23:48 Найти цитируемый пост)
Да и то я сомневаюсь, что получится обогнать

Если точность невысока (относительная ~10-4), то может и обогнать...


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
volatile
Дата 4.2.2012, 01:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85



Цитата(feodorv @  4.2.2012,  00:12 Найти цитируемый пост)
Если точность невысока (относительная ~10-4), то может и обогнать... 

надо будет замерить как-нибудь..
(иногда возникает необходимость в быстром синусе).
но чисто интуитивно -  что-либо значительного там не добиться...

PM MAIL   Вверх
feodorv
Дата 4.2.2012, 10:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Цитата(volatile @  4.2.2012,  01:36 Найти цитируемый пост)
надо будет замерить как-нибудь..


Набросал некоторую программку:
Код

#include <conio.h>
#include <math.h>
#include <windows.h>

double mysin( double value )
{
  double v2 = value * value;
  double step = value * v2 / 6.;
  return value - step + v2 * step / 20.;
}

double mysin2( double value )
{
  double v2 = value * value;
  double step = value * v2 / 6.;
  value -= step;
  step *= v2 / 20.;
  value += step;
  return value - step * v2 / 42.;
}

double mysin3( double value )
{
  double v2 = value * value;
  double step = value * v2 / 6.;
  double step2 = step * v2 / 20.;
  double step3 = step2 * v2 / 42.;
  return value - step + step2 - step3;
}

#define N 100000
#define M 100

enum
{
  SINMIN = 0,
  SINMAX,
  SINAVE,
  SINLAST
};

#define INITIME(tm) \
    (tm)[SINMAX] = (tm)[SINMIN] = (tm)[SINAVE] = 0

#define GETTIME(f,tm) \
  do{ \
    LARGE_INTEGER time1, time2; \
    double z, span; \
    int n; \
    \
    QueryPerformanceCounter( &time1 ); \
    for( n=0,z=y; n<N; n++, z+=y) (f)(z); \
    QueryPerformanceCounter( &time2 ); \
    \
    time2.QuadPart -= time1.QuadPart; \
    span = (double) time2.QuadPart / freq.QuadPart; \
    \
    if( (tm)[SINMAX] < span ) (tm)[SINMAX] = span; \
    if( (tm)[SINMIN] == 0 || (tm)[SINMIN] > span ) (tm)[SINMIN] = span; \
    (tm)[SINAVE] += span; \
  } while(0)

#define PRITIME(tm,fn) \
  printf( "%s time: %f %f %f seconds\n", (fn), (tm)[SINMIN], (tm)[SINMAX], (tm)[SINAVE] / (double) M);

#define SINCHECK

void main(void)
{
  int m;
  double y;
  LARGE_INTEGER freq;
  double ts[SINLAST], ty[SINLAST], ty2[SINLAST], ty3[SINLAST];

  y = 2.0 / (double) N;
  QueryPerformanceFrequency(&freq);
  INITIME( ts );
  INITIME( ty );
  INITIME( ty2 );
  INITIME( ty3 );

#ifdef SINCHECK
  {
    int n; double z;
    for( n=0,z=y; n<N/2; n++, z+=y)
    {
      double m = mysin(z), m2 = mysin2(z), m3 = mysin3(z), s = sin(z);
      if( fabs( (s-m)/z ) > 0.0002 ) printf( "Oops(mysin)... z=%f s=%f m=%f err=%f\n", z, s, m, fabs( (s-m)/z ));
      if( fabs( (s-m2)/z ) > 0.000003 ) printf( "Oops(mysin2)... z=%f s=%f m2=%f err=%f\n", z, s, m2, fabs( (s-m2)/z ));
      if( fabs( (s-m3)/z ) > 0.000003 ) printf( "Oops(mysin3)... z=%f s=%f m3=%f err=%f\n", z, s, m3, fabs( (s-m3)/z ));
    }
    for( n=0,z=1.0; n<N/2; n++, z+=y)
    {
      double m = mysin(z), m2 = mysin2(z), m3 = mysin3(z), s = sin(z);
      if( fabs( (s-m)/z ) > 0.013 ) printf( "Oops(mysin)... z=%f s=%f m=%f err=%f\n", z, s, m, fabs( (s-m)/z ));
      if( fabs( (s-m2)/z ) > 0.0007 ) printf( "Oops(mysin2)... z=%f s=%f m2=%f err=%f\n", z, s, m2, fabs( (s-m2)/z ));
      if( fabs( (s-m3)/z ) > 0.0007 ) printf( "Oops(mysin3)... z=%f s=%f m3=%f err=%f\n", z, s, m3, fabs( (s-m3)/z ));
    }
  }
#endif

  for( m = 0; m < M; m++)
  {
    Sleep(100);
    GETTIME( mysin, ty);
    GETTIME( mysin2, ty2);
    GETTIME( mysin3, ty3);
    GETTIME( sin, ts);
  }

  PRITIME( ts, "sin");
  PRITIME( ty, "mysin");
  PRITIME( ty2, "mysin2");
  PRITIME( ty3, "mysin3");
  getch();
}


Здесь mysin использует первые 3 члена разложения sin в ряд, mysin2 - уже 4, mysin3 - практически то же самое, что и mysin2, но несколько иначе считает сумму.

Результаты. С установленной SINCHECK:
Цитата

sin time: 0.017760 0.047614 0.020920 seconds
mysin time: 0.012157 0.026837 0.013616 seconds
mysin2 time: 0.017722 0.046867 0.019851 seconds
mysin3 time: 0.016511 0.037132 0.018554 seconds


С выключенной SINCHECK:
Цитата

sin time: 0.017547 0.039049 0.020133 seconds
mysin time: 0.012153 0.027060 0.013632 seconds
mysin2 time: 0.017726 0.054278 0.020688 seconds
mysin3 time: 0.018676 0.050791 0.021672 seconds

Гм. Почему так разнятся результаты (а это поведение устойчивое) с SINCHECK и без оной, понять не могу.

В любом случае mysin подходит под условие задачи, причём её точность в диапазоне аргументов -1 <= z <= 1 составляет две сотых процента, а в диапазоне -2 <= z <=2 - полтора процента (этот диапазон не покрывает -pi <= z <= pi, но это другая история).


Цитата(volatile @  4.2.2012,  01:36 Найти цитируемый пост)
но чисто интуитивно -  что-либо значительного там не добиться...

 smile 


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
ksili
Дата 4.2.2012, 13:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: нет
Всего: 17



Где-то я слышал, что обычно вычисляют синус приближением многочленами Чебышева. FPU по-моему так и делает. Но в нём многочлены взяты такого порядка, чтобы получить расширенную точность (максимальная точность FPU). А вам надо взять степень меньше. 

Если найдете материалы по этой теме, киньте ссылку здесь. Мне тоже интересно.


--------------------
Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)
PM MAIL   Вверх
boostcoder
Дата 4.2.2012, 13:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 20
Всего: 110



Цитата(feodorv @  4.2.2012,  10:56 Найти цитируемый пост)
QueryPerformanceCounter

можно было использовать boost.chrono, чтоб код можно было выполнить не только на венде.

спасибо.

PM WWW   Вверх
feodorv
Дата 4.2.2012, 15:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



 smile Дурная голова ногам покоя не даёт... Не правильно расчитал ошибку  smile  А смайлика, посыпающего голову пеплом, нет?)))

Короче говоря, вместо 
Код
(s-m)/s
 написал 
Код
(s-m)/z


Тогда цифры получаются такие:
Код

    for( n=0,z=y; n<N/2; n++, z+=y)
    {
      double m = mysin(z), m2 = mysin2(z), m3 = mysin3(z), s = sin(z);
      if( fabs( (s-m)/s ) > 0.00024 ) printf( "Oops(mysin)... z=%f s=%f m=%f err=%f\n", z, s, m, fabs( (s-m)/s ));
      if( fabs( (s-m2)/s ) > 0.000004 ) printf( "Oops(mysin2)... z=%f s=%f m2=%f err=%f\n", z, s, m2, fabs( (s-m2)/s ));
      if( fabs( (s-m3)/s ) > 0.000004 ) printf( "Oops(mysin3)... z=%f s=%f m3=%f err=%f\n", z, s, m3, fabs( (s-m3)/s ));
    }
    for( n=0,z=1.0; n<N/2; n++, z+=y)
    {
      double m = mysin(z), m2 = mysin2(z), m3 = mysin3(z), s = sin(z);
      if( fabs( (s-m)/s ) > 0.027 ) printf( "Oops(mysin)... z=%f s=%f m=%f err=%f\n", z, s, m, fabs( (s-m)/s ));
      if( fabs( (s-m2)/s ) > 0.0015 ) printf( "Oops(mysin2)... z=%f s=%f m2=%f err=%f\n", z, s, m2, fabs( (s-m2)/s ));
      if( fabs( (s-m3)/s ) > 0.0015 ) printf( "Oops(mysin3)... z=%f s=%f m3=%f err=%f\n", z, s, m3, fabs( (s-m3)/s ));
    }


То есть, в диапазоне -2 <= z <=2 точность достигает трёх процентов (не полутора). Ну это так, для порядка)))


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
Staskot
Дата 4.2.2012, 15:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.2.2012

Репутация: нет
Всего: нет



feodorv 
хм запустил вашу у программу у себя( VS 2010) вот какие у меня результаты: 
sin time: 0.002971  0.005865  0.003412 seconds
mysin time : 0.006127  0.013735  0.007204 seconds
mysin2 time : 0.007505  0.013541  0.008607 seconds
mysin3 time : 0.008309  0.016118  0.009687 seconds
И ещё я правильно понял что добиться скорости  в 50% нельзя если обрезать до 10 знаков?
PM MAIL   Вверх
feodorv
Дата 4.2.2012, 15:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



По поводу многочленов Чебышева:Добавлено @ 15:56
Цитата(Staskot @  4.2.2012,  15:49 Найти цитируемый пост)
И ещё я правильно понял что добиться скорости  в 50% нельзя если обрезать до 10 знаков? 

Можно как раз попробовать Чебышевкий вариант)))
А обрезано и так до невозможности...
Если у Вас очень малые z (порядка 10-6), то можно просто возвращать z, не заморачиваясь, абсолютная точность до 10 знаков будет обеспечена. Скорость при этом будет обалденная)))
Я так и не понял, в каком место вам нужны эти 10 знаков. Чтобы совпадало с точностью до 10 знаков на диапазоне -2 <= z <= 2 никак встроенный sin не обогнать.

Добавлено @ 15:58
Но у Вас sin более чем в два раза опережает mysin  smile Что и требовалось доказать smile Видимо, новые процессоры, новые сопроцессоры, новые шины, новая частота памяти...

Это сообщение отредактировал(а) feodorv - 4.2.2012, 16:08


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.0620 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.