2

While searching for a way to do a faster ceil operator than ceil itself, I came upon this:

var ceilX = (X + 1) >> 0

Which does a bit of bitwise magic to shave off the decimal, but ultimately fails to do a correct ceil operation because (1 + 1) >> 0 === 2, while ceil(1) === 1.

There's a different question on how to do this here, but the line of thought got me wondering if there's a way to add a number that's baaaaarely less than 1 to a value and then use the bitwise shift to round it. This seems to me like it should work for everything that can be expressed as a 32-bit number, but I'm not sure how to get the number that's really close to 1. In the name of pointless micro optimization, is there a good way of doing this?

Community
  • 1
  • 1
ckersch
  • 7,507
  • 2
  • 37
  • 44
  • 1
    why should this approach work? won't floating point rounding mess it up? – guest Jun 09 '14 at 23:23
  • 1
    That method of doing a `ceil` operation doesn't actually work, but it seems like (1 + barelyLessThanOne) >> 0 should – ckersch Jun 09 '14 at 23:24
  • but what about larger values? suppose `1 + (barely 1)` comes out to just under `2`. what if `1000 + (barely 1)` rounds up to `1001`? – guest Jun 09 '14 at 23:24
  • 1
    A problem is that the difference between integers is not fixed throughout the range for relative precision floating-point values (e.g. the number type). – user2864740 Jun 09 '14 at 23:26
  • 1
    the goal here is to use the `>>` operator, which operates on only 32 bits. if we agree to use this only on numbers that would fit in 32 bits, the smallest difference between numbers will be less than 1 – guest Jun 09 '14 at 23:27
  • In that case, is there a way to get the largest number less than the precision of a given number? – ckersch Jun 09 '14 at 23:28
  • I.e., there should be a number, n, for any given X, such that (X + n) >> 0 === ceil(X) – ckersch Jun 09 '14 at 23:29
  • @guest Good point, I redacted that bit of my previous comment. – user2864740 Jun 09 '14 at 23:29
  • Just convert `00111111011111111111111111111111` to a float, it's the closest possible number to one in IEEE754 single precision. – Etheryte Jun 09 '14 at 23:33

2 Answers2

0

In non IE browsers the Number.EPSILON property represents the difference between one and the smallest value greater than one. So to get to your largest number less one would be 1-Number.EPSILON

You can also calculate an Epsilon value by recursively dividing 1 by 2 until it equals zero and then taking the number from the second last step. This will produce a smaller value than Number.EPSILON.

Both methods are shown in the below fiddle along with comparisons to the internal ceil function and unfortunately neither epsilon methods match the internal method exactly but do ok up to an arbitrary precision. The bit-shifting method also shows no performance improvement in Chrome over the standard function. So even as far as pointless micro optimization goes this would achieve little.

http://jsfiddle.net/J8H8e/1/

David Ewen
  • 3,632
  • 1
  • 19
  • 30
0

Number.EPSILON provides the correct answer for X = 1, but for larger numbers, the largest number n less than one such that (X + n) >> 0 === ceil(X) is based on the exponent of the number. This is based on the way that doubles are structured, with an exponent and a significand. The precision of the last bit of the significand is based on the exponent, and gives the precision of the number represented.

Specifically, the number can be computed as follows:

var relEps = Number.EPSILON * ((1 << (((Math.log(X) / Math.LN2) | 0) - 1)) + 1)

After which:

(X + (1 - relEps)) >> 0 === ceil(X)

I'm pretty sure this is slower than ceil(X), but it was fun to figure out.

For something that's actually faster than ceil, this gives a lower bound that shows that

(X + (1 - X * Number.EPSILON)) >> 0

Will work for X !== 0. This is faster than native ceil.

ckersch
  • 7,507
  • 2
  • 37
  • 44