Приведение от (длинного) двойного к size_t - PullRequest
Новая
       57

Приведение от (длинного) двойного к size_t

0 голосов
/ 19 декабря 2018

Я пытаюсь сделать Сито Эратосфена максимально эффективным.Я хотел бы установить длину моего простого массива в верхнюю связь равной pi(n) < 1.25506n / ln n, но я не уверен, как перейти к преобразованиям, чтобы сделать это безопасно, и какая комбинация типов лучше для этого.

Максимальная длина моего списка будет ограничена максимальным размером массива.

Я предполагаю, что идеальная комбинация зависит от того, как size_t реализован внутри, и от его верхнего предела.

Я бы хотелполучить результат как можно ближе к ceil( 1.25506n / ln n), не получая меньшее число.

Любые советы, как это сделать?

1 Ответ

0 голосов
/ 19 декабря 2018

Вот способ сделать это: 

#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.
  • Эта формула очень консервативна, как вы можете видеть здесь .Так что, на самом деле, весь этот бизнес с плавающей точкой не требуется.Даже если код немного просчитается, он все равно будет иметь верхнюю границу с большим запасом.
...