c++ - 从 (long)double 转换为 size_t

Question

我正在尝试尽可能高效地实现埃拉托色尼筛法。我想将素数数组的长度设置为上键 pi(n) < 1.25506n / ln n但我不确定如何进行转换以安全地进行转换，也不确定哪种类型组合最适合。

我的列表的最大长度将受到数组最大大小的限制。

我的猜测是，理想的组合取决于 size_t 的内部实现方式及其上限。

我希望得到尽可能接近的结果 ceil( 1.25506n / ln n)数字从未变小。

关于如何做到这一点有什么建议吗？

Answer 1

这里有一个方法可以做到这一点:

#include <cstddef>
#include <cfloat>
#include <cmath>

std::size_t piUpperBound(std::size_t n) {
    double x = n;
    double num = nextafter(x, DBL_MAX);

    x = log(x);
    double den = nextafter(x, -DBL_MAX);

    double result = num/den;
    result = nextafter(1.25506, DBL_MAX)*nextafter(result, DBL_MAX);
    result = nextafter(result, DBL_MAX);

    return ceil(result);
}

此代码假定log 最多有 1 个 ulp 错误。

基本思想是使用nextafter，它为我们提供了下一个可能的 float 。每次操作后，我都会调用 nextafter，以某种方式修改数字，使生成的表达式保持上限。

如果我们假设除法、乘法正确舍入(对于 IEEE-754 为真)，则可以创建更好的界限，而不是 nextafter，我们可以调整舍入模式(始终舍入向上或向下)。

注意事项:

• 对原始表达式使用ceil 可能比较保守。例如，如果pi(...)=12.2，则最多有12个素数，而不是13个。
• 这个公式很保守，可以看到here .所以，实际上，不需要整个浮点业务。即使代码计算错误一点点，它仍然是一个很大的上限。