From: masaki <GEC01122@...>
Date: 2003-01-27T01:21:28+09:00
Subject: [ruby-dev:19441] Integer#gcd


正木です。

Integer の method 追加の要望です。

最大公約数 gcd はかなり需要があると思うので Integer#gcd を
組み込みにしてもらえませんか？
（あるいは Integer.gcd(m,n) といった形でもいいですが）


それから以下の２つは、必要と思う人がどれくらいいるかは分りませんが
一応要望だけ出しておきます。
平方根の floor を返す method
m 乗根の floor を返す method 

私はとりあえず次のような拡張 library で代用しています：

-----
#include "ruby.h"

static VALUE
gcd(VALUE self,VALUE m,VALUE n)
{
    if(FIXNUM_P(n) && FIX2INT(n)==0) return m;
    return gcd(self,n,rb_funcall(m,'%',1, n));
}

static int
int_sqrt0(int i)
{
  int j;
  if(i==0) return 0;
  j=2*int_sqrt0(i>>2);
  if((j+1)*(j+1)>i) return j;
  return j+1;
}

static VALUE
int_sqrt(VALUE self,VALUE n)
{
  int i;
  VALUE j,k,k1;
    switch (TYPE(n)) {
    case T_FIXNUM:
      i = FIX2INT(n);
      if(i<0) return Qnil;
      return INT2FIX(int_sqrt0(i));
      break;
    case T_BIGNUM:
      j=rb_funcall(n,rb_intern(">>"),1,INT2FIX(2));
      k=rb_funcall(int_sqrt(self,j),'*',1,INT2FIX(2));
      k1=rb_funcall(k,'+',1,INT2FIX(1));
      if(rb_funcall(rb_funcall(k1,'*',1,k1),'>',1,n)) return k;
      return k1;
      break;
    default:
      rb_raise(rb_eTypeError,"argument is not integer");
    }
}

static VALUE
int_root(VALUE self,VALUE n,VALUE m)
{
  VALUE j,k,k1;
  if(FIXNUM_P(n) && FIX2INT(n)==0) return INT2FIX(0);
  j=rb_funcall(n,rb_intern(">>"),1,m);
  k=rb_funcall(int_root(self,j,m),'*',1,INT2FIX(2));
  k1=rb_funcall(k,'+',1,INT2FIX(1));
  if(rb_funcall(rb_funcall(k1,rb_intern("**"),1,m),'>',1,n))
    return k;
  return k1;
}

Init_int()
{
    VALUE mInt = rb_define_module("Int");
    rb_define_module_function(mInt, "gcd", gcd, 2);
    rb_define_module_function(mInt, "isqrt", int_sqrt, 1);
    rb_define_module_function(mInt, "iroot", int_root, 2);
}

-----