いけがみです。

[ruby-math:00576] 原さん:
>ちょっと話それるけど、rational.rb では計算するたびに約分してます
>よね。もしかすると、ある程度分子と分母が大きくなってからとか、表
>示する時に約分する事にするとパフォーマンスが上がるってことありま
>せんかね。

有理数ならば、むしろ gcd 計算をこまめにしたほうが効率があがると思います。
少なくとも、有理数の四則演算の前に gcd を計算した方がいいと思います。

分数の掛け算
   p/q := a/b * c/d 
において、 a/b, c/d がすでに既約だったら
   gcd(a * c, b * d) = gcd(a, d) * gcd(b, c)
が成り立ちますから、
左辺から gcd (p, q) を計算するより右辺のほうが早いです。
(a, b, c, d が a * c, b * d よりも小さいので)

分数の足し算においても
   p/q := a/b + c/d
において、a/b, c/d が既約のほうが p, q が膨れ上がらずに済みます。
このとき、
  p = a * d + b * c, q = b * d
から、 gcd(p, q) を計算するよりも、
  p = a * (d/gcd(b, d)) + c * (b/gcd(b, d))
  q = b * d/gcd(b, d)
で p, q を計算したほうが、gcd(p, q) が早く計算できます。
d/gcd(b, d), b/gcd(b, d) は拡張 Euclid アルゴリズムで同時に高速に求まります。

現在の rational.rb はこの点で改善できます。

この話は、
J.H.Davenport, Y.Siret and E.Tournier, 
``Computer Algebra -- Systems and Algorithms for Algebraic Computation'',
2nd edit., Academic Press, 1993, p.77 Sec. 2.2
に載ってました。

一方、有理多項式の場合は gcd の計算に時間がかかるので、
原さんの言う通り、約分は後に回した方がいいと思います。

Mathematica では、
  1/2 = Rational[1, 2], 2/4 => 1/2 (ただちに約分)
  1/x = Power[x, -1]
  (x + 1)/(x + 2) = (x + 1) * Power[x + 2, -1]
のように、有理数と有理多項式を分けて扱います。
--
池上 大介
Daisuke IKEGAMI <daisu-ik / is.aist-nara.ac.jp>
奈良先端科学技術大学院大学 情報科学研究科
情報処理学専攻 情報基礎学講座 関研究室