Карта сайта Kansoftware
НОВОСТИУСЛУГИРЕШЕНИЯКОНТАКТЫ
Разработка программного обеспечения

Comparison of Nth-root Finding Algorithms

Boost , Math Toolkit 2.5.0 , Comparison of Root Finding Algorithms

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Второй пример сравнивает четыре обобщенных алгоритма поиска n-корня для различных n-корней (5, 7 и 13) одного значения 28,0 для четырех типов плавающих точек<float>,<double>,<long double>иBoost.Multiprecision.Тип<cpp_bin_float_50>. В каждом случае точность цели была установлена с использованием наших «рекомендуемых» пределов точности (или, по крайней мере, пределов, которые являются хорошей отправной точкой, что, вероятно, даст почти полную точность, не прибегая к ненужным итерациям).

Функция

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

TOMS748

numeric_limits::цифры - 2

Ньютон

этаж (число_лимиты:: цифры * 0,6)

Галлей

этаж (число_лимиты:: цифры * 0.4)

Schröder

этаж (число_лимиты:: цифры * 0.4)

В тестах использовались Microsoft Visual Studio 2013 (Update 1) и GCC 4.9.1 с использованием исходного кодаroot_n_finding_algorithms.cpp.

Неопределенность времени (особенно при использовании MSVC) составляет не менее 5% от нормированного времени.

Чтобы выбрать «лучшие» и «худшие» алгоритмы выделены синим и красным цветом. Более чем один результат может быть «лучшим», когда нормализованные времена неразличимы в пределах неопределенности.

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

Фракция полной точности 1

Table 12.3. 5th root(28) for float, double, long double and cpp_bin_float_50 types, using _X86_SSE2

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

7

320

1.53

0

11

576

2.61

1

11

557

2.48

1

12

119843

7.52

0

Ньютон

3

209

1.00

0

4

221

1.00

-1

4

225

1.00

-1

6

15937

1.00

0

Галлей

2

214

1.02

0

3

256

1.16

0

3

243

1.08

0

4

28437

1.78

0

Schröder

2

218

1.04

0

3

245

1.11

-1

3

245

1.09

-1

4

35625

2.24

0


Table 12.4. 7th root(28) for float, double, long double and cpp_bin_float_50 types, using _X86_SSE2

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

12

493

2.18

1

15

762

3.05

2

15

765

3.08

2

14

157343

7.09

0

Ньютон

5

226

1.00

0

6

250

1.00

0

6

248

1.00

0

8

22187

1.00

0

Галлей

4

257

1.14

0

5

293

1.17

0

5

293

1.18

0

6

44062

1.99

0

Schröder

5

285

1.26

0

6

317

1.27

0

6

317

1.28

0

7

61406

2.77

0


Table 12.5. 11th root(28) for float, double, long double and cpp_bin_float_50 types, using _X86_SSE2

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

12

556

2.24

-2

14

784

2,94

2

14

793

2,94

2

17

235781

8.88

2

Ньютон

6

248

1.00

0

7

267

1.00

0

7

270

1.00

0

9

26562

1.00

0

Галлей

4

254

1.02

-1

5

290

1.09

0

5

293

1.09

0

6

46406

1,75

0

Schröder

6

312

1.26

0

7

351

1.31

0

7

356

1.32

0

8

76250

2.87

0


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

Фракция полной точности 1

Table 12.6. 5th root(28) for float, double, long double and cpp_bin_float_50 types, using _X64_AVX

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

7

239

1.50

0

11

451

2.53

1

11

439

2.49

1

12

90312

7.51

0

Ньютон

3

159

1.00

0

4

178

1.00

-1

4

176

1.00

-1

6

12031

1.00

0

Галлей

2

168

1.06

0

3

203

1.14

0

3

198

1.13

0

4

20937

1.74

0

Schröder

2

173

1.09

0

3

206

1.16

-1

3

203

1.15

-1

4

26250

2.18

0


Table 12.7. 7th root(28) for float, double, long double and cpp_bin_float_50 types, using _X64_AVX

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

12

385

2.19

1

15

635

3.13

2

15

621

3.17

2

14

114843

6.81

0

Ньютон

5

176

1.00

0

6

203

1.00

0

6

196

1.00

0

8

16875

1.00

0

Галлей

4

209

1.19

0

5

254

1.25

0

5

246

1.26

0

6

32343

1,92

0

Schröder

5

223

1.27

0

6

273

1.34

0

6

275

1.40

0

7

45156

2.68

0


Table 12.8. 11th root(28) for float, double, long double and cpp_bin_float_50 types, using _X64_AVX

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

12

467

2,42

-2

14

648

3.06

2

14

640

2.99

2

17

170000

8,85

2

Ньютон

6

193

1.00

0

7

212

1.00

0

7

214

1.00

0

9

19218

1.00

0

Галлей

4

209

1.08

-1

5

256

1.21

0

5

250

1.17

0

6

32656

1,70

0

Schröder

6

248

1.28

0

7

306

1.44

0

7

298

1.39

0

8

53437

2.78

0


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

Фракция полной точности 1

Table 12.9. 5th root(28) for float, double, long double and cpp_bin_float_50 types, using _X64_SSE2

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

7

193

2.14

0

11

432

3.86

1

9

579

3,83

0

12

59062

7.56

0

Ньютон

3

90

1.00

0

4

112

1.00

-1

5

151

1.00

0

6

7812

1.00

0

Галлей

2

98

1.09

0

3

135

1.21

0

3

201

1.33

0

4

13750

1.76

0

Schröder

2

112

1.24

0

3

142

1.27

-1

3

206

1.36

0

4

17031

2.18

0


Table 12.10. 7th root(28) for float, double, long double and cpp_bin_float_50 types, using _X64_SSE2

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

12

351

1.97

1

15

621

3.18

2

13

906

3.61

0

14

75468

7.10

0

Ньютон

5

178

1.00

0

6

195

1.00

0

7

251

1.00

0

8

10625

1.00

0

Галлей

4

196

1.10

0

5

242

1.24

0

5

345

1.37

0

6

21093

1.99

0

Schröder

5

225

1.26

0

6

270

1.38

0

6

384

1.53

0

7

29062

2,74

0


Table 12.11. 11th root(28) for float, double, long double and cpp_bin_float_50 types, using _X64_SSE2

плавать

двойной

длинный

pp50

    

Алго

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

Его

Время

Norm

Дис

TOMS748

12

429

2.22

-2

14

679

3.02

2

14

1098

3.94

1

17

114531

8.83

2

Ньютон

6

193

1.00

0

7

225

1.00

0

7

279

1.00

0

9

12968

1.00

0

Галлей

4

196

1.02

-1

5

248

1.10

0

5

348

1.25

0

6

21718

1.67

0

Schröder

6

254

1.32

0

7

323

1.44

0

7

453

1.62

0

8

35625

2,75

0


Из этого ограниченного упражнения можно сделать некоторые предварительные выводы.

  • Возможно, удивительно, что между различными алгоритмами дляфундаментальных типовсуществует небольшая разница. Использование первых производныхитерации Ньютона-Рафсонаобычно является лучшим, но в то время как улучшение по сравнению с непроизводнымалгоритмом 748 TOMS: включение нулей непрерывных функцийзначительно по количеству итераций, но мало по времени выполнения. Это отражает тот факт, что функция, для которой мы находим корень, является тривиальной для оценки, поэтому во времени выполнения преобладает время, взятое кодом boilerplate в каждом методе.
  • Дополнительные затраты на оценку вторых производныхHalleyилиSchröderобычно слишком велики для какой-либо чистой выгоды: как и в случае с кубическим корнем, эти функторы настолько дешевы для оценки, что во времени выполнения в значительной степени доминирует сложность метода поиска корня.
  • ДляBoost.Multiprecisionтипа с плавающей запятой итерацияНьютона-Рафсонаявляется явным победителем с многократным увеличением. Алгоритм TOMS 748: включающий нули непрерывных функций, и снова не улучшающий алгоритмы второго производного.
  • Время выполнения 50 десятичных цифрBoost.Multiprecisionпримерно в 30 раз больше, чем<double>.
  • Колонка «dis» показывает количество битов, удаленных от правильного результата. Алгоритм Ньютона-Рафсона показывает немного лучшую точность, чем. TOMS Алгоритм 748: включающий нули непрерывных функций.
  • Доброта «угадывания» особенно важна дляBoost.Multiprecision. Отдельные эксперименты показывают, что оценка «угадывания» с помощью<double>позволяет сходимость к конечному точному результату в одной или двух итерациях. Поэтому в этом надуманном примере, грубо разделив показатель на N для «угадывания», было бы гораздо лучше использовать функцию<pow<double>>или, если точнее,<pow<longdouble>>для оценки «угадывания». Ограничение этой тактики состоит в том, что диапазон возможных (экспонентных) значений может быть меньше многоточного типа.
  • Используя расширение с плавающей запятой, инструкции SSE2сделали небольшое ускорение на десять процентов.
  • Используя MSVC, было некоторое улучшение с использованием 64-разрядного, заметно дляBoost.Multiprecision.
  • Компилятор GCC 4.9.1, использующий 64-разрядный процессор, был как минимум в пять раз быстрее 32-разрядного, что, по-видимому, отражает лучшую оптимизацию.

Очевидно, что ваш пробегбудет варьироваться, но в целомитерация Ньютона-Рафсонакажется первым выбором алгоритма и попыткой найти хорошую «угадку» первой цели ускорения, особенно дляBoost.Multiprecision. И, конечно же, оптимизация компилятора имеет решающее значение для скорости.

Copyright © 2006-2010, 2012-2014 Nikhar Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan Råde, Gautam Sewani, Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang

Распространяется под лицензией Boost Software License, версия 1.0. (См. сопроводительный файл LICENSE_1_0.txt или копию по адресу) http://www.boost.org/LICENSE_1_0.txt
PrevUpHomeNext

Статья Comparison of Nth-root Finding Algorithms раздела Math Toolkit 2.5.0 Comparison of Root Finding Algorithms может быть полезна для разработчиков на c++ и boost.




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


:: Главная :: Comparison of Root Finding Algorithms ::

реклама
©KANSoftWare (разработка программного обеспечения, создание программ, создание интерактивных сайтов), 2007
Top.Mail.Ru

Время компиляции файла: 2024-08-30 11:47:00
2025-07-05 05:44:07/0.0074789524078369/0