正木です。

|[ruby-math:00577] Re: int / int -> ?
|From: keiju / ishitsuka.com (石塚圭樹)
|Integer.sqrtは高速に計算できそうですね. ビットシフトするだけだから.

具体的な algorithm を教えて下さい。こういうものがあれば、例えば
(27/8)**(2/3) #=> 9/4
のようにできると思ったのですが、下記の Isqrt,Iroot のような
とてもエレガントとは言えない方法しか思い付きませんでした。

----
Isqrt=Function.new({0=>0}){"|x| m=2 
    case x
    when Integer
      if x>0
        n=2*self[x>>m]
        ((n+1)**m>x)? n : n+1
      end
    when Rational
      self[x.numerator]/self[x.denominator]
    else
      nil
    end
  "}
Iroot=Sequence.new{"|m| 
   Function.new({0=>0,1=>1},m){'|x,m|
      if x<0 
        if m%2==0
          nil
        else
          -self[-x]
        end
      else
        case x
        when Integer
          n=2*self[x>>m]
          ((n+1)**m>x)? n : n+1
        when Rational
          self[x.numerator]/self[x.denominator]
        else
          nil
        end
      end
      '}"}
Sqrt=Function.new({0=>0}){"|x| 
  case x
    when Float
      sqrt(x)
    when Sequence2
      s=Sequence.new([],x){\"|n,x| Sqrt[x[n]].approx2(x.errorR[n]) \"}
      RealComplex.new(s,'W')
    else
      a=(x<0)? Complex::I : (x.type==Complex)? 1 : Isqrt[x]
      if a**2==x
        a
      else
        s=Sequence.new([a],x){\"|n,x| a=self[n-1];(a+x/a)/2 \"}.Shift
        error=Sequence.new([],x,s){\"|n,x,s| y=s[n];(y-x/y).abs1 \"}
        RealComplex.new(s,error)
      end
    end
  "}
Power=Function.new{"|x| 
  Sequence.new([1],x){\"|n,x| 
    if n%2==1
      x*self[n-1]
    else
      self[n/2]*self[n/2]
    end
    \"}"}
Exp=Function.new({0=>1}){"|x| 
    case x
    when Sequence2
      x=x.regular
      s=Sequence.new([],x){\"|n,x| ex=Exp[x[n]]
           ex.approx2(ex.abs1max[0]*(Exp[x.error[n]].abs1max[1]-1)) \"}
      RealComplex.new(s,'W')
    else
      if x.Float?
        exp(x)
      else
        n=Integer(2*x.abs1)
        RealComplex.new(ExpS[x].Sum.Shift(n),ExpS[x].abs1.Shift(n))
      end
    end
    "}
FPower=Function.new{"|x| 
    Function.new({},x){\"|y,x|
        case y
        when Integer
          if y >= 0
	    Power[x][y]
          elsif y < 0
	    1/Power[x][-y]
          end
        when 1/2
          Sqrt[x]
        when Rational
          if Iroot[y.denominator][x]**y.denominator==x
            Iroot[y.denominator][x]**y.numerator
          else
            Exp[Log[x]*y]
          end
        when Complex,Sequence2
          Exp[Log[x]*y]
        end
     \"}"}
class Integer,Rational,Complex
alias pow! **
  def **(y)
    x=self
    return Float(x) ** y if y.Float?
    case y
    when 2
      x*x
    when Integer
      if y >= 0
	Power[x][y]
      elsif y < 0
	1/Power[x][-y]
      end
    when Rational
      n=y.floor
      FPower[x][y-n]*x**n
    when Complex,Sequence2
      FPower[x][y]
    else
      a , b = y.coerce(x)
      a ** b
    end
  end
end
class Integer,Rational,Sequence2
  def Float?
    FALSE
  end
end
class Float
  def Float?
    TRUE
  end
end
class Complex
  def Float?
      real.type==Float || imag.type==Float
  end
end
class Integer,Rational,Float,Complex
  def abs1max
    Sequence.const(abs1)
  end
end
class NilClass
  def **(other)
    nil
  end
end
class Integer
  def gcd(n)
    return self if n==0
    n=n.abs
    n.gcd(self%n)
  end
end
-----

最後の gcd の変更で EulerConstant 60 桁の計算が 54sec から 27sec に
劇的に早くなりました。Bignum に対しては単純な方法の方が早い場合が
あるようです。
調べてみると、従来の gcd の中で
    n >>= 1 while n[0] == 0
の所が意外に時間を食うようです。
非常に極端な例をあげると
(2**1000000+1).gcd 2**1000000
は上の方法なら数十 ms で済むのに、従来の方法だと何時間もかかりそうです。