Can I trust a real-to-int conversion of the result of ceil()?

Question

Suppose I have some code such as:

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

Is it ever possible that s1 != s2? My concern is when a/b is a perfect square. For example, perhaps a=100.0 and b=4.0, then the output of ceil should be 5.00000 but what if instead it is 4.99999?

Similar question: is there a chance that 100.0/4.0 evaluates to say 5.00001 and then ceil will round it up to 6.00000?

I'd prefer to do this in integer math but the sqrt kinda screws that plan.

EDIT: suggestions on how to better implement this would be appreciated too! The a and b values are integer values, so actual code is more like: ceil(sqrt(float(a)/b))

EDIT: Based on levis501's answer, I think I will do this:

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

Thank you all!

Answer 1

You may want to write an explicit function for your case. e.g.:

/* 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;
}

This will handle the odd case where the square root of your ratio a/b is within the precision of double.

Answer 2

I don't think it's possible. Regardless of the value of sqrt(a/b), what it produces is some value N that we use as:

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

Since ceil always produces an integer value (albeit represented as a double), we will always have some value X, for which the first produces X.0 and the second X.1. Conversion to int will always truncate that .1, so both will result in X.

It might seem like there would be an exception if X was so large that X.1 overflowed the range of double. I don't see where this could be possible though. Except close to 0 (where overflow isn't a concern) the square root of a number will always be smaller than the input number. Therefore, before ceil(N)+0.1 could overflow, the a/b being used as an input in sqrt(a/b) would have to have overflowed already.

Answer 3

Equality of floating point numbers is indeed an issue, but IMHO not if we deal with integer numbers.

If you have the case of 100.0/4.0, it should perfectly evaluate to 25.0, as 25.0 is exactly representable as a float, as opposite to e.g. 25.1.

Answer 4

Yes, it's entirely possible that s1 != s2. Why is that a problem, though? It seems natural enough that s1 != (s1 + 0.1).

BTW, if you would prefer to have 5.00001 rounded to 5.00000 instead of 6.00000, use rint instead of ceil.

---

And to answer the actual question (in your comment) - you can use sqrt to get a starting point and then just find the correct square using integer arithmetic.

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;
}

And yes, this can be improved a lot, it's just a quick sketch.

Answer 5

s1 will always equal s2.

The C and C++ standards do not say much about the accuracy of math routines. Taken literally, it is impossible for the standard to be implemented, since the C standard says sqrt(x) returns the square root of x, but the square root of two cannot be exactly represented in floating point.

Implementing routines with good performance that always return a correctly rounded result (in round-to-nearest mode, this means the result is the representable floating-point number that is nearest to the exact result, with ties resolved in favor of a low zero bit) is a difficult research problem. Good math libraries target accuracy less than 1 ULP (so one of the two nearest representable numbers is returned), perhaps something slightly more than .5 ULP. (An ULP is the Unit of Least Precision, the value of the low bit given a particular value in the exponent field.) Some math libraries may be significantly worse than this. You would have to ask your vendor or check the documentation for more information.

So sqrt may be slightly off. If the exact square root is an integer (within the range in which integers are exactly representable in floating-point) and the library guarantees errors are less than 1 ULP, then the result of sqrt must be exactly correct, because any result other than the exact result is at least 1 ULP away.

Similarly, if the library guarantees errors are less than 1 ULP, then ceil must return the exact result, again because the exact result is representable and any other result would be at least 1 ULP away. Additionally, the nature of ceil is such that I would expect any reasonable math library to always return an integer, even if the rest of the library were not high quality.

As for overflow cases, if ceil(x) were beyond the range where all integers are exactly representable, then ceil(x)+.1 is closer to ceil(x) than it is to any other representable number, so the rounded result of adding .1 to ceil(x) should be ceil(x) in any system implementing the floating-point standard (IEEE 754). That is provided you are in the default rounding mode, which is round-to-nearest. It is possible to change the rounding mode to something like round-toward-infinity, which could cause ceil(x)+.1 to be an integer higher than ceil(x).