// (C) Copyright John Maddock 2005-2006. | |
// Use, modification and distribution are subject to the | |
// Boost Software License, Version 1.0. (See accompanying file | |
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
#ifndef BOOST_MATH_TOOLS_FRACTION_INCLUDED | |
#define BOOST_MATH_TOOLS_FRACTION_INCLUDED | |
#ifdef _MSC_VER | |
#pragma once | |
#endif | |
#include <boost/config/no_tr1/cmath.hpp> | |
#include <boost/cstdint.hpp> | |
#include <boost/type_traits/integral_constant.hpp> | |
#include <boost/mpl/if.hpp> | |
#include <boost/math/tools/precision.hpp> | |
namespace boost{ namespace math{ namespace tools{ | |
namespace detail | |
{ | |
template <class T> | |
struct is_pair : public boost::false_type{}; | |
template <class T, class U> | |
struct is_pair<std::pair<T,U> > : public boost::true_type{}; | |
template <class Gen> | |
struct fraction_traits_simple | |
{ | |
typedef typename Gen::result_type result_type; | |
typedef typename Gen::result_type value_type; | |
static result_type a(const value_type& v) | |
{ | |
return 1; | |
} | |
static result_type b(const value_type& v) | |
{ | |
return v; | |
} | |
}; | |
template <class Gen> | |
struct fraction_traits_pair | |
{ | |
typedef typename Gen::result_type value_type; | |
typedef typename value_type::first_type result_type; | |
static result_type a(const value_type& v) | |
{ | |
return v.first; | |
} | |
static result_type b(const value_type& v) | |
{ | |
return v.second; | |
} | |
}; | |
template <class Gen> | |
struct fraction_traits | |
: public boost::mpl::if_c< | |
is_pair<typename Gen::result_type>::value, | |
fraction_traits_pair<Gen>, | |
fraction_traits_simple<Gen> >::type | |
{ | |
}; | |
} // namespace detail | |
// | |
// continued_fraction_b | |
// Evaluates: | |
// | |
// b0 + a1 | |
// --------------- | |
// b1 + a2 | |
// ---------- | |
// b2 + a3 | |
// ----- | |
// b3 + ... | |
// | |
// Note that the first a0 returned by generator Gen is disarded. | |
// | |
template <class Gen, class U> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_b(Gen& g, const U& factor, boost::uintmax_t& max_terms) | |
{ | |
BOOST_MATH_STD_USING // ADL of std names | |
typedef detail::fraction_traits<Gen> traits; | |
typedef typename traits::result_type result_type; | |
typedef typename traits::value_type value_type; | |
result_type tiny = tools::min_value<result_type>(); | |
value_type v = g(); | |
result_type f, C, D, delta; | |
f = traits::b(v); | |
if(f == 0) | |
f = tiny; | |
C = f; | |
D = 0; | |
boost::uintmax_t counter(max_terms); | |
do{ | |
v = g(); | |
D = traits::b(v) + traits::a(v) * D; | |
if(D == 0) | |
D = tiny; | |
C = traits::b(v) + traits::a(v) / C; | |
if(C == 0) | |
C = tiny; | |
D = 1/D; | |
delta = C*D; | |
f = f * delta; | |
}while((fabs(delta - 1) > factor) && --counter); | |
max_terms = max_terms - counter; | |
return f; | |
} | |
template <class Gen, class U> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_b(Gen& g, const U& factor) | |
{ | |
boost::uintmax_t max_terms = (std::numeric_limits<boost::uintmax_t>::max)(); | |
return continued_fraction_b(g, factor, max_terms); | |
} | |
template <class Gen> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_b(Gen& g, int bits) | |
{ | |
BOOST_MATH_STD_USING // ADL of std names | |
typedef detail::fraction_traits<Gen> traits; | |
typedef typename traits::result_type result_type; | |
result_type factor = ldexp(1.0f, 1 - bits); // 1 / pow(result_type(2), bits); | |
boost::uintmax_t max_terms = (std::numeric_limits<boost::uintmax_t>::max)(); | |
return continued_fraction_b(g, factor, max_terms); | |
} | |
template <class Gen> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_b(Gen& g, int bits, boost::uintmax_t& max_terms) | |
{ | |
BOOST_MATH_STD_USING // ADL of std names | |
typedef detail::fraction_traits<Gen> traits; | |
typedef typename traits::result_type result_type; | |
result_type factor = ldexp(1.0f, 1 - bits); // 1 / pow(result_type(2), bits); | |
return continued_fraction_b(g, factor, max_terms); | |
} | |
// | |
// continued_fraction_a | |
// Evaluates: | |
// | |
// a1 | |
// --------------- | |
// b1 + a2 | |
// ---------- | |
// b2 + a3 | |
// ----- | |
// b3 + ... | |
// | |
// Note that the first a1 and b1 returned by generator Gen are both used. | |
// | |
template <class Gen, class U> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_a(Gen& g, const U& factor, boost::uintmax_t& max_terms) | |
{ | |
BOOST_MATH_STD_USING // ADL of std names | |
typedef detail::fraction_traits<Gen> traits; | |
typedef typename traits::result_type result_type; | |
typedef typename traits::value_type value_type; | |
result_type tiny = tools::min_value<result_type>(); | |
value_type v = g(); | |
result_type f, C, D, delta, a0; | |
f = traits::b(v); | |
a0 = traits::a(v); | |
if(f == 0) | |
f = tiny; | |
C = f; | |
D = 0; | |
boost::uintmax_t counter(max_terms); | |
do{ | |
v = g(); | |
D = traits::b(v) + traits::a(v) * D; | |
if(D == 0) | |
D = tiny; | |
C = traits::b(v) + traits::a(v) / C; | |
if(C == 0) | |
C = tiny; | |
D = 1/D; | |
delta = C*D; | |
f = f * delta; | |
}while((fabs(delta - 1) > factor) && --counter); | |
max_terms = max_terms - counter; | |
return a0/f; | |
} | |
template <class Gen, class U> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_a(Gen& g, const U& factor) | |
{ | |
boost::uintmax_t max_iter = (std::numeric_limits<boost::uintmax_t>::max)(); | |
return continued_fraction_a(g, factor, max_iter); | |
} | |
template <class Gen> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_a(Gen& g, int bits) | |
{ | |
BOOST_MATH_STD_USING // ADL of std names | |
typedef detail::fraction_traits<Gen> traits; | |
typedef typename traits::result_type result_type; | |
result_type factor = ldexp(1.0f, 1-bits); // 1 / pow(result_type(2), bits); | |
boost::uintmax_t max_iter = (std::numeric_limits<boost::uintmax_t>::max)(); | |
return continued_fraction_a(g, factor, max_iter); | |
} | |
template <class Gen> | |
inline typename detail::fraction_traits<Gen>::result_type continued_fraction_a(Gen& g, int bits, boost::uintmax_t& max_terms) | |
{ | |
BOOST_MATH_STD_USING // ADL of std names | |
typedef detail::fraction_traits<Gen> traits; | |
typedef typename traits::result_type result_type; | |
result_type factor = ldexp(1.0f, 1-bits); // 1 / pow(result_type(2), bits); | |
return continued_fraction_a(g, factor, max_terms); | |
} | |
} // namespace tools | |
} // namespace math | |
} // namespace boost | |
#endif // BOOST_MATH_TOOLS_FRACTION_INCLUDED | |