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

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

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

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

我想得到尽可能接近的结果ceil( 1.25506n / ln n)不会越来越小。

任何建议如何做到这一点？

最佳答案

这是一种方法:

#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，它为我们提供了下一个可能的浮点数。每次操作后，我都调用nextafter，以某种方式修改数字，使结果表达式始终保持上限。

如果我们假设，可以创建一个更好的界限，即除法，乘法正确舍入(对于IEEE-754是正确的)，并且可以代替nextafter来调整舍入模式(始终向上或向下舍入)。

笔记:

为原始表达式使用ceil可能很保守。例如，如果pi(...)= 12.2，则最多有12个素数，而不是13。

该公式非常保守，如您所见here。因此，实际上，不需要整个浮点业务。即使代码误算了一点，它仍然是一个较大的上限。