Magic bouncing ball problem

Mary got a magic ball for her birthday. The ball, when thrown from some height, bounces for the double of this height. Mary's thrown the ball from her balcony which is x above the ground. Help her calculate how many bounces are there needed for the ball to reach whe height w.

Input: One integer z (1 ≤ z ≤ 10⁶) as the number of test cases. For every test, integers x开发者_JAVA百科 and w (1 ≤ x ≤ 10⁹, 0 ≤ w ≤ 10⁹).

Output: For every case one integer equal to the number of bounces needed fot the ball to reach w should be printed.

OK, so, though it looks unspeakably easy, I can't find a more efficient way to solve it than a simple, dumb, brutal approach of a loop multiplying x by 2 till it's at least w. For a maximum test, it will get a horrific time, of course. Then, I thought of using previous cases which saves quite a bit time providing that we can get the closest yet smaller result from the previous cases in a short time (O(1)?) which, however, I can't (and don't know if it's possible..) implement. How should this be done?

---

You are essentially trying to solve the problem

2ⁱ x = w

and then finding the smallest integer greater than i. Solving, we get

2ⁱ = w / x

i = log₂ (w / x)

So one approach would be to compute this value explicitly and then take the ceiling. Of course, you'd have to watch out for numerical instability when doing this. For example, if you are using floats to encode the values and then let w = 8,000,001 and x = 1,000,000, you will end up getting the wrong answer (3 instead of 4). If you use doubles to hold the value, you will also get the wrong answer when x = 1 and w = 536870912 (reporting 30 instead of 29, since 1 x 2²⁹ = 536870912, but due to inaccuracies in the double the answer is erroneously rounded up to 30). It looks like we'll have to switch to a different approach.

Let's revisit your initial solution of just doubling the value of x until it exceeds w should be perfectly fine here. The maximum number of times you can double x until it reaches w is given by log₂ (w/x), and since w/x is at most one billion, this iterates at most log₂ 10⁹ times, which is about thirty times each. Doing thirty iterations of a multiply by two is probably going to be extremely fast. More generally, if the upper bound of w / x is U, then this will take at most O(log U) time to complete. If you have k (x, w) pairs to check, this takes time O(k log U).

If you're not satisfied with doing this, though, there's another very fast algorithm you could try. Essentially, you want to compute log₂ w/x. You could start off by creating a table that lists all powers of two along with their logarithms. For example, your table might look like

T[1] = 0
T[2] = 1
T[4] = 2
T[8] = 3
...

You could then compute w/x, then do a binary search to figure out where in which range the value lies. The upper bound of this range is then the number of times the ball must bounce. This means that if you have k different pairs to inspect, and if you know that the maximum ratio of w/x is U, creating this table takes O(log U) time and each query then takes time proportional to the log of the size of the table, which is O(log log U). The overall runtime is then O(log U + k log log U), which is extremely good. Given that you're dealing with at most one million problem instances and that U is one billion, k log log U is just under five million, and log U is about thirty.

Finally, if you're willing to do some perversely awful stuff with bitwise hackery, since you know for a fact that w/x fits into a 32-bit word, you can use this bitwise trickery with IEEE doubles to compute the logarithm in a very small number of machine operations. This would probably be faster than the above two approaches, though I can't necessarily guarantee it.

Hope this helps!

---

Use this formula to calculate the number of bounces for each test case.

ceil( log(w/x) / log(2) )

This is pseudo-code, but it should be pretty simple to convert it to any language. Just replace log with a function that finds the logarithm of a number in some specific base and replace ceil with a function that rounds up a given decimal value to the next int above it (for example, ceil(2.3) = 3).

See http://www.purplemath.com/modules/solvexpo2.htm for why this works (in your case, you're trying to solve the equation x * 2 ^ n = w for an integer n, and you should start by dividing both sides by x).

EDIT:
Before using this method, you should check that w > x and return 1 if it isn't. (The ball always has to bounce at least once).

Also, it has been pointed out that inaccuracies in floating point values may cause this method to sometimes fail. You can work around this by checking if 2 ^ (n-1) >= w, where n is the result of the equation above, and if so returning (n - 1) instead of n.