Исследование касалось только целых (точнее, натуральных) степеней аргумента, а не вещественных. Целые степени намеренно приняты такими большими, чтобы увидеть разницу.
Всего тестов 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
Сделал через функции
2009.11.08 09:37:08 stepen EURUSD,M15: Хитрое перемножение вещественных: 46.141000002009.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 баров использование стандартной функции практически не повлияет. Интерес представляет только использование в тяжелых алгоритмах. И то, надо с умом применять.
Разница довольно весомая. Предпологал такое, но не до такой степени. Надо функцию делать для хитрого перемножения. Только на расчетах потеря времени опять будет
Насчет хитрости этого перемножения я не в курсе, но реализовывать приходилось давным-давно :) Всё делается очень просто исходя из двоичного представления показателя степени. И естественно возведение в степень с целым показателем лучше сделать свое, чем использовать 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); }
Я бы так не сказал. Массовые вычисления регрессий - хороший пример. У меня как раз такой случай сейчас (это скрипт, считающий статистику и запускающийся всего один раз). Если это будет не очень сложно, выложу результаты сравнения.
Ну а до необходимости применения хитрого алгоритма дело доходит и правда не так часто. Но и реализация его совсем несложная.
Насчет хитрости этого перемножения я не в курсе, но реализовывать приходилось давным-давно :) Всё делается очень просто исходя из двоичного представления показателя степени. И естественно возведение в степень с целым показателем лучше сделать свое, чем использовать MathPow (логично было бы предположить, что там используется что-нибудь типа exp(power*ln(base))).
Собственно, вот реализация. Полезно читать сайты, посвященные алгоритмам типа http://algolist.manual.ru/ и http://alglib.sources.ru/. :)
UPD: Что-то я не посмотрел, там по ссылке возведение в степень по модулю и с другими типами. Вот так примерно надо:
Быстрее все равно не получилось.
Я бы так не сказал. Массовые вычисления регрессий - хороший пример. У меня как раз такой случай сейчас (это скрипт, считающий статистику и запускающийся всего один раз). Если это будет не очень сложно, выложу результаты сравнения.
Ну а до необходимости применения хитрого алгоритма дело доходит и правда не так часто. Но и реализация его совсем несложная.
Если такая нужда есть- то это совершенно другое дело!
А какой диапазон чисел у Вас, Mathemat, ходит в аргументах?
В общем-то, есть целочисленный вариант при котором вычисления занимают 0 ))).
Т.е. не 14.672 секунд, а 0 ))).
Причем способ годится для любой функции.
А какой диапазон чисел у Вас, Mathemat, ходит в аргументах?
В общем-то, есть вариант при котором вычисления занимают 0 ))).
Да в том-то и дело, что диапазоны-то разные. В худшем случае - примерно от -1500 до +1500 с шагом 10 (300 чисел). Но я, кажись, догадался, что Вы имеете в виду. Табулирование степеней, что ли?
P.S. Понял, кажись. Сумма целых степеней целых вычисляется по известным формулам. Да, но этот случай самый простой. А приходится ведь не только степени независимого аргумента вычислять, но и еще умножать их на степени значений. Тут простой формулой уже не обойтись.
Вот сейчас прикинул, сколько раз пришлось бы в степень возводить в моем случае. Немного, никак не больше 10 миллионов. Так что зря беспокоился, преувеличил угрозу.
2 Vinin: да ладно, Вить, забудем о хитром алгоритме. В финансовых вычислениях необходимость в нем редка. Но как пример программной оптимизации вычислений он вполне показателен.
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
Исследование касалось только целых (точнее, натуральных) степеней аргумента, а не вещественных. Целые степени намеренно приняты такими большими, чтобы увидеть разницу.
Всего тестов 6, по три на каждую группу - с целыми и вещественными числами.
Вот скрипт:
Результаты работы скрипта таковы:
Результаты нужно читать снизу вверх :)
Как видим, функция MathPow() - очень, очень медленная. Всегда, когда можно ее заменить (скажем, если степень целая), это нужно делать - даже если умножений много. Дополнительный эффект получается, если степень велика: достаточно преобразовать показатель степени в двоичную систему счисления и перемножить получающиеся степени двойки. Общее число умножений получается гораздо меньшим, чем при прямом перемножении.