エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Haskellでポラード・ロー法を実装してみた - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Haskellでポラード・ロー法を実装してみた - Qiita
ポラード・ロー法(Pollard's rho algorithm)は非自明な約数を高速に発見するアルゴリズムです。 ただし... ポラード・ロー法(Pollard's rho algorithm)は非自明な約数を高速に発見するアルゴリズムです。 ただし、このアルゴリズムは必ず約数を発見できるわけではなく、失敗する可能性があります。 今回は、このアルゴリズムをHaskellで実装して、その速度を計測してみました。 また、素朴な試し割り法による約数の探索についても速度を計測して、ポラード・ロー法の速さと比較してみようと思います。 -- ポラード・ロー法 rho :: Integer -> Maybe Integer rho n | n < 4 = Nothing | otherwise = loop 2 2 1 -- フロイドの循環検出法で循環が検出されるまで試し割りする where random = \x -> mod (x*x + 1) n --疑似乱数 loop x0 y0 d | d == n = Nothing