けいじゅ@日本ラショナルソフトウェアです.

In [ruby-math :00582 ] the message: "[ruby-math:00582] Re: int / int -
> ? ", on Aug/21 15:57(JST) IKEGAMI Daisuke writes:

>いけがみです。

>有理数ならば、むしろ 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 アルゴリズムで同時に高速に求まり
>ます。

これって, gcd(b, d), d/gcd(b, d), b/gcd(b, d) の三者ってことですよね? こ
ういうのが欲しいなって思っていたんですよ.

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

それは言えますね... 計算した後に、約分していますものね. 

>一方、有理多項式の場合は 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]
>のように、有理数と有理多項式を分けて扱います。

うーん. 一筋縄では行かないのね.

__
..............................石塚 圭樹@日本ラショナルソフトウェア...
----------------------------------->> e-mail: keiju / rational.com <<---