-
- いいね！0
大堀龍一 (Ryuichi OHORI)
@__DaLong
@colun 従来法という呼び名が何を指しているのかよくわかりませんが、ユークリッドの互除法のことなら証明はなされています。
2012-01-28 23:48:29
コルン
@colun
@__DaLong 失礼しました。従来法がO(logp)に収まることは、でした。O(min(n, logp))が僕の予想でした。で、従来法というのは、マイナスを用いない場合の方法のことです。
2012-01-28 23:49:14
大堀龍一 (Ryuichi OHORI)
@__DaLong
@colun とりあえず、今のところ思いついている最悪ケースの計算量 n, 法 p が http://t.co/baOOK8vR です。
2012-01-28 23:51:38
コルン
@colun
@__DaLong そのページの数式って、DaLongさんが定義したものでしょうか？ その最悪のケースで、logpより明らかに大きなオーダーになっていそうですか？
2012-01-29 00:02:06
大堀龍一 (Ryuichi OHORI)
@__DaLong
@highjellies @colun O(n) が明らかで O(log p) が未証明とおっしゃったのは、rng-hos-ome 法 (略して ρ法と呼ぶことにする) のゼロへ近付ける方ですか、正のみのバリアントの方ですか。
2012-01-29 00:05:24
コルン
@colun
@__DaLong @highjellies マイナスを用いない方、、、つまり、正のみの方です。（バリアントと言ってるのは、知識不足で分かりません
2012-01-29 00:06:07
大堀龍一 (Ryuichi OHORI)
@__DaLong
@colun 説明が遅れて申し訳ないですが、n に対して 2 以上 n 以下のどれで割っても 1 足りない最小の素数です。
2012-01-29 00:06:21
コルン
@colun
@__DaLong このグラフは横軸nの奥行きpですけど、横軸pの奥行きnって可能でしょうか？ そちらのグラフの方を見たいです。 @colun
2012-01-29 00:09:24
大堀龍一 (Ryuichi OHORI)
@__DaLong
@colun いえ、横が n に対して縦軸 (A083685) が p ですよ。奥行きはありません。
2012-01-29 00:11:11
コルン
@colun
@__DaLong というのも、横軸nの奥行きpだと、nを変化させた場合にO(n)に収まることがグラフから読み取れますが、、、pを変化させた場合にO(logp)に収まるかどうかは、横軸pの奥行きnじゃないと分かりません。 @colun
2012-01-29 00:11:26
jellies
@highjellies
@omeometo (mod.97) 23*5=18 18*6=11 11*9=2 2*49=1 だと49が2の逆元で49*9が11の逆元で49*9*6が18の逆元で49*9*6*5が23の逆元だと一度にもとまるという意味なら分かる
2012-01-29 00:27:49
jellies
@highjellies
@omeometo でこの（マイナスを使わない）方法だとO(log p)回の反復で終わるのかどうか自分程度には証明できなかった
2012-01-29 00:28:50
コルン
@colun
@omeometo @highjellies マイナスを用いないバージョン(n, n-1, n-2, n-3, n-4, ...2, 1)の最悪パターンを、常に故意に発生させる様な方法でしょうか？
2012-01-29 00:40:02
コルン
@colun
@omeometo @highjellies ちなみに最悪パターンを発生させなくても、メモ化DPでnの小さい方から順番に求めていけば、1〜nまでのn個をO(n)で求めることができるのは明白ですよね？ @colun
2012-01-29 00:55:56