原です。

>いけがみです。

>分数の掛け算
>    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) が早く計算できます。

なるほど!やっぱり割れるときに割っておいた方が効率いいみたい
ですね。

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

やっぱり、こっちもこまめに gcd で割っておいた方がいいかもしれな
いですね。同じ理由で。

>Mathematica では、
>   1/2 = Rational[1, 2], 2/4 => 1/2 (ただちに約分)

2/4 の表示が 1/2 になったからといって、ただちに約分したと
はいえない(表示を求めたれたから約分したのかも)と思うの
だけど、いけがみさんの計算を見ると、やはりただちに約分し
てるのでしょう。


>d/gcd(b, d), b/gcd(b, d) は拡張 Euclid アルゴリズムで同時に高速に求まります。

拡張 Euclid アルゴリズムというの gcd(b, d) を求めると同時に

   x * b + y * d = gcd(b, d)

となる x, y を求めるものですよね。これが d/gcd(b, d), b/gcd(b, d)
と結びつきます?