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

アバター
あまさとしおん ◆mzDKTVUAtwqE
2020/7/16 14:19
2^53より大きな数値を正確に計算できる『BIG_CALCライブラリ』の開発を始めました。
1024^16も1の位までしっかり計算できます。
(上段:ライブラリによる計算、下段:プチコンによる計算)

この計算では処理時間が10秒ぐらい掛かりました。

コメント

アバター
あまさとしおん 2020/7/21 21:18 ◆mzDKTVUAtwqE
(この後、乗算をMUL関数に独立させてみたら逆に遅くなった)
IF COM$=="*" THENという判定するよりも関数を呼ぶコストのほうが高いらしい
アバター
あまさとしおん 2020/7/22 13:30 ◆mzDKTVUAtwqE
奇数全般に効くショートカットを加えたらかなり速くなった
その代わり2の累乗が逆に遅くなった…
アバター
あまさとしおん 2020/7/22 13:34 ◆mzDKTVUAtwqE
POW(2,20)のPOW(2,10)乗が244秒になりました、無念…
アバター
あまさとしおん 2020/7/22 13:47 ◆mzDKTVUAtwqE
369^1024→90.939秒(以前は168秒だった)
奇数向けショートカット爆速ですな…
アバター
こういち 2020/10/19 10:36 ◆.Id/aHiU36hu
POWの計算って出来そうにないな…(除算は出来るけど、割りきれる必要があるので、使えない)
アバター
こういち 2020/10/19 10:40 ◆.Id/aHiU36hu
そういえば、聞いたことがある
フェルマーの小定理の強化版であるオイラーの定理というものが存在するということを…
これを使えばPOWの計算できるか?(できたとしても実装難しそう)
アバター
こういち 2020/10/19 12:01 ◆.Id/aHiU36hu
結果が割り切れない除算ができない?wフッフッフw心配することなかれwwこんな時にも役に立つのが競技プログラミング、伝家の宝刀†二分探索†を使わせていただきますぞ!wwwまずは初期値を(0+1<<136)/2=1<<135にセットして……グオーーーー!!!!!!!!数の比較ができなかった……(悲しい)
アバター
こういち 2020/10/19 12:04 ◆.Id/aHiU36hu
出来なくはないけど、数の比較に桁数kの二乗に比例した時間がかかるんだよな…(雑な見積もりなので、実際にはもっとかかる)
で、二分探索で桁数に比例した回数比較するので、除算はO(k^3)
Powで除算を略
全体でO(k^4)
まぁ多項式時間なので現実的と言えなくもないけど…
アバター
こういち 2020/11/4 11:31 ◆.Id/aHiU36hu
せっかく大きな数が表せるなら、視認性の高いdB表記に対応させたい。(放置ゲーみたいに正確に計算したいけど、見るときは大体の値が知りたいときなど)
logで真数同士の足し算って出来たっけな…

どうせ下の方の桁は計算しても精度の関係で切り捨てられるので、上から何桁か取り出して、指数部を足し算するのが良さそう。
123456789だったら、10*log(1235)+10*5
みたいな。
アバター
あまさとしおん 2020/11/27 16:33 ◆mzDKTVUAtwqE
かなり久しぶりに高速化に挑戦している
アバター
あまさとしおん 2020/11/27 16:37 ◆mzDKTVUAtwqE
369^1024→91.477秒

…ほぼ変わんないな(わずかに遅い)
アバター
あまさとしおん 2020/11/27 16:38 ◆mzDKTVUAtwqE
事実上のお題である1727^28は3.053秒なのでごくわずかに速くなりましたが…

ちなみに大昔に108秒→その後4.36秒まで高速化に成功した5415^41は、ついに1秒を切りましたw
アバター
あまさとしおん 2020/11/27 17:27 ◆mzDKTVUAtwqE
あっ
369^1024→57.196秒
やはりIF文列挙なので条件の値をいじると格段に変わるな
アバター
あまさとしおん 2020/11/27 17:33 ◆mzDKTVUAtwqE
sbkey=[公開終了]
ミソは563行目あたりに追加されたIF文の列挙

お題の式が一部変化しました(分単位で計算が終わらない事案の対策)
アバター
あまさとしおん 2020/12/7 20:29 ◆mzDKTVUAtwqE
1727^28が0.176秒になってしまったwww
ほぼ限界来たな
アバター
あまさとしおん 2020/12/8 14:24 ◆mzDKTVUAtwqE
あっ
限界かと思ったら条件の設定ミスがあったので直したらもうちょっと速くなったw
1727^28→0.069秒
アバター
あまさとしおん 2020/12/8 14:29 ◆mzDKTVUAtwqE
sbkey=SBDX 78QV

ちなみに369^1024は追加した高速化プログラムの条件を満たさないのでほぼ変わりません(わずかに遅くなりました)
アバター
あまさとしおん 2020/12/11 17:43 ◆mzDKTVUAtwqE
マジかよ…
それでも暇を持て余すけど…
369^1024→35.97秒

3の倍数に対するショートカットを廃止する代わりに、10の乗数倍の高速化プログラムに、4倍の重みを追加しただけです。
アバター
あまさとしおん 2020/12/11 18:14 ◆mzDKTVUAtwqE
クソ速い
アバター
こういち 2021/1/21 11:52 ◆.Id/aHiU36hu
暗号について調べてたらこんなん見つけた。
これを使えばなんとなく速くなるかも。
https://ja.m.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%82%B4%E3%83%A1%E3%83%AA%E4%B9%97%E7%AE%97

コメントを書く

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

- WEB PATIO -