连分数适合当数据类型么？

zeroieme · 发表于 2012-2-27 00:39:13

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

最近看到连分数在一些数值计算上的优势，但却找不到连分数直接进行加减乘除的方法。
难道要算回普通分数再进行？难道连分数只适合存在于算法中间某点？

liangbch · 发表于 2012-2-27 10:33:21

如果想使用连分数作为一种变量类型，它至少应该能够
  1.方便的连分数的四则运算的实现
  2.能够方便得和其他数据类型进行运算，如它和整数进行4则运算
  3.能够方便的转为为其他数据类型，如转化为普通分数，转化为double，转化为高精度浮点浮点类型，如GMP中的浮点数。

liangbch · 发表于 2012-2-28 12:03:19

连分数作为基本类型，或许是可行的，不过我不建议这样做，在许多方面，用连分数作为变量类型都显得太复杂了。
在 mathworld的continued fraction 条目中，有如下描述
   Gosper has invented an algorithm for performing analytic addition, subtraction, multiplication, and division using continued fractions. It requires keeping track of eight integers which are conceptually arranged at the polyhedron vertices of a cube. Although this algorithm has not appeared in print, similar algorithms have been constructed by Vuillemin (1987) and Liardet and Stambul (1998).
      Gosper's algorithm for computing the continued fraction for (ax+b)/(cx+d) from the continued fraction for  x is described by Gosper (1972), Knuth (1998, Exercise 4.5.3.15, pp. 360 and 601), and Fowler (1999). (In line 9 of Knuth's solution, $x_k larr min(|__A//C__|)$
should be replaced by $x_k larr min(|__A//C__|,|__(A+B)//(C+D)__|)$ Gosper (1972) and Knuth (1981) also mention the bivariate case $(axy+bx+cy+d)//(Axy+Bx+Cy+D)$
      不过，从这段摘要性的内容，我并没有搞明白其具体实现，如果你有兴趣，可研读之。

zeroieme · 发表于 2012-2-28 12:34:47

3# liangbch

先行感谢，我看看去。

wayne · 发表于 2012-2-28 15:42:13

4# zeroieme
搜了一下 liangbch 说的 Gosper's Algorithm ，
找到了这个链接，很全：
http://pauljmccarthy.us/Cfrac/CF_Arithmetic.htm

以及这个pdf
http://hal.inria.fr/docs/00/07/57/92/PDF/RR-0760.pdf

wayne · 发表于 2012-2-28 16:05:14

搜Continued Fraction Arithmetic，更好！！
http://perl.plover.com/yak/cftalk/
http://contfrac.sourceforge.net/
http://library.wolfram.com/infocenter/Articles/2782/
发现1999年有人以此作为博士论文了：
http://lists.canonical.org/piper ... ebruary/000095.html

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 连分数适合当数据类型么？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。