search

NASU41 / AtCoderLibraryForJava

Creative Commons Zero v1.0 Universal
78 stars 23 forks source link

ModArithmetic998244353#add(int, int) の演算結果が異なる #54

Closed m1zz1y closed 3 years ago

m1zz1y commented 3 years ago

add(1000000000, 1000000000) (10^9 + 10^9) など、足した値が mod の2倍以上になるときに正しい値が返ってこないようです。 ModArithmetic1000000007でも同様？他の演算でもあるかどうかは未確認です。（どうやって確かめるのが賢いんだろう… 🤔 ） https://github.com/NASU41/AtCoderLibraryForJava/blob/99a84f374a9e1a22dfb9718fbed75d7c55a9316c/ModInt/ModInt.java#L227-L238

修正方針としては以下あたりがいいのでしょうか

suisen-cp commented 3 years ago

ModArithmetic は ModInt 経由でしか触らないクラスとして設計しており, ModInt 経由であれば add(a, b) において 0<=a,b<mod が仮定できるのでこのような形になっています.

ModInt 経由で 0<=a,b<mod が満たされない状況が発生したのであれば, その状況を教えていただけるとありがたいです.

m1zz1y commented 3 years ago

なるほど、設計の意味を読み違えていました！ 今回発生していたのはModInt経由ではなくModArithmeticを直接使用していたケースでした。 （そこを理解した上でなのかもですが、ModArithmeticを直接使用しているコードを以前見て勘違いしていました。。）

再度ソースを見返してみましたが、自分の目からだとModInt経由で演算結果が異なる場合はなさそうに見えました。 以上より実際には問題はなさそうなのでcloseさせていただきます、お騒がせしました 🙏

ちなみに「外から見える可視性修飾子になってしまっているのでは」と思ってしまっていたのですが、Java版のほうはきちんとprivateになっており、 自分が使っているKotlin版のほうので誤って可視範囲が広くなってしまっている（恐らくconvert時のミス？）ようでした。 教えていただくまで気がつけなかったので感謝です、ありがとうございます… 🙏

suisen-cp commented 3 years ago

了解しました！報告ありがとうございます.

ModInt は結構重いので ModArithmetic を直接使用する方がパフォーマンスが良く, そちらを好んで使用する人はいるかもしれません. ただし, 指摘して頂いた通り直接扱う場合は正しくない演算結果を返す可能性があるので注意が必要です.

ModArithmetic クラス自体は外から見えないんですが, メソッドの修飾子が interface の仕様上なのか public しか許されなかったので紛らわしくなっています, すみません (abstract class にするのが良いのでしょうか？この辺りをよく分かっておらず...)

m1zz1y commented 3 years ago

返信遅れてすみません！ 注意喚起感謝です…！

interfaceを使っていると文字通り「インターフェイスとして外部に公開するもの」というニュアンスを感じるので、役割的にはabstract classを使ったほうが個人的にはしっくりきます。わざわざ変更するものかというとそんなに…とも思いますが。。 （私のJava歴はまだ浅いので、もしかしたらとんちんかんなことを言ってしまっているかも＆パフォーマンスに影響出てしまうものかもしれません。。）

もしくは、 Java では interfaceのメソッドはアクセス修飾子なしでもpublicになるので、アクセス修飾子の省略だけしてしまうのはありかもしれません（気持ちの問題なのでかなり優先度は低くなりそうですが）

余談ですが、こういう省略できるところとかは IntelliJ IDEA が詳しく教えてくれるのでオススメです…！