Comparison of Cube Root Finding Algorithms . Boost , Math Toolkit 2.5.0 , Comparison of Root Finding Algorithms

Comparison of Cube Root Finding Algorithms

В таблице ниже кубический корень из 28 был вычислен для трех фундаментальных типов типов с плавающей точкой и одного Boost.Multiprecision типа cpp_bin_float с использованием точности 50 десятичных цифр с использованием четырех алгоритмов.

Точный ответ был вычислен с использованием типа 100 десятичных цифр:

cpp_bin_float_100 full_answer ("3.036588971875662519420809578505669635581453977248111123242141654169177268411884961770250390838097895");

Время измеряли с использованием Boost.Timer с использованием class cpu_timer.

Its - это количество итераций, взятых для поиска корня.
Times — это время ЦП, затрачиваемое на произвольные единицы.
Норма является нормированным временем по сравнению с самым быстрым алгоритмом (со значением 1.00).
Dis — расстояние от ближайшего представления «точного» корня в битах. Расстояние от «точного» ответа измеряется с помощью функции Boost.Math float_distance. Расстояние в один или два бита означает, что все результаты «правильны». Зеро означает «точный» - ближайшее значение репрезентабельное для типа с плавающей точкой.

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

Используемая программа была root_finding_algorithms.cpp. использовалось 100000 оценок каждого типа и алгоритма с плавающей запятой, а время процессора оценивалось по повторным запускам с неопределенностью 10%. Сравнение MSVC для double и long double (которые идентичны на этой патформе) может дать руководство по неопределенности времени.

Запрошенная точность была установлена следующим образом:

Функция	Запрошенная точность
TOMS748	numeric_limits::цифры - 2
Ньютон	этаж (число_лимиты:: цифры * 0,6)
Галлей	этаж (число_лимиты:: цифры * 0.4)
Schröder	этаж (число_лимиты:: цифры * 0.4)

C++ Стандартная корневая функция куба std::cbrt определяется только для встроенных или фундаментальных типов, поэтому не может использоваться с любыми типами с плавающей точкой, определенными пользователем, такими как Boost.Multiprecision. Это, а также то, что функция куба настолько безупречна, позволяет реализатору использовать множество трюков для достижения быстрого вычисления. На некоторых платформах std::cbrt появился в несколько раз быстрее, чем более общий boost::math::cbrt, на других платформах/компиляторах boost::cbrt заметно быстрее. В целом, результаты сильно зависят от используемых вариантов компилятора выбора архитектуры кода/процессора. Можно предположить, что стандартная библиотека будет компилироваться с опциями почти , оптимальными для платформы, на которой она была установлена, где у пользователя больше выбора по сравнению с опциями, используемыми для Boost. Математика. Выберите что-то слишком общее / консервативное, и производительность пострадает, в то же время выбирая опции, которые используют новейший набор команд, заметно увеличивают скорость.


Были сопоставлены два компилятора в оптимизированном режиме: GCC 4.9.1 с использованием Netbeans IDS и Microsoft Visual Studio 2013 (Update 1) на одном и том же оборудовании. Количество итераций казалось последовательным, но относительное время выполнения удивительно отличалось.
boost::math::cbrt позволяет использовать с  любым типом плавающей точки, определенным пользователем, удобно Boost.Multiprecision. Он также может воспользоваться некоторым преимуществом хорошего поведения функции куба по сравнению с более общей реализацией в n-ых примерах поиска корней. Например, он использует полиномиальное приближение, чтобы генерировать лучшее предположение, чем деление экспоненты на три, и может избежать сложных проверок в итерации  Ньютона-Рафсона , необходимых для предотвращения резкого отклонения поиска. Для известной точности также может быть возможно зафиксировать количество итераций, позволяя вставлять и разворачивать петлю. Он также алгебраически упрощает шаги Галлея, что приводит к значительному сокращению количества операций с плавающей запятой по сравнению с реализацией «черного ящика», которая вычисляет производные отдельно, а затем объединяет их в коде Галлея. Как правило, было обнаружено, что вычисления с использованием типа double занимали в несколько раз больше времени при использовании различных алгоритмов непосредственного поиска корней, а не ручного кодирования / оптимизации cbrt.
Важность получения хорошей догадки можно увидеть по количеству итераций для многоточного случая: здесь мы немного «обманываем» и используем кубический корень, рассчитанный для удвоения точности в качестве начальной догадки. Ограничение этой тактики состоит в том, что диапазон возможных (экспонентных) значений может быть меньше многоточного типа.
Для фундаментальных типов было мало выбора между тремя производными методами, но для cpp_bin_float итерация Newton-Raphson была в два раза быстрее. Обратите внимание, что кубический корень является экстремальным тестовым случаем, поскольку стоимость вызова функтора настолько дешева, что во времени выполнения в значительной степени доминирует сложность кода итерации.
Компиляция с оптимизацией сократила вдвое время вычислений, и любые различия между алгоритмами стали почти незначительными. Особенно заметным было ускорение оптимизации алгоритма 748 TOMS: включение нулей непрерывных функций.
Использование многоточного типа, такого как cpp_bin_float_50, для точности 50 десятичных цифр заняло гораздо больше времени, как и ожидалось, потому что большинство вычислений использует программное обеспечение, а не 64-битное оборудование с плавающей запятой. Скорость часто более чем в 50 раз медленнее.
Используя cpp_bin_float_50, TOMS Алгоритм 748: включение нулей непрерывных функций было намного медленнее, показывая преимущество использования производных.  Итерация Ньютона-Рафсона  оказалась в два раза быстрее, чем любой из методов второго производного: это крайний случай, хотя функция и ее производные настолько дешевы для вычислений, что мы действительно измеряем сложность кода поиска корней.
Для многоточности типов для получения оставшихся 35 цифр, независимо от используемого алгоритма, требуется только одна или две дополнительные . (Время, конечно, было намного больше для этих типов).

Использование типа 100 десятичных цифр только удвоило время и потребовало еще нескольких итераций, поэтому стоимость дополнительной точности в основном лежит в основе затрат на вычисление большего количества цифр, а не в том, как работает алгоритм. Это подтверждает предыдущие наблюдения с использованием NTL A Library для выполнения теории чисел высокоточных типов.




          Program
          root_finding_algorithms.cpp, Microsoft Visual C++ version 12.0, Dinkumware
          standard library version 610, Win32, x64
 1000000 evaluations of each
          of 5 root_finding algorithms.
        

Table 12.1. Cube root(28) for float, double, long double and cpp_bin_float_50



























                  плавать






                  двойной






                  длинный






                  pp50



 
 



 Алгоритм 

 Его 

 Время 


                  
                    Norm
                  

 Дис 


 Его 

 Время 


                  
                    Norm
                  

 Дис 


 Его 

 Время 


                  
                    Norm
                  

 Дис 


 Его 

 Время 


                  
                    Norm
                  

 Дис 




 cbrt 


                  
                    0
                  

 46875 


                  
                    1.0
                  


                  
                    0
                  



                  
                    0
                  

 46875 


                  
                    1.0
                  

 1 



                  
                    0
                  

 46875 


                  
                    1.0
                  

 1 



                  
                    0
                  

 4906250 


                  
                    1.1
                  


                  
                    0
                  




 TOMS748 


                  
                    8
                  

 234375 


                  
                    5.0
                  

-1 


 11 

 437500 

 9.3 

 2 


 11 

 437500 

 9.3 

 2 


 7 


                  
                    66218750
                  

 15. 

 -2 




 Ньютон 

 5 


                  
                    109375
                  

 2.3 


                  
                    0
                  


 6 

 125000 

 2.7 


                  
                    0
                  


 6 

 140625 

 3.0 


                  
                    0
                  


 2 


                  
                    4531250
                  


                  
                    1.0
                  


                  
                    0
                  




 Галлей 

 3 

 125000 

 2.7 


                  
                    0
                  


 4 

 156250 

 3.3 


                  
                    0
                  


 4 

 156250 

 3.3 


                  
                    0
                  


 2 

 10625000 

 2.3 


                  
                    0
                  




 Schröder 

 4 

 140625 

 3.0 


                  
                    0
                  


 5 

 187500 

 4.0 


                  
                    0
                  


 5 

 203125 

 4.3 


                  
                    0
                  


 2 

 13109375 

 2.9 


                  
                    0
                  









          Program
          root_finding_algorithms.cpp, GNU C++ version 4.9.2, GNU libstdc++ version
          20141030, Win32, x64
 1000000 evaluations of each of 5 root_finding
          algorithms.
        

Table 12.2. Cube root(28) for float, double, long double and cpp_bin_float_50



























                  плавать






                  двойной






                  длинный






                  pp50



 
 



 Алгоритм 

 Его 

 Время 


                  
                    Norm
                  

 Дис 


 Его 

 Время 


                  
                    Norm
                  

 Дис 


 Его 

 Время 


                  
                    Norm
                  

 Дис 


 Его 

 Время 


                  
                    Norm
                  

 Дис 




 cbrt 


                  
                    0
                  

 46875 


                  
                    1.0
                  


                  
                    0
                  



                  
                    0
                  

 46875 


                  
                    1.0
                  


                  
                    0
                  



                  
                    0
                  

 46875 


                  
                    1.0
                  


                  
                    0
                  



                  
                    0
                  


                  
                    3500000
                  


                  
                    1.1
                  


                  
                    0
                  




 TOMS748 


                  
                    8
                  

 187500 

 4.0 

-1 


 11 

 406250 

 8.7 

 2 



                  
                    10
                  

 609375 

 13. 

-1 


 7 


                  
                    44531250
                  

 14. 

 -2 




 Ньютон 

 5 

 93750 


                  
                    2.0
                  


                  
                    0
                  


 6 


                  
                    109375
                  

 2.3 


                  
                    0
                  


 6 

 171875 

 3.7 


                  
                    0
                  


 2 


                  
                    3140625
                  


                  
                    1.0
                  

-1 




 Галлей 

 3 

 93750 


                  
                    2.0
                  


                  
                    0
                  


 4 

 125000 

 2.7 


                  
                    0
                  


 4 

 218750 

 4.7 


                  
                    0
                  


 2 

 7171875 

 2.3 


                  
                    0
                  




 Schröder 

 4 


                  
                    109375
                  

 2.3 


                  
                    0
                  


 5 

 171875 

 3.7 


                  
                    0
                  


 5 


                  
                    281250
                  

 6.0 


                  
                    0
                  


 2 

 8703125 


                  
                    2.8
                  


                  
                    0

Comparison of Cube Root Finding Algorithms

Boost , Math Toolkit 2.5.0 , Comparison of Root Finding Algorithms

Boost C++ Libraries

Comparison of Cube Root Finding Algorithms

Program root_finding_algorithms.cpp, Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, Win32, x64 1000000 evaluations of each of 5 root_finding algorithms.

Program root_finding_algorithms.cpp, GNU C++ version 4.9.2, GNU libstdc++ version 20141030, Win32, x64 1000000 evaluations of each of 5 root_finding algorithms.

Program root_finding_algorithms.cpp, Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, Win32, x64
1000000 evaluations of each of 5 root_finding algorithms.

Program root_finding_algorithms.cpp, GNU C++ version 4.9.2, GNU libstdc++ version 20141030, Win32, x64
1000000 evaluations of each of 5 root_finding algorithms.