Petitverse

こういち ◆.Id/aHiU36hu
2021/12/3 0:09

ものすごく今更ですが、整数×整数で計算結果が整数に収まらない場合、modを取ったとしても結果が正しいとは限らないんですね。(昔出してた問題ではこれを嫌って20123とか小さめの素数を使ってた)
例
A%=1000000006
B%=A%*A% MOD 1000000007
PRINT B%

実行結果
923446813
(1000000006はMOD 1000000007上では-1なので、1になってほしい。)

この923446813ってなんなんでしょうね？(下位32bitとか？)

こういち 2021/12/3 0:25 ◆.Id/aHiU36hu

少し厄介なのが、65536*65536も0になってしまうこと。
正しく計算するなら
low0%=A%>>16&65535
up0%=A%&65535
low1%=B%>>16&65535
up1%=B%&65535
c0%=low0%*low1% MOD P%
c2%=up0%*up1% MOD P%
C%=(c2%+c0%)mod P%-(up0%-low0%+P%)*(up1%-low1%+P%) MOD P%+P%
IF C%>=P% THEN C%=C%-P%
C%=c2%*32768mod P%*32768mod P%*4mod P%+C%*32768mod P%*2MOD P%
IF C%>=P% THEN C%=C%-P%
C%=C%+c0%
IF C%>=P% THEN C%=C%-P%

…面倒の極みじゃん。(脳死でカラツバ法使ってしまったけど、多分普通にやった方がシンプルで速い)

こういち 2021/12/3 12:59 ◆.Id/aHiU36hu

low0%=A%>>16&65535
up0%=A%&65535
low1%=B%>>16&65535
up1%=B%&65535
t%=up0%*up1%mod P%*32768mod P%*32768mod P%*4mod P%
t%=t%+low0%*low1%mod P%
if t%>=P% then t%=t%-P%
C%=low0%*up1%mod P%+low1%*up0%mod P%+t%
if C%>=P% then C%=C%-P%

…だいぶシンプルになった…のか？

こういち 2021/12/4 12:28 ◆.Id/aHiU36hu

話は戻って、Garnerのアルゴリズム。
1000000007<PQ<2147483647
となるような素数PQを取ってきて、
AB MOD P
AB MOD Q
からAB MOD PQを復元しようと思ったけど、復元するには逆数を求める必要があって、逆数を求めるのに30回前後の計算が必要なので、普通にやった方が速いかな。

こういち 2021/12/6 23:34 ◆.Id/aHiU36hu

一瞬小さめな素数でやろうとも思ったけど、さすがに実用性ないよな…
多分65536未満で使えそうなのは40961(5*2^13+1)

コメントを書く

こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
ユーザー登録なしで書き込みができます
秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります

プチコン 非公式コミュニティ プレイ日記

コメント

コメントを書く

プチコン非公式コミュニティプレイ日記