[ruby-list:7017] Re: modulo

けいじゅ＠日本ラショナルソフトウェアです.

In [ruby-list :07013 ] the message: "[ruby-list:7013] modulo ", on
Mar/09 01:57(JST) [e-mail] writes:

>  豊福＠パパイヤです。

>  下のような剰余系のプログラムを書いて一応動くの
>ですがもっとうまい方法を教えて下さい。

何か変わったことしていますね(^^;;;;


>(1) 元の +,-,*,/ を使って *,/ を再定義しているの
>  ですが、元の +,-,*,/ を alias して使っているので
>  例えば x * b - y * a を x.ml(b).mn(y.ml(a)) と
>  書くように非常に可読性が悪くなっています。
>
>(2) 最初は +,- も再定義していたのですが
>  for i 1..100 というのではまりました。i を増加
>  していくのにも再定義した + が使われるのですね。
>  当り前ですが。これはしょうがないだろうな。

Integer/Bignumそのものを剰余数にしちゃっていますね. これは, (2)でも話
していますが, かなり無理があると思います.

# いや, 無理があるというのと違うかな, 目的が剰余系なrubyを作りたいとい
# うなら別ですが...

といってもなかなかきれいに解決する方法はなさそうですね.

1. rubyのベースになる動作を根本的に変更しない.
2. できるだけきれいに剰余系を表現したい.

これを重視して考えてみますと:

まず, 何がクラスになるかを検討します. 剰余系はある種の状態を表していま
すので, これがクラスになると思います. ただし, 何を法とするかによってだ
けクラスがある. つまり, 2を法とするModulo2, 3を法とするModulo3, ...

というわけで, 動的にクラスを作ってやる必要が出てきます.

んで, 数についてですが, 通常は

  4 == 2 (mod 2)

の様に表現しますよね. 4とか2は通常の数(ruby流にはFixnum)です. 

このまま実装するのは無理があるので,

  v1 = Modulo2(4)
  v2 = Modulo2(2)

  v1 == v2 ==> true

の様に2を法とする剰余系の2と4のインスタンスを生成してその上で演算を行
なうようにします.

で, 実装ですが, 以下のような感じです:

module Modulo
  Modulo_n = {}

  def Modulo.def_modulo(n)
    n = n.abs
    if mod = Modulo_n[n]
      mod
    else
      mod = eval(<<END_OF_EVAL, TOPLEVEL_BINDING)
      class Modulo#{n}
	include Modulo
	Mod = #{n}

	def mod
	  Mod
	end
      end   
      def Modulo#{n}(value)
	Modulo#{n}.new(value)
      end
      Modulo#{n}
END_OF_EVAL
      Modulo_n[n] = mod
    end
    mod
  end

  def initialize(value)
    @value = value
    normalize
  end

  attr :value

  # original Integer#mod
  def normalize
    if (mod == 0)
      return self
    else
      void, @value = @value.divmod(mod)
      @value += mod if (@value < 0)
      return self
    end
  end

  def +(other)
    case other
    when Integer
      type.new(@value + other)
    when Modulo
      type.new(@value + other.value)
    else
      v1, v2 = other.coerce(self)
      v1 + v2
    end
  end

  def -(other)
    case other
    when Integer
      type.new(@value - other)
    when Modulo
      type.new(@value - other.value)
    else
      v1, v2 = other.coerce(self)
      v1 - v2
    end
  end

  def *(other)
    case other
    when Integer
      type.new(@value * other)
    when Modulo
      type.new(@value * other.value)
    else
      v1, v2 = other.coerce(self)
      v1 * v2
    end
  end

  def /(other)
    if (mod == 0)
      case other
      when Integer
	type.new(@value / other)
      when Modulo
	type.new(@value / other.value)
      else
	v1, v2 = other.coerce(self)
	v1 / v2
      end
    else
      type.new(@value * other.inv)
    end
  end

  def inv
    #...
  end

end

coerceなどはまだ定義されていません.

使い方は以下のようになります:

rbc0> Modulo.def_modulo(3)
Modulo3
# ここでクラスModulo3と関数Modulo3が定義されます.

rbc0> v1 = Modulo3(10)
#<Modulo3: @value=1>
rbc0> v2 = Modulo3(2)
#<Modulo3: @value=2>

rbc0> v1 + v2
#<Modulo3: @value=0>
rbc0> v1 - v2
#<Modulo3: @value=2>
rbc0> v1 * v2
#<Modulo3: @value=2>

rbc0> v1 += 1
#<Modulo3: @value=2>
rbc0> v1 += 1
#<Modulo3: @value=0>


># 剰余系での演算
># 合成数のケースはちょっと面倒なので後まわし

合成数って何でしたっけ?


__
................................石塚 圭樹＠日本ラショナルソフトェア...
----------------------------------->> e-mail: [e-mail] <<---