Скорость MathPow(): одно маленькое исследование

Новый комментарий
 

Исследование касалось только целых (точнее, натуральных) степеней аргумента, а не вещественных. Целые степени намеренно приняты такими большими, чтобы увидеть разницу.

Всего тестов 6, по три на каждую группу - с целыми и вещественными числами.

Вот скрипт:

#define _MAX  100000000

int start( )
{
   int st = GetTickCount( );
   /// прямое применение функции MathPow()
   double res;
   for( int i = 1; i < _MAX; i ++ )       res = MathPow( i, 38 );
   int time1 = GetTickCount( ) - st;
   Print( "Прямое применение функции MathPow(): " + time1 / 1000. );

   st = GetTickCount( );
   /// прямое перемножение аргументов
   for( i = 1; i < _MAX; i ++ )       res = i * i * i * i * i * 
                                            i * i * i * i * i * 
                                            i * i * i * i * i * 
                                            i * i * i * i * i * 
                                            i * i * i * i * i * 
                                            i * i * i * i * i * 
                                            i * i * i * i * i * 
                                            i * i * i;
   int time2 = GetTickCount( ) - st;
   Print( "Прямое перемножение целых аргументов: " + time2 / 1000. );

   st = GetTickCount( );
   /// хитрое перемножение аргументов (38 = 32 + 4 + 2). Всего - 7 перемножений вместо 37.
   int i2, i4, i8, i16, i32;
   for( i = 1; i < _MAX; i ++ )       
   {
      i2 = i * i;
      i4 = i2 * i2;
      i8 = i4 * i4;
      i16 = i8 * i8;
      i32 = i16 * i16;
      res = i32 * i4 * i2;
   }                                         
   int time3 = GetTickCount( ) - st;
   Print( "Хитрое перемножение целых: " + time3 / 1000. );


   /// аргумент - вещественное число
   
   st = GetTickCount( );
   double arg;
   /// прямое применение функции MathPow()
   for( i = 1; i < _MAX; i ++ )       
   {
      arg = MathSqrt( i );
      res = MathPow( arg, 20 );
   }   
   int time4 = GetTickCount( ) - st;
   Print( "Прямое применение функции MathPow(): " + time4 / 1000. );

   st = GetTickCount( );
   /// прямое перемножение аргументов
   for( i = 1; i < _MAX; i ++ )       
   {
      arg = MathSqrt( i );
      res = arg * arg * arg * arg * arg *
            arg * arg * arg * arg * arg *
            arg * arg * arg * arg * arg *
            arg * arg * arg * arg * arg;
   }         
   int time5 = GetTickCount( ) - st;
   Print( "Прямое перемножение вещественных: " + time5 / 1000. );

   st = GetTickCount( );
   /// хитрое перемножение аргументов (20 = 16 + 4). Всего - 5 перемножений вместо 19.
   double p2, p4, p8, p16;
   for( i = 1; i < _MAX; i ++ )       
   {
      arg = MathSqrt( i );
      p2 = arg * arg;
      p4 = p2 * p2;
      p8 = p4 * p4;
      p16 = p8 * p8;
      res = p16 * p4;
   }         
   int time6 = GetTickCount( ) - st;
   Print( "Хитрое перемножение вещественных: " + time6 / 1000. );
   
   return( 0 );
}

Результаты работы скрипта таковы:


Результаты нужно читать снизу вверх :)

Как видим, функция MathPow() - очень, очень медленная. Всегда, когда можно ее заменить (скажем, если степень целая), это нужно делать - даже если умножений много. Дополнительный эффект получается, если степень велика: достаточно преобразовать показатель степени в двоичную систему счисления и перемножить получающиеся степени двойки. Общее число умножений получается гораздо меньшим, чем при прямом перемножении.

 
Mathemat писал(а) >>

Исследование касалось только целых (точнее, натуральных) степеней аргумента, а не вещественных. Целые степени намеренно приняты такими большими, чтобы увидеть разницу.

Всего тестов 6, по три на каждую группу - с целыми и вещественными числами.

Вот скрипт:

Результаты работы скрипта таковы:

Результаты нужно читать снизу вверх :)

Как видим, функция MathPow() - очень, очень медленная. Всегда, когда можно ее заменить (скажем, если степень целая), это нужно делать - даже если умножений много. Дополнительный эффект получается, если степень велика: достаточно преобразовать показатель степени в двоичную систему счисления и перемножить получающиеся степени двойки. Общее число умножений получается гораздо меньшим, чем при прямом перемножении.

Разница довольно весомая. Предпологал такое, но не до такой степени. Надо функцию делать для хитрого перемножения. Только на расчетах потеря времени опять будет

 

14.672 /* функция */ - 3.141 /* хитрое перемножение */ = 11.531 /* разница */
11.531 / 100000000 /* кол-во прогонов */ = 0.00000011531 <--- это разница в секундах на одном прогоне

ИМХО, интерес академический

 

Сделал через функции

#define _MAX  100000000

int start( )
{
   int st = GetTickCount( );
   /// прямое применение функции MathPow()
   double res;
   for( int i = 1; i < _MAX; i ++ )       res = MathPow1( i, 38 );
   int time1 = GetTickCount( ) - st;
   Print( "Прямое применение функции MathPow():" + time1 / 1000. );

   st = GetTickCount( );
   /// прямое перемножение аргументов
   for( i = 1; i < _MAX; i ++ )       res = MathPow2( i, 38 );
   int time2 = GetTickCount( ) - st;
   Print( "Прямое перемножение целых аргументов: " + time2 / 1000. );

   st = GetTickCount( );
   /// хитрое перемножение аргументов (38 = 32 + 4 + 2). Всего - 7 перемножений вместо 37.
   int i2, i4, i8, i16, i32;
   for( i = 1; i < _MAX; i ++ )      res = MathPow3( i, 38 );
   int time3 = GetTickCount( ) - st;
   Print( "Хитрое перемножение целых: " + time3 / 1000. );


   /// аргумент - вещественное число
   
   st = GetTickCount( );
   double arg;
   /// прямое применение функции MathPow()
   for( i = 1; i < _MAX; i ++ )       res = MathPow1( MathSqrt(i), 20 );
   int time4 = GetTickCount( ) - st;
   Print( "Прямое применение функции MathPow(): " + time4 / 1000. );

   st = GetTickCount( );
   /// прямое перемножение аргументов
   for( i = 1; i < _MAX; i ++ )       res = MathPow2( MathSqrt(i), 20 );
   int time5 = GetTickCount( ) - st;
   Print( "Прймое перемножение вещественных: " + time5 / 1000. );

   st = GetTickCount( );
   /// хитрое перемножение аргументов (20 = 16 + 4). Всего - 5 перемножений вместо 19.
   double p2, p4, p8, p16;
   for( i = 1; i < _MAX; i ++ )       res = MathPow3( MathSqrt(i), 20 );
   int time6 = GetTickCount( ) - st;
   Print( "Хитрое перемножение вещественных: " + time6 / 1000. );
   
   return( 0 );
}
//+------------------------------------------------------------------+

double MathPow1(double base, int power){
   double Res=MathPow(base, power);
   return(Res);
}

double MathPow2(double base, int power){
   double Res=1;
   for (int i=1;i<=power;i++) Res*=base;
   return(Res);
}

double MathPow3(double base, int power){
   double Res=1, tmp=1;
   int st1=MathSqrt(power);
   int st2=power-st1*st1;
   Res*=MathPow2(MathPow2(base,st1),st1); 
   Res*=MathPow2(base,st2);
   return(Res);
}
2009.11.08 09:37:08 stepen EURUSD,M15: Хитрое перемножение вещественных: 46.14100000
2009.11.08 09:36:22 stepen EURUSD,M15: Прймое перемножение вещественных: 24.01600000
2009.11.08 09:35:58 stepen EURUSD,M15: Прямое применение функции MathPow(): 21.20300000
2009.11.08 09:35:37 stepen EURUSD,M15: Хитрое перемножение целых: 47.75000000
2009.11.08 09:34:49 stepen EURUSD,M15: Прямое перемножение целых аргументов: 35.96900000
2009.11.08 09:34:13 stepen EURUSD,M15: Прямое применение функции MathPow():19.32800000
 
Vinin писал(а) >>

Сделал через функции

2009.11.08 09:37:08 stepen EURUSD,M15: Хитрое перемножение вещественных: 46.14100000
2009.11.08 09:36:22 stepen EURUSD,M15: Прймое перемножение вещественных: 24.01600000
2009.11.08 09:35:58 stepen EURUSD,M15: Прямое применение функции MathPow(): 21.20300000
2009.11.08 09:35:37 stepen EURUSD,M15: Хитрое перемножение целых: 47.75000000
2009.11.08 09:34:49 stepen EURUSD,M15: Прямое перемножение целых аргументов: 35.96900000
2009.11.08 09:34:13 stepen EURUSD,M15: Прямое применение функции MathPow():19.32800000

Зачем же добавлять столько вызовов? Они все время съели!

Mathemat,

Эта разница заметна только для очень сложных циклических вычислений. На производительность индикатора с единственным вызовом этой функции на каждый бар при 65000 баров использование стандартной функции практически не повлияет. Интерес представляет только использование в тяжелых алгоритмах. И то, надо с умом применять.

 
Vinin писал(а) >>

Разница довольно весомая. Предпологал такое, но не до такой степени. Надо функцию делать для хитрого перемножения. Только на расчетах потеря времени опять будет

Насчет хитрости этого перемножения я не в курсе, но реализовывать приходилось давным-давно :) Всё делается очень просто исходя из двоичного представления показателя степени. И естественно возведение в степень с целым показателем лучше сделать свое, чем использовать MathPow (логично было бы предположить, что там используется что-нибудь типа exp(power*ln(base))).

Собственно, вот реализация. Полезно читать сайты, посвященные алгоритмам типа http://algolist.manual.ru/ и http://alglib.sources.ru/. :)

UPD: Что-то я не посмотрел, там по ссылке возведение в степень по модулю и с другими типами. Вот так примерно надо:

double FastPow(double base,int power) {
  double retVal=1;
  bool inv=false;
  if (power<0) {
    power=-power;
    inv=true;
  }
  while (power!=0) {
    if (power&1==0)
      base*=base;
    else
      retVal*=base;
    power>>=1;
  }
  if (inv)
    retVal=1.0/retVal;
  return (retVal);
}
 
jartmailru >>:

ИМХО, интерес академический

Я бы так не сказал. Массовые вычисления регрессий - хороший пример. У меня как раз такой случай сейчас (это скрипт, считающий статистику и запускающийся всего один раз). Если это будет не очень сложно, выложу результаты сравнения.

Ну а до необходимости применения хитрого алгоритма дело доходит и правда не так часто. Но и реализация его совсем несложная.

 
lea писал(а) >>

Насчет хитрости этого перемножения я не в курсе, но реализовывать приходилось давным-давно :) Всё делается очень просто исходя из двоичного представления показателя степени. И естественно возведение в степень с целым показателем лучше сделать свое, чем использовать MathPow (логично было бы предположить, что там используется что-нибудь типа exp(power*ln(base))).

Собственно, вот реализация. Полезно читать сайты, посвященные алгоритмам типа http://algolist.manual.ru/ и http://alglib.sources.ru/. :)

UPD: Что-то я не посмотрел, там по ссылке возведение в степень по модулю и с другими типами. Вот так примерно надо:

Быстрее все равно не получилось.

 
Mathemat >>:

Я бы так не сказал. Массовые вычисления регрессий - хороший пример. У меня как раз такой случай сейчас (это скрипт, считающий статистику и запускающийся всего один раз). Если это будет не очень сложно, выложу результаты сравнения.

Ну а до необходимости применения хитрого алгоритма дело доходит и правда не так часто. Но и реализация его совсем несложная.

Если такая нужда есть- то это совершенно другое дело!

А какой диапазон чисел у Вас, Mathemat, ходит в аргументах?

В общем-то, есть целочисленный вариант при котором вычисления занимают 0 ))).

Т.е. не 14.672 секунд, а 0 ))).

Причем способ годится для любой функции.

 
jartmailru >>:

А какой диапазон чисел у Вас, Mathemat, ходит в аргументах?

В общем-то, есть вариант при котором вычисления занимают 0 ))).

Да в том-то и дело, что диапазоны-то разные. В худшем случае - примерно от -1500 до +1500 с шагом 10 (300 чисел). Но я, кажись, догадался, что Вы имеете в виду. Табулирование степеней, что ли?

P.S. Понял, кажись. Сумма целых степеней целых вычисляется по известным формулам. Да, но этот случай самый простой. А приходится ведь не только степени независимого аргумента вычислять, но и еще умножать их на степени значений. Тут простой формулой уже не обойтись.

Вот сейчас прикинул, сколько раз пришлось бы в степень возводить в моем случае. Немного, никак не больше 10 миллионов. Так что зря беспокоился, преувеличил угрозу.

2 Vinin: да ладно, Вить, забудем о хитром алгоритме. В финансовых вычислениях необходимость в нем редка. Но как пример программной оптимизации вычислений он вполне показателен.

 
jartmailru писал(а) >>

В общем-то, есть целочисленный вариант при котором вычисления занимают 0 ))).

Т.е. не 14.672 секунд, а 0 ))).

Причем способ годится для любой функции.

Таблицы?) Неплохой вариант.
123
Новый комментарий
Причина обращения: