Comparison of Elliptic Integral Root Finding Algoritghms . Boost , Math Toolkit 2.5.0 , Comparison of Root Finding Algorithms

Comparison of Elliptic Integral Root Finding Algoritghms

Второй пример сравнивает четыре алгоритма поиска корня для определения второго радиуса эллипса с первым радиусом 28 и длиной дуги 300, для четырех типов плавающих точек, float, ДП, long ДП и Boost.Multiprecision Тип cpp_bin_float_50<>.


То есть мы решаем:
4xE(sqrt(1 - 28² / x²)) - 300 = 0
В каждом случае точность цели была установлена с использованием наших «рекомендованных» пределов точности (или, по крайней мере, ограничений, которые делают хорошую отправную точку - что, вероятно, даст почти полную точность, не прибегая к ненужным итерациям).







                  Функция


                  Запрошенная точность




 TOMS748 


                  
                    numeric_limits<T>::digits - 2
                  



 Ньютон 

 этаж (цифровые_ограничения::цифры * 0,6) 



 Halley 

 этаж (цифровые_ограничения::цифры * 0,4) 




                  
                    Schröder
                  

 этаж (цифровые_ограничения::цифры * 0,4) 




Испытания использовали Microsoft Visual Studio 2013 (обновление 1) и GCC 4.9.1 с использованием исходного кода root_elliptic_finding.cpp.
Неопределенность времени (особенно с использованием MSVC) составляет не менее 5% от нормализованного времени «Norm».
Чтобы выбрать «лучшие» и «худшие» алгоритмы выделены синим и красным. Более одного результата может быть «лучшим», когда нормализованные времена неотличимы в неопределенности.


          Program
          root_elliptic_finding.cpp,
          Microsoft Visual C++ version 12.0, Dinkumware standard library version
          610, Win32 Compiled in optimise mode., _X86_SSE2
        

Table 12.12. root with radius 28 and arc length 300) for float, double, long
          double and cpp_bin_float_50 types, using _X86_SSE2



























                  плавание






                  двойной






                  д






                  cpp50



 
 




                  
                    Algo
                  

 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 




 TOMS748 

 5 

 515 

 1.43 

 -1 


 9 


                  
                    968
                  

 1.82 

 1 


 9 


                  
                    968
                  

 1.82 

 1 


 11 

 871875 

 1.53 

 -3 




 Ньютон 

 3 

 453 

 1.26 

 -1 


 4 

 640 

 1.21 

 1 


 4 

 640 

 1.21 

 1 


 5 


                  
                    685937
                  

 1.20 


                  
                    0
                  




 Halley 

 2 

 359 

 1.00 


                  
                    0
                  


 3 

 531 

 1.00 

 3 


 3 

 531 

 1.00 

 3 


 4 

 570312 

 1.00 


                  
                    0
                  





                  
                    Schröder
                  

 3 

 484 

 1.35 

 -1 


 6 

 1000 


                  
                    1.88
                  

 1 


 6 

 984 

 1.85 

 1 


 5 

 742187 

 1.30 

 -2 









          Program
          root_elliptic_finding.cpp,
          Microsoft Visual C++ version 12.0, Dinkumware standard library version
          610, Win32 Compiled in optimise mode., _X64_AVX
        

Table 12.13. root with radius 28 and arc length 300) for float, double, long
          double and cpp_bin_float_50 types, using _X64_AVX



























                  плавание






                  двойной






                  д






                  cpp50



 
 




                  
                    Algo
                  

 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 




 TOMS748 

 5 

 500 

 1.33 

 -1 


 9 

 1046 

 1.72 

 1 


 9 

 1062 

 1.70 

 1 


 11 

 698437 

 1.54 

 -3 




 Ньютон 

 3 

 484 

 1.29 

 -1 


 4 


                  
                    734
                  

 1.21 

 1 


 4 

 687 

 1.10 

 1 


 5 


                  
                    545312
                  

 1.20 


                  
                    0
                  




 Halley 

 2 

 375 

 1.00 


                  
                    0
                  


 3 

 609 

 1.00 

 3 


 3 

 625 

 1.00 

 3 


 4 

 453125 

 1.00 


                  
                    0
                  





                  
                    Schröder
                  

 3 

 546 

 1.46 

 -1 


 6 

 1109 

 1.82 

 1 


 6 


                  
                    1187
                  


                  
                    1.90
                  

 1 


 5 

 564062 

 1.24 

 -2 









          Program
          root_elliptic_finding.cpp,
          GNU C++ version 4.9.2, GNU libstdc++ version 20141030, Win32 Compiled in
          optimise mode., _X64_SSE2
        

Table 12.14. root with radius 28 and arc length 300) for float, double, long
          double and cpp_bin_float_50 types, using _X64_SSE2



























                  плавание






                  двойной






                  д






                  cpp50



 
 




                  
                    Algo
                  

 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 


 

 Times 

 Нормы 

 Dis 




 TOMS748 

 5 

 328 

 1.31 

 -1 


 8 

 875 

 1.51 


                  
                    0
                  


 8 

 1109 

 1.69 

 4 


 11 

 479687 

 1.49 

 -3 




 Ньютон 

 3 

 328 

 1.31 

 -1 


 4 

 671 

 1.16 

 1 


 4 

 781 

 1.19 

 1 


 5 

 387500 

 1.20 


                  
                    0
                  




 Halley 

 2 

 250 

 1.00 


                  
                    0
                  


 3 

 578 

 1.00 

 1 


 3 

 656 

 1.00 

 7 


 4 

 321875 

 1.00 


                  
                    0
                  





                  
                    Schröder
                  

 3 

 375 

 1.50 

 -1 


 4 


                  
                    734
                  

 1.27 


                  
                    0
                  


 4 

 828 

 1.26 

 3 


 5 

 414062 

 1.29 

 -2 







Замечания:

Разрешаемая функция теперь умеренно дорогая, и в два раза дороже звонить при получении производного, чем когда нет. Следовательно, очень мало улучшений в переходе от производного свободного метода к итерации Ньютона. Однако, как только вы рассчитали первое производное, второе приходит почти бесплатно, следовательно, методы третьего порядка (Halley) делают гораздо лучшее.
Из двух методов второго порядка Халли делает все возможное, как и ожидалось: метод Шродера предлагает лучшие гарантии quadratic конвергенции, в то время как Halley полагается на гладкую функцию с одним корнем, чтобы дать cubic конвергенции. Не совсем ясно, почему итерация Шродера часто делает хуже, чем Ньютон.

Comparison of Elliptic Integral Root Finding Algoritghms

Boost , Math Toolkit 2.5.0 , Comparison of Root Finding Algorithms

Boost C++ Libraries

Comparison of Elliptic Integral Root Finding Algoritghms

Program root_elliptic_finding.cpp, Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, Win32 Compiled in optimise mode., _X86_SSE2

Program root_elliptic_finding.cpp, Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, Win32 Compiled in optimise mode., _X64_AVX

Program root_elliptic_finding.cpp, GNU C++ version 4.9.2, GNU libstdc++ version 20141030, Win32 Compiled in optimise mode., _X64_SSE2