Могу ли я доверять преобразованию реального результата в ceil ()? - PullRequest
Новая
       15

Могу ли я доверять преобразованию реального результата в ceil ()?

4 голосов
/ 02 ноября 2011

Предположим, у меня есть код, такой как: 

float a, b = ...; // both positive
int s1 = ceil(sqrt(a/b));
int s2 = ceil(sqrt(a/b)) + 0.1;

Возможно ли, что s1 != s2? Меня беспокоит, когда a/b - идеальный квадрат. Например, возможно a=100.0 и b=4.0, тогда вывод ceil должен быть 5.00000, но что если вместо этого это 4.99999?

Аналогичный вопрос: есть ли вероятность, что 100.0/4.0 оценит, чтобы сказать 5.00001, а затем ceil округлит его до 6.00000?

Я бы предпочел сделать это в целочисленной математике, но sqrt вроде шурупы, которые планируют.

РЕДАКТИРОВАТЬ: предложения о том, как лучше реализовать это тоже будет оценено! Значения a и b являются целочисленными значениями, поэтому фактический код больше похож на: ceil(sqrt(float(a)/b))

РЕДАКТИРОВАТЬ: Основываясь на ответе levis501, я думаю, я сделаю это: 

float a, b = ...; // both positive
int s = sqrt(a/b);
while (s*s*b < a) ++s;

Спасибо всем!

Ответы [ 5 ]

6 голосов
/ 02 ноября 2011

Я не думаю, что это возможно.Независимо от значения sqrt(a/b), оно генерирует некоторое значение N, которое мы используем как: 

int s1 = ceil(N);
int s2 = ceil(N) + 0.1;

Поскольку ceil всегда выдает целочисленное значение (хотя и представляется как двойное), у нас всегда будет некотороезначение X, для которого первый выдает X.0, а второй X.1.Преобразование в int всегда усекает это .1, поэтому оба результата приведут к X.

Может показаться, что было бы исключение, если бы X было настолько большим, что X.1 переполнило диапазондвойной.Я не понимаю, где это могло быть возможно, хотя.За исключением близкого к 0 (где переполнение не имеет значения) квадратный корень из числа всегда будет меньше , чем входное число.Поэтому, прежде чем ceil (N) +0.1 может переполниться, a/b, используемый в качестве входа в sqrt(a/b), должен был уже переполниться.

3 голосов
/ 02 ноября 2011

Вы можете написать явную функцию для вашего случая.Например: 

/* return the smallest positive integer whose square is at least x */
int isqrt(double x) {
  int y1 = ceil(sqrt(x));
  int y2 = y1 - 1;
  if ((y2 * y2) >= x) return y2;
  return y1;
}

Это будет обрабатывать нечетный случай, когда квадратный корень из вашего отношения a/b находится в пределах точности double.

1 голос
/ 02 ноября 2011

Равенство чисел с плавающей точкой действительно является проблемой, но ИМХО нет, если мы имеем дело с целыми числами.

Если у вас есть случай 100.0/4.0, он должен прекрасно оценить 25.0, так как 25.0 точно представлен как число с плавающей точкой, в отличие от, например, 25.1.

0 голосов
/ 04 ноября 2011

s1 всегда будет равно s2.

Стандарты C и C ++ мало говорят о точности математических процедур. В буквальном смысле невозможно реализовать стандарт, поскольку стандарт C говорит, что sqrt (x) возвращает квадратный корень из x, но квадратный корень из двух не может быть точно представлен в плавающей запятой.

Реализация подпрограмм с хорошей производительностью, которые всегда возвращают правильно округленный результат (в режиме округления к ближайшему это означает, что результатом является представимое число с плавающей запятой, которое является ближайшим к точному результату, причем связи разрешаются в пользу низкий нулевой бит) - сложная исследовательская задача. Хорошие математические библиотеки нацелены на точность менее 1 ULP (поэтому возвращается одно из двух ближайших представимых чисел), возможно, немного больше, чем .5 ULP. (ULP - это единица наименьшей точности, значение младшего бита, заданное конкретным значением в поле экспоненты.) Некоторые математические библиотеки могут быть значительно хуже этого. Вам нужно будет обратиться к поставщику или проверить документацию для получения дополнительной информации.

Так что sqrt может быть немного отключен. Если точный квадратный корень является целым числом (в пределах диапазона, в котором целые числа точно представимы в плавающей точке), и библиотека гарантирует, что ошибки меньше 1 ULP, то результат sqrt должен быть точно правильным, потому что любой результат, отличный от Точный результат не менее 1 ULP.

Аналогично, если библиотека гарантирует, что ошибки меньше 1 ULP, ceil должен вернуть точный результат, опять же, потому что точный результат представим, а любой другой результат будет по крайней мере на 1 ULP. Кроме того, природа ceil такова, что я ожидаю, что любая разумная математическая библиотека всегда будет возвращать целое число, даже если остальная библиотека была не высокого качества.

Что касается случаев переполнения, если ceil (x) был вне диапазона, в котором все целые числа точно представимы, то ceil (x) +. 1 ближе к ceil (x), чем к любому другому представимому числу, поэтому округленный результат добавления .1 к ceil (x) должен быть ceil (x) в любой системе, реализующей стандарт с плавающей запятой (IEEE 754). Это при условии, что вы находитесь в режиме округления по умолчанию, который округляется до ближайшего. Можно изменить режим округления на что-то вроде округления до бесконечности, что может привести к тому, что ceil (x) +. 1 будет целым числом выше, чем ceil (x).

0 голосов
/ 02 ноября 2011

Да, вполне возможно, что s1 != s2. Почему это проблема, хотя? Кажется достаточно естественным, что s1 != (s1 + 0.1).

Кстати, если вы хотите, чтобы 5.00001 было округлено до 5.00000 вместо 6.00000, используйте rint вместо ceil.

И чтобы ответить на реальный вопрос (в вашем комментарии) - вы можете использовать sqrt, чтобы получить начальную точку, а затем просто найти правильный квадрат, используя целочисленную арифметику. 

int min_dimension_greater_than(int items, int buckets)
{
    double target = double(items) / buckets;
    int min_square = ceil(target);
    int dim = floor(sqrt(target));
    int square = dim * dim;
    while (square < min_square) {
        seed += 1;
        square = dim * dim;
    }
    return dim;
}

И да, это можно улучшить, это всего лишь быстрый набросок.

...