パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

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

  •  を馬鹿正直に 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 で
    • ええと,こういう問題は桁数に対してどのくらいのオーダーになるかが重要なんだと思います.例えばnビットの数についてこのプログラムをそのまま適用すると,2^nに比例した記憶領域と時間がかかってしまいます.
      • 基本的なことだと思うんですけど、こういう場合の四則演算 自体の速さってのは O(1) でいいんでしょうか? O(n) とかにしないと多倍長につかえないじゃん、っておもったり。
        # 掛け算は FFTで速くできる、とかきいたが。
        • d ビット整数の加減算は O(d) 時間です。乗算は素朴にやると O(d^2) 時間、 FFT を使った乗算では O(d log d log log d) 時間です。

          商と余りを求める除算の計算量はよく知りません。素朴には O(d^2) 時間でやっているように思いますが。
          --
          鵜呑みにしてみる?
          • d bitの除算はNewton-Raphsonで近似計算すればケチらなくってもlog d回の乗算(と加減算)で終りますよ。余りを求める除算の場合だって多少後処理するだけで、同じオーダーでしょう。

            ちなみに各近似ステップで
            • d bitの除算はNewton-Raphsonで近似計算すればケチらなくってもlog d回の乗算(と加減算)で終りますよ。
              忘れていました。お恥ずかしい限りです。ということは、乗算に FFT を使えば除算のオーダは O(d log^2 d log log d) 時間まで落ちますね。ありがとうございます。
              --
              鵜呑みにしてみる?
              親コメント

「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」

処理中...