Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

連分數計算(Continued Fraction Evaluation)

概要

#include <boost/math/tools/fraction.hpp>

namespace boost{ namespace math{ namespace tools{

template <class Gen>
typename detail::fraction_traits<Gen>::result_type 
   continued_fraction_b(Gen& g, int bits);

template <class Gen>
typename detail::fraction_traits<Gen>::result_type 
   continued_fraction_b(Gen& g, int bits, boost::uintmax_t& max_terms);

template <class Gen>
typename detail::fraction_traits<Gen>::result_type 
   continued_fraction_a(Gen& g, int bits);
   
template <class Gen>
typename detail::fraction_traits<Gen>::result_type 
   continued_fraction_a(Gen& g, int bits, boost::uintmax_t& max_terms);
   
}}} // namespaces
說明

連分數是逼近的一種常見方法. 這些函數都計算用generator 類型參數描述的連分數。帶有"_a" 後綴的函數計算下面的分數(fraction):

帶有"_b" 後綴的函數計算下面的分數(fraction):

後一種形式更自然一些,因為它對應於連分數一般的定義,但請注意由生成器(generator)返回的第一個a 值被忽略了。另外,在連分數中開始的 ab 值對於剩餘的項具有不同的定義方程,這使得具有「_a」後綴的形式更加合適。

生成器(generator)的類型應當是滿足下列操作的函數對像:

表達式

說明

Gen::result_type

這個類型是調用 operator()的返回值的類型。這可以是一個算術類型,也可以是一個算術類型的 std::pair<> 。

g()

返回一個 Gen::result_type類型的對象。

每次調用這個操作符,返回下一對a和b值。或者,如果 result_type 是一個算術類型,那麼返回下一個b值,且所有的a值假定為1。

在所有的連分數計算函數中,參數bits 是結果中的bit精度,連分數的計算持續到最後一項的計算使得開始的bits 個bits沒有發生改變為止。

如果指定了可選的參數max_terms ,那麼不會進行超過max_terms 次對生成器(generator)的調用,並且在輸出的時候,max_terms 將被設置為實際調用的次數。這個特性在為連分數的收斂繪圖時很有用。

實現

在內部實現中,這些算法將會使用修正的 Lentz algorithm:參考 Numeric Recipes in C++, W. H. Press et all, chapter 5, (especially 5.2 Evaluation of continued fractions, p 175 - 179)瞭解更多信息,以及參考 W.J. 1976, Applied Optics, vol. 15, pp. 668-671。

例子

golden ratio phi = 1.618033989... 可以使用最簡單的連分數來計算:

我們開始定義生成函數(generator function):

template <class T>
struct golden_ratio_fraction
{
   typedef T result_type;
   
   result_type operator()
   {
      return 1;
   }
};

黃金分割點(golden ratio) 可以使用下面的方法計算到double精度:

continued_fraction_a(
   golden_ratio_fraction<double>(),
   std::numeric_limits<double>::digits);

當通過連分數來計算特殊函數的時候,定義a和b是很有常見的。 例如 tan 函數定義為:

因此,生成函數(generator function)可能像下面這樣:

template <class T>
struct tan_fraction
{
private:
   T a, b;
public:
   tan_fraction(T v)
      : a(-v*v), b(-1)
   {}

   typedef std::pair<T,T> result_type;

   std::pair<T,T> operator()()
   {
      b += 2;
      return std::make_pair(a, b);
   }
};

注意,如果連續從b項中減去,也就是這裡的情況,那麼由這個生成器函數(generator function)返回的所有的a項都是負數。tangent 函數現在可以通過下面的方法計算:

template <class T>
T tan(T a)
{
   tan_fraction<T> fract(a);
   return a / continued_fraction_b(fract, std::numeric_limits<T>::digits);
}

注意,這一次我們使用帶有"_b" 後綴版本的計算函數:因為它與所有的其它項都不同,所以在計算的過程中我們刪除了前導的a項。


PrevUpHomeNext