Ruby の C拡張を作ってみた

プロジェクト・オイラー参照)の計算高速化のため、Ruby の C拡張に挑戦してへろへろに疲れました。参考にしたのはここここなど。公式ページ(だと思う)がやはり詳しいです。ここも読むべきでしょう。(※追記 ここも追加。)

とりあえずソース。

#include "totient.h"

long gcd(long x, long y) {
  long tmp;
  if (x < y) {tmp = x; x = y; y = tmp;}
  if (!y) return x;
  return gcd(y, x % y);
}

VALUE totient(VALUE self, VALUE n) {
  int a;
  long i, se;
  
  a = 0;
  se = FIX2LONG(n);
  for (i = 1; i < se; i++) {
    if (gcd(se, i) == 1) a++;
  }
  return INT2FIX(a);
}

void Init_totient(void){
  VALUE rb_cTotient;
  
  rb_cTotient = rb_define_module("Totient");
  rb_define_method(rb_cTotient, "totient", totient, 1);
}



(野良)Gem化はとにかくここのとおりにやりました。Bundler でやるのが簡単です。ただ、'cannot load such file -- rake/extensiontask' というエラーがでたので、Bundler でではなくて $ gem install rake-compiler が必要でした。

あとでもう少し書き直します。


C拡張はできたけれど、プロジェクト・オイラーを解くには殆ど無意味でした。brute-force にやるのは馬鹿らしいのだなあ…。

なお上の C拡張は、以下の Ruby コードとほぼ同じ内容です。gcd はユークリッドの互除法参照)で実装しました。

def totient(n)
  a = 0
  1.upto(n - 1) {|i| a += 1 if n.gcd(i) == 1}
  return a
end


効果

比較してみました。

ruby

def totient(n)
  a = 0
  1.upto(n - 1) {|i| a += 1 if n.gcd(i) == 1}
  return a
end

2.upto(30000) {|i| totient(i)}

C拡張版

require 'bundler/setup'
require 'totient'

include Totient
2.upto(30000) {|i| totient(i)}

Ruby版は 107秒、C拡張版は 62秒ということで、単純な計算だから倍も速くなっていないですね。でも、こんなのでも効果がないことはない。ものによれば 10倍くらいは速くなったりするそうです。まあ、またそのうち遊んでみよう。


なお、GitHub を使った「野良Gem」(RubyGems.org に登録していない Gem)なので、gem install でインストールできません。どうも、自分の腐った Gem で RubyGems名前空間を汚したくないのだよね。ただ、Gem の管理に Bundler を使っている人は、Gemfile に gem 'totient', github: 'obelisk68/totient' を追加して $ bundle install でインストールできるので(参照)、よかったら遊んでみて下さい(ってこれ使い道がないでしょう…)。Windows を使っている人はこちらでインストール可能です。