「素数判定アルゴリズムを開発」記事へのコメント

エラトステネスの篩

[Anonymous Coward]

　を馬鹿正直に N までやると O(N^2) ですけど。これも多項式時間?

(defun prime-p (n)
  (let ((v (make-array (1+ n) :initial-element t)))
    (setf (aref v 0) nil)
    (setf (aref v 1) nil)
    (dotimes (i (1+ n))
      (when (aref v i)
        (do ((j (+ i i) (+ i j)))
            ((> i n))
          (setf (aref v j) nil))))
    (aref v n)))
;; C で書いたけど変な文字があるって云われるじゃん。

Re:エラトステネスの篩

[moonbear (4602)]

ええと，こういう問題は桁数に対してどのくらいのオーダーになるかが重要なんだと思います．例えばnビットの数についてこのプログラムをそのまま適用すると，2^nに比例した記憶領域と時間がかかってしまいます．

Re:エラトステネスの篩

[Anonymous Coward]

基本的なことだと思うんですけど、こういう場合の四則演算 自体の速さってのは O(1) でいいんでしょうか? O(n) とかにしないと多倍長につかえないじゃん、っておもったり。
# 掛け算は FFTで速くできる、とかきいたが。

Re:エラトステネスの篩

[tix (7637)]

d ビット整数の加減算は O(d) 時間です。乗算は素朴にやると O(d^2) 時間、 FFT を使った乗算では O(d log d log log d) 時間です。

商と余りを求める除算の計算量はよく知りません。素朴には O(d^2) 時間でやっているように思いますが。

--
鵜呑みにしてみる？

Re:エラトステネスの篩

[K_O_ (7268)]

d bitの除算はNewton-Raphsonで近似計算すればケチらなくってもlog d回の乗算(と加減算)で終りますよ。余りを求める除算の場合だって多少後処理するだけで、同じオーダーでしょう。

ちなみに各近似ステップでの有効桁数は倍々で伸びるので、必要充分な演算精度にして演算量をもっと減らすことは出来る筈です。

でなきゃあそこまで莫大な円周率の計算なんてできません。

Re:エラトステネスの篩

[tix (7637)]

d bitの除算はNewton-Raphsonで近似計算すればケチらなくってもlog d回の乗算(と加減算)で終りますよ。

忘れていました。お恥ずかしい限りです。ということは、乗算に FFT を使えば除算のオーダは O(d log^2 d log log d) 時間まで落ちますね。ありがとうございます。

--
鵜呑みにしてみる？

Re:エラトステネスの篩

[Anonymous Coward]

SRTならゲートの遅延が O(d) でできます．(アルゴリズムの計算量じゃありません，念のため)

Re:エラトステネスの篩

[tix (7637)]

「SRT」がわからなくて調べたら、 Sweeney-Robertson-Tocher の除算法、 non-restoring division （引き算の結果が負になってもそのまま計算を進めるような除算の方法？）を高速化したもの、と出てきました。 Pentium などでも使われているようですね。

non-restoring division も初耳なので、 SRT 除算まで理解するのは大変そうです。

--
鵜呑みにしてみる？

Re:エラトステネスの篩

[Anonymous Coward]

O(1)とO(n)の違いは今の場合はあまり重要ではないでしょうね。

Re:エラトステネスの篩

[mishima (737)]

件の論文の Introduction には、エラトステネスのふるいの計算量は
入力サイズの指数オーダだって書いてあるけど。
んで、こっちのアルゴリズムの計算量は(漸近的には) O( log(n)^12 ) だって。

--
# mishimaは本田透先生を熱烈に応援しています

Re:エラトステネスの篩

[Anonymous Coward]

まずい、数式が顔文字に見えてしまった。（悲笑