]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // (C) Copyright John Maddock 2006. |
2 | // Use, modification and distribution are subject to the | |
3 | // Boost Software License, Version 1.0. (See accompanying file | |
4 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | #ifndef BOOST_MATH_SF_CBRT_HPP | |
7 | #define BOOST_MATH_SF_CBRT_HPP | |
8 | ||
9 | #ifdef _MSC_VER | |
10 | #pragma once | |
11 | #endif | |
12 | ||
13 | #include <boost/math/tools/rational.hpp> | |
14 | #include <boost/math/policies/error_handling.hpp> | |
15 | #include <boost/math/special_functions/math_fwd.hpp> | |
16 | #include <boost/math/special_functions/fpclassify.hpp> | |
17 | #include <boost/mpl/divides.hpp> | |
18 | #include <boost/mpl/plus.hpp> | |
19 | #include <boost/mpl/if.hpp> | |
20 | #include <boost/type_traits/is_convertible.hpp> | |
21 | ||
22 | namespace boost{ namespace math{ | |
23 | ||
24 | namespace detail | |
25 | { | |
26 | ||
27 | struct big_int_type | |
28 | { | |
29 | operator boost::uintmax_t()const; | |
30 | }; | |
31 | ||
32 | template <class T> | |
33 | struct largest_cbrt_int_type | |
34 | { | |
35 | typedef typename mpl::if_< | |
36 | boost::is_convertible<big_int_type, T>, | |
37 | boost::uintmax_t, | |
38 | unsigned int | |
39 | >::type type; | |
40 | }; | |
41 | ||
42 | template <class T, class Policy> | |
43 | T cbrt_imp(T z, const Policy& pol) | |
44 | { | |
45 | BOOST_MATH_STD_USING | |
46 | // | |
47 | // cbrt approximation for z in the range [0.5,1] | |
48 | // It's hard to say what number of terms gives the optimum | |
49 | // trade off between precision and performance, this seems | |
50 | // to be about the best for double precision. | |
51 | // | |
52 | // Maximum Deviation Found: 1.231e-006 | |
53 | // Expected Error Term: -1.231e-006 | |
54 | // Maximum Relative Change in Control Points: 5.982e-004 | |
55 | // | |
56 | static const T P[] = { | |
57 | static_cast<T>(0.37568269008611818), | |
58 | static_cast<T>(1.3304968705558024), | |
59 | static_cast<T>(-1.4897101632445036), | |
60 | static_cast<T>(1.2875573098219835), | |
61 | static_cast<T>(-0.6398703759826468), | |
62 | static_cast<T>(0.13584489959258635), | |
63 | }; | |
64 | static const T correction[] = { | |
65 | static_cast<T>(0.62996052494743658238360530363911), // 2^-2/3 | |
66 | static_cast<T>(0.79370052598409973737585281963615), // 2^-1/3 | |
67 | static_cast<T>(1), | |
68 | static_cast<T>(1.2599210498948731647672106072782), // 2^1/3 | |
69 | static_cast<T>(1.5874010519681994747517056392723), // 2^2/3 | |
70 | }; | |
71 | ||
72 | if(!(boost::math::isfinite)(z)) | |
73 | { | |
74 | return policies::raise_domain_error("boost::math::cbrt<%1%>(%1%)", "Argument to function must be finite but got %1%.", z, pol); | |
75 | } | |
76 | ||
77 | int i_exp, sign(1); | |
78 | if(z < 0) | |
79 | { | |
80 | z = -z; | |
81 | sign = -sign; | |
82 | } | |
83 | if(z == 0) | |
84 | return 0; | |
85 | ||
86 | T guess = frexp(z, &i_exp); | |
87 | int original_i_exp = i_exp; // save for later | |
88 | guess = tools::evaluate_polynomial(P, guess); | |
89 | int i_exp3 = i_exp / 3; | |
90 | ||
91 | typedef typename largest_cbrt_int_type<T>::type shift_type; | |
92 | ||
93 | BOOST_STATIC_ASSERT( ::std::numeric_limits<shift_type>::radix == 2); | |
94 | ||
95 | if(abs(i_exp3) < std::numeric_limits<shift_type>::digits) | |
96 | { | |
97 | if(i_exp3 > 0) | |
98 | guess *= shift_type(1u) << i_exp3; | |
99 | else | |
100 | guess /= shift_type(1u) << -i_exp3; | |
101 | } | |
102 | else | |
103 | { | |
104 | guess = ldexp(guess, i_exp3); | |
105 | } | |
106 | i_exp %= 3; | |
107 | guess *= correction[i_exp + 2]; | |
108 | // | |
109 | // Now inline Halley iteration. | |
110 | // We do this here rather than calling tools::halley_iterate since we can | |
111 | // simplify the expressions algebraically, and don't need most of the error | |
112 | // checking of the boilerplate version as we know in advance that the function | |
113 | // is well behaved... | |
114 | // | |
115 | typedef typename policies::precision<T, Policy>::type prec; | |
116 | typedef typename mpl::divides<prec, mpl::int_<3> >::type prec3; | |
117 | typedef typename mpl::plus<prec3, mpl::int_<3> >::type new_prec; | |
118 | typedef typename policies::normalise<Policy, policies::digits2<new_prec::value> >::type new_policy; | |
119 | // | |
120 | // Epsilon calculation uses compile time arithmetic when it's available for type T, | |
121 | // otherwise uses ldexp to calculate at runtime: | |
122 | // | |
123 | T eps = (new_prec::value > 3) ? policies::get_epsilon<T, new_policy>() : ldexp(T(1), -2 - tools::digits<T>() / 3); | |
124 | T diff; | |
125 | ||
126 | if(original_i_exp < std::numeric_limits<T>::max_exponent - 3) | |
127 | { | |
128 | // | |
129 | // Safe from overflow, use the fast method: | |
130 | // | |
131 | do | |
132 | { | |
133 | T g3 = guess * guess * guess; | |
134 | diff = (g3 + z + z) / (g3 + g3 + z); | |
135 | guess *= diff; | |
136 | } | |
137 | while(fabs(1 - diff) > eps); | |
138 | } | |
139 | else | |
140 | { | |
141 | // | |
142 | // Either we're ready to overflow, or we can't tell because numeric_limits isn't | |
143 | // available for type T: | |
144 | // | |
145 | do | |
146 | { | |
147 | T g2 = guess * guess; | |
148 | diff = (g2 - z / guess) / (2 * guess + z / g2); | |
149 | guess -= diff; | |
150 | } | |
151 | while((guess * eps) < fabs(diff)); | |
152 | } | |
153 | ||
154 | return sign * guess; | |
155 | } | |
156 | ||
157 | } // namespace detail | |
158 | ||
159 | template <class T, class Policy> | |
160 | inline typename tools::promote_args<T>::type cbrt(T z, const Policy& pol) | |
161 | { | |
162 | typedef typename tools::promote_args<T>::type result_type; | |
163 | typedef typename policies::evaluation<result_type, Policy>::type value_type; | |
164 | return static_cast<result_type>(detail::cbrt_imp(value_type(z), pol)); | |
165 | } | |
166 | ||
167 | template <class T> | |
168 | inline typename tools::promote_args<T>::type cbrt(T z) | |
169 | { | |
170 | return cbrt(z, policies::policy<>()); | |
171 | } | |
172 | ||
173 | } // namespace math | |
174 | } // namespace boost | |
175 | ||
176 | #endif // BOOST_MATH_SF_CBRT_HPP | |
177 | ||
178 | ||
179 | ||
180 |