Skip to content

Latest commit

 

History

History
349 lines (218 loc) · 12.6 KB

modint.md

File metadata and controls

349 lines (218 loc) · 12.6 KB
Raw

ModInt

答えをある数で割ったあまりを出力する問題で使えるライブラリです。

計算の際に自動であまりを取るため、ミスを減らすことができます。

注意

本ライブラリModIntの使用により、実行時間が遅くなる可能性があります。

使用にあたり注意してください。

使用例

最初にModInt.set_modかModInt.mod =で、剰余の法を設定して下さい。

ModInt.set_mod(11)
ModInt.mod #=> 11

a = ModInt(10)
b = 3.to_m

p -b    # 8 mod 11

p a + b # 2 mod 11
p 1 + a # 0 mod 11
p a - b # 7 mod 11
p b - a # 4 mod 11

p a * b # 8 mod 11
p b.inv # 4 mod 11

p a / b #  7 mod 11

a += b
p a #  2 mod 11
a -= b
p a # 10 mod 11
a *= b
p a #  8 mod 11
a /= b
p a # 10 mod 11

p ModInt(2)**4 # 5 mod 11

puts a  #=> 10

p ModInt.raw(3) #=> 3 mod 11

putsとpによる出力

ModInt.mod = 11
a = 12.to_m

puts a #=> 1
p a    #=> 1 mod 11

ModIntは、to_s, inspectを定義しています。

これにより、putsはto_s, pはinspectを内部で使っているため、出力が変更されています。

putsメソッドは、Integerの出力と変わらない振る舞いで便利ですが、逆にいえば見分けはつかないので注意して下さい。

特異メソッド

new(val = 0) -> ModInt

a = ModInt.new(10)
b = ModInt(3)

newを使わないシンタックスシュガーKernel#ModIntを用意しています。

【参考】Integer#to_m, String#to_m

5.to_m
'2'.to_m

Integer、StringインスタンスをModIntに変換します。

エイリアス to_modint, to_m

set_mod(mod)

ModInt.set_mod(10**9 + 7)
ModInt.mod = 10**9 + 7

最初にこのメソッドを用い、modを設定して下さい。

これは、内部の実装として、グローバル変数$_modに設定しています。

また、内部では$_modが素数かどうかを判定して, グローバル変数$_mod_is_primeに真偽値を代入します。

なお、このメソッドの返り値を使う機会は少ないと思いますが、mod=の方は、代入した引数をそのまま返すのに対し、set_modは[mod, mod.prime?]を返します。

エイリアス set_mod, mod=

mod -> Integer

ModInt.mod

modを返します。

これは、内部の実装として、グローバル変数$_modを返します。

raw(val) -> ModInt

ModInt.raw(2, 11) # 2 mod 11

valに対してmodを取らずに、ModIntを返します。

定数倍高速化のための、コンストラクタです。

valが0以上でmodを超えないことが保証される場合、こちらでModIntを生成した方が高速です。

インスタンスメソッド

val -> Integer

ModInt.mod = 11
m = 12.to_m #  1 mod 11
n = -1.to_m # 10 mod 11

p i = m.val  #=> 1
p j = n.to_i #=> 10

ModIntクラスのインスタンスから、本体の値を返します。

内部の実装として、@valを返しています。

integerに変換するときに、使用してください。

エイリアス val, to_i

エイリアスについての補足

valとto_iは、ModIntのインスタンスメソッドとしてはエイリアスで違いはありません。しかし、Integerクラスにもto_iメソッドがあるためto_iの方が柔軟性がありRubyらしいです。内部実装でもどちらが引数であってもいいようにto_iが使われています。なお、valは、本家の関数名であり、内部実装のインスタンス変数名@valです。

inv -> ModInt

ModInt.mod = 11
m = 3.to_m

p m.inv #=> 4 mod 11

xy ≡ 1なるyを返します。

つまり、モジュラ逆数を返します。

pow(other) -> ModInt

ModInt.mod = 11
m = 2.to_m

p m**4　#=> 5 mod 11
p m.pow(4)　#=> 5 mod 11

引数はIntegerのみです。

各種演算

Integerクラスと同じように、ModInt同士、IntegerとModIntで四則演算などができます。 詳しくは、使用例のところを見てください。

ModInt.mod = 11

p 5.to_m + 7.to_m #=> 1 mod 11
p 0 + -1.to_m     #=> 10 mod 11
p -1.to_m + 0     #=> 10 mod 11

p 12.to_m == 23.to_m #=> true
p 12.to_m == 1 #=> true

【注意】IntegerとModIntの比較方法

IntegerとModIntは==, !=による比較ができますが、本家ACLと一部の挙動が異なっています。

比較するIntegerは[0, mod)の範囲では真偽値を返しますが、それ以外の範囲の場合は必ずfalseを返します。本ライブラリは[0, mod)の範囲で制約がありますが、本家ライブラリは制約がないので、この点で異なります。

Verified

高速化Tips

+, -, *, /のメソッドは、それぞれ内部でdupで複製させたものに対してadd!, sub!, mul!, div!のメソッドを用いています。レシーバのModIntを破壊的に変更してもいいときは、こちらのメソッドを用いた方が定数倍ベースで速いかもしれません。

参考リンク

Q&A

実行時間が遅くなる可能性があるのに、何故入れるのか

  • 本家ライブラリの再現。
  • コードの本質的な部分への再現
  • 実際どれぐらい遅いのか計測するため。ベンチマークとして。
  • 利用者を増やして需要を確かめ、Ruby本体に入れるように訴えたい。

ModIntのメリット

Rubyは、C言語/C++と異なり、次のような特徴があります。

  • 負数を正数で割っても正数を返す定義
  • 多倍長整数で、オーバーフローしない(※数が大きすぎると計算は遅くなります)

そのため、C言語/C++に比べるとModIntを使うメリットは薄れる部分もありますが、

  • 可読性の向上
  • Modの取り忘れを気にする必要がなくなる

などのメリットがあります。

グローバル変数を使う意図は

$_modや$_mod_is_primeというグローバル変数を使用しています。

特に実務などで、グローバル変数は忌避すべきものとされています。

しかし、クラス変数は、インスタンス変数に比べアクセスするのに時間がかかるようで、全てのそれぞれのModIntインスタンス変数@modを持たせるよりも遅くなることがありました。

そのため、総合的に1番実行時間が速かったグローバル変数を使用しています。

インスタンス変数、クラス変数、クラスインスタンス変数、グローバル変数、定数など色々ありますが、どれがどこで遅いのか・速いのか、何が最善なのかわかっていないので、実装を変える可能性があります。

グローバル変数が、アンダースコア始まりな理由

$modはコードで書きたい人もいたので、名前衝突しないよう$_modとしました。

Numericクラスから継承する意図は

Rubyの数値クラスは、Numericクラスから継承する仕様で、それに合わせています。

継承してると、少しだけいいことがあります。

  • ==を定義すると、!=, zero?, nonzero?などのメソッドも定義される。
    • ここ重要です。==を定義しているので、!=を定義しなくて済んでいます。
  • *を定義すると、abs2メソッドも定義される。
  • finite?, real, real?,imag, が使えるようになる。
  • is_a?(Numeric)でtrueを返し数値のクラスだとわかる。

Integerクラスから継承しない理由

Integerなどの数値クラスではInteger.new(i)のように書けないようにnewメソッドが封じられていて、うまい継承方法がわかりませんでした。 また、そもそもIntegerと割り算などの挙動が違うため、Integerから継承すべきではないという意見もありました。ModIntは大小の比較などもすべきではないです。。

add!と!がついている理由

Rubyだと!付きメソッドが破壊的メソッドが多いから、本ライブラリでもそうしました。+にaddのエイリアスをつけるという案もありましたが、そのようなエイリアスがあっても使う人はほぼいないと考え保留にしました。

primeライブラリのprime?を使わない理由

Ruby本体のprimeライブラリにあるprime?を使用せず、本家ライブラリのis_prime関数に合わせてModInt.prime?(k)を実装しています。こちらの方が速いようです。「Ruby本体のprimeライブラリは計測などの目的であり高速化する必要はない」旨をRubyコミッターの方がruby-jpで発言していた記憶です。

powメソッドの引数がIntegerで、ModIntが取れない理由

ModInt#powの引数は、Integerのみとしています。

しかし、ModIntも許容すれば、コードがスッキリする可能性もあると思いますが、理論的にIntegerのみが来るはずと考えるためです。間違った形でModIntを引数にとれてしまうとバグが起きたときに気がつきにくいため、封印しています。

ModIntの大小比較やRangeが取れない理由

コードがスッキリする可能性もあると思いますが、理論的に正しくないと考えるためです。間違った形でModIntが大小比較できてしまうと、バグが起きたときに気がつきにくいため、封印しています。

RubyならRefinementsでModIntを作れるのでは

それもいいかもしれないです。

ModIntのコンストラクタまわりの由来など

ModInt(val) -> ModInt

Kernel#Integer, Kernel#Float, Kernel#Rationalに準じて、Kernel#ModIntを作っています。

ModInt.mod = 11

m = ModInt(5)

ModInt.raw(val)

rawの由来は本家がそうしてたからです。

to_m

Rubyのto_i, to_fなどに準じています。

本家ライブラリとの違い

rhsという変数名

右辺(right-hand side)の意味でrhsという変数名が使われていましたが、馴染みがなくRubyではotherが一般的であるためotherに変更しています。

def ==(other)
  @val == other.to_i
end

コンストラクタは、true/false未対応

本家C++ライブラリの実装では、真偽値からmodint型の0, 1を作れるらしいです。

しかし、本ライブラリは、下記の理由から、対応しません。

  • 定数倍高速化
  • Rubyの他の数値型は、true/falseから直接変換できない。
  • Rubyの偽扱いのfaltyはfalse/nilのみであり、コンストラクタだけ対応しても変な印象を受ける。
  • Ruby中心に使っている人には馴染みがなく使う人が少なそう。
  • 使う機会もあまりなさそう。