在 Rust 中建造一個高性能的阿特金篩

https://codereview.stackexchange.com/questions/288983/construct-a-performant-sieve-of-atkin-in-rust

在 Rust 中構建 Atkin 篩的高效實現
這個 Rust 中的 Atkin 篩實現了 Atkin 與 Bernstein 的論文直接實現(通過經驗觀測進行了一些優化)。在 1.4 GHz 的機器上,它能在 4.5 秒內使用 34.4 MiB 找到 1,000,000,000 以內的所有質數。Sieve 使用了 Vec< u16 >,其中第 i 個元素指示了 60 * i + d 這 16 個數是否是質數,其中 d 是對模 60 互質的餘數。此外,isqrt 是整數平方根函數(在此未顯示實現),因為在 Rust 中整數平方根並未穩定。

此外,該文提及了 A. O. L. Atkin and D. J. Bernstein 的論文“Prime Sieves Using Binary Quadratic Forms”,詳細解釋了算法。

此實現主要執行 3 個算法:algorithm_3_1、algorithm_3_2 和 algorithm_3_3。每個構造都包含若干次“0..self.sieve.len()”的迴圈。這些代碼可能以數學上的優化進一步改進性能。同時,有些代碼可以重構,以減少重複。

此外,對於 iter 方法,能否更好、更快地實現?

結論:這個 Sieve 實現了 Atkin 與 Bernstein 的論文提出的算法,爲了進一步優化性能,你可能可以考慮簡化一些代碼、優化算法以及重構一些重複的部分。

via Recent Questions – Code Review Stack Exchange

January 18, 2024 at 08:03PM

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *