Haskell は負数の割り算をきちんとサポートしていて、剰余の符号が、割る数と割られる数のどっちに依存するかで2種類ある。 quotRem x y = (q,r) ならば x = qy + r divMod x y = (d,m) ならば x = dy + m 違いは、r の符号は x と同じ (restoring method) m…

数論入門―証明を理解しながら学べる (ブルーバックス) を見て、加速互除法というユークリッドの互助法の高速化ネタを知りました。 剰余を絶対値が最小になる取り方で与えると、パラメータの減りが速くなるとのこと。 なるほどーと思って実装してみたのですが…