Ruby の C拡張で約数を求めるメソッドを書いた

なぜか Ruby 本体には、約数を求めるメソッドがないようですので、C拡張で作ってみました。

以前書いた Utilsc への機能追加です。コードは必要な部分だけ載せます。全体のコードはここ です。

#include "utilsc.h"
#include "math.h"

VALUE divisors(VALUE self) {
  int a;
  long i, se;
  VALUE ar;
  
  se = FIX2LONG(self);
  ar = rb_ary_new();
  a = (int)sqrt(se);
  for (i = 1; i <= a; i++) {
    if (!(se % i)) {
      rb_ary_push(ar, INT2FIX(i));
      rb_ary_push(ar, INT2FIX(se / i));
    }
  }
  return rb_funcall(ar, rb_intern("uniq"), 0);
}

void Init_utilsc(void){
  VALUE fix;
  
  fix = rb_const_get(rb_cObject, rb_intern("Fixnum"));
  rb_define_method(fix, "totient", totient, 0);
  rb_define_method(fix, "divisors", divisors, 0);
}

メソッドは Fixnum#divisors です。以前 Ruby で書いたもの(参照)とほぼ同じですが、返される配列はソートされていません。例:

require 'bundler/setup'
require 'utilsc'

p 150.divisors    #=>[1, 150, 2, 75, 3, 50, 5, 30, 6, 25, 10, 15]


ベンチマーク

Ruby 版(参照)。

require 'bundler/setup'
require 'utils'

100_0000.times do |i|
  (i + 1).divisors_int
end

これでおよそ 117秒 かかりました。

C拡張版。

require 'bundler/setup'
require 'utilsc'

100_0000.times do |i|
  (i + 1).divisors.sort
end

かかったのはおよそ 11秒です。

10倍高速化されたということですね。まずまずだと思います。


※追記
GitHub の使い方で参考になったページ:
git pushがrejectされたときの解決の手順 - 今日もスミマセン。
今さら聞けない!GitHubの使い方【超初心者向け】 | TechAcademyマガジン