1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Estrin's method for polynomial evaluation</title>
<link rel="stylesheet" href="../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../poly.html" title="Chapter 12. Polynomials and Rational Functions">
<link rel="prev" href="polynomials.html" title="Polynomials">
<link rel="next" href="rational.html" title="Polynomial and Rational Function Evaluation">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="polynomials.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../poly.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rational.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="math_toolkit.estrin"></a><a class="link" href="estrin.html" title="Estrin's method for polynomial evaluation">Estrin's method for polynomial evaluation</a>
</h2></div></div></div>
<h5>
<a name="math_toolkit.estrin.h0"></a>
<span class="phrase"><a name="math_toolkit.estrin.synopsis"></a></span><a class="link" href="estrin.html#math_toolkit.estrin.synopsis">Synopsis</a>
</h5>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">estrin</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
</pre>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span> <span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">tools</span> <span class="special">{</span>
<span class="comment">// Advanced interface: Use if you can preallocate a scratch buffer of size (coeffs.size() +1)/2:</span>
<span class="comment">// The scratch buffer size is *unchecked* in release compiles, so use at your own risk!</span>
<span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">RandomAccessContainer1</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">RandomAccessContainer2</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">RealOrComplex</span><span class="special">></span>
<span class="keyword">inline</span> <span class="keyword">auto</span> <span class="identifier">evaluate_polynomial_estrin</span><span class="special">(</span><span class="identifier">RandomAccessContainer1</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">coeffs</span><span class="special">,</span> <span class="identifier">RandomAccessContainer2</span><span class="special">&</span> <span class="identifier">scratch</span><span class="special">,</span> <span class="identifier">RealOrComplex</span> <span class="identifier">z</span><span class="special">);</span>
<span class="comment">// Template specialization for std::array, no preallocation is necessary so massive performance improvements are typically observed:</span>
<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">RealOrComplex1</span><span class="special">,</span> <span class="identifier">size_t</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">RealOrComplex2</span><span class="special">></span>
<span class="keyword">inline</span> <span class="identifier">RealOrComplex2</span> <span class="identifier">evaluate_polynomial_estrin</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">RealOrComplex1</span><span class="special">,</span> <span class="identifier">n</span><span class="special">></span> <span class="special">&</span><span class="identifier">coeffs</span><span class="special">,</span> <span class="identifier">RealOrComplex2</span> <span class="identifier">z</span><span class="special">);</span>
<span class="special">}}}</span> <span class="comment">// namespaces</span>
</pre>
<h5>
<a name="math_toolkit.estrin.h1"></a>
<span class="phrase"><a name="math_toolkit.estrin.description"></a></span><a class="link" href="estrin.html#math_toolkit.estrin.description">Description</a>
</h5>
<p>
Boost.math provided free functions which evaluate polynomials by Estrin's method.
Though Estrin's method is not optimal from the standpoint of minimizing arithmetic
operations (that claim goes to Horner's method), it nonetheless is well-suited
to SIMD pipelines on modern CPUs. For example, on an 2022 M1 Pro, evaluating
a double precision polynomial of length N using Estrin's method with scratch
space takes 0.28 N nanoseconds for large N, whereas Horner's method takes 1.24
N ns. If you know your polynomial coefficients at compile time and can store
them in a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span></code>, then Estrin's method is unconditionally
faster. If the coefficients are computed at runtime, then only for N roughly
greater than 90 is Estrin's method better. These numbers are highly dependent
on compiler flags and architecture; ensure the compiler is allowed to emit
vector instructions and fmas to take full advantage of the benefits of Estrin's
method.
</p>
<p>
To measure the performance on your system, refer to the google benchmark file
<code class="computeroutput"><span class="identifier">reporting</span><span class="special">/</span><span class="identifier">performance</span><span class="special">/</span><span class="identifier">estrin_performance</span><span class="special">.</span><span class="identifier">cpp</span></code>.
</p>
<p>
Note that Estrin's method is less accurate that Horner's method. Refer to
<code class="computeroutput"><span class="identifier">example</span><span class="special">/</span><span class="identifier">estrin_vs_horner_accuracy</span><span class="special">.</span><span class="identifier">cpp</span></code> for details.
</p>
<p>
<span class="inlinemediaobject"><img src="../../graphs/horner_vs_estrin_accuracy.png"></span>
</p>
<h5>
<a name="math_toolkit.estrin.h2"></a>
<span class="phrase"><a name="math_toolkit.estrin.references"></a></span><a class="link" href="estrin.html#math_toolkit.estrin.references">References</a>
</h5>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
Muller, Jean-Michel (2005). Elementary Functions: Algorithms and Implementation
(2nd ed.). Birkhäuser. p. 58. ISBN 0-8176-4372-9.
</li></ul></div>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
Walker and Xiaogang Zhang<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="polynomials.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../poly.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rational.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
