Guess unlimited integer

Question

If I tell you:

"I think of a number from 0 to n, and I will tell you if your assumption is high or low," then you will immediately reach the binary search.

What if i delete the upper border? those. I think of positive integers, and you need to guess it.

One possible way is to guess 2, 4, 8, ... until you guess 2 ** k for some k, and I say "below." Then you can apply binary search.

Is there a faster method?

EDIT:

It is clear that any decision will take time proportional to the size of the target number. If I take the Graham number through the Ackerman function, we will wait until what strategy you pursue.

I could also suggest this algorithm: guess each integer in turn, starting at 1.

It is guaranteed to end in a finite time, but still it is clearly much worse than my "force 2" strategy. If I can find the worst algorithm (and I know that it is worse), then maybe I can find the best?

For example, instead of degrees 2, perhaps I can use powers of 10. Then I find the upper bound in steps of log_10(n) instead of steps of log_2(n) . But I have to look for more space. Say k = ceil(log_10(n)) . Then I need the log_2(10**k - 10**(k-1)) steps for my binary search, which I think is about 10+log_2(k) . For credentials 2, I have roughly log_2(log_2(n)) steps for my search phase. What is the gain?

What if I look up using n**n ? Or some other sequence? Does it win for those who can find the sequence that grows fastest? Is this a problem with the answer?

Thanks for your thoughts. And my apologies to those you offer, I start with MAX_INT or 2 ** 32-1, as I am clearly shying away from the limits of practicality here.

COMPLETION:

Hello to all,

Thank you for your responses. I accepted the answer of Norman Ramsey (and the commentator one by one) for what I understood as the following argument: for the target number n, any strategy should be able to distinguish (at least) the numbers from 0..n, which means you need (by at least) O (log (n)) comparison.

However, you also pointed out that the problem is not defined in the first place, since it is impossible to choose a “random positive integer” with a uniform probability distribution (or, rather, a uniform probability distribution cannot exist over an infinite set). And as soon as I give you an uneven distribution, you can split it in half and apply the binary search as usual.

This is a problem that I often thought about when I get around, so I'm glad that I have two convincing answers.

Answer 1

In the worst case, you can find it in time by the logarithmic size of the answer, using exactly the methods that you describe. You can use the Ackerman function to find the upper bound faster than the logarithmic time, but then a binary search between the specified number and the previous assumption will require logarithmic time in the size of the interval, which (if guesses grow very quickly) is close to the logarithmic size of the answer.

It would be interesting to try to prove that there is no faster algorithm (for example, O (log log n)), but I have no idea how to do this.

Answer 2

If there really is no upper bound, and all numbers are infinitely equally probable, then there is no optimal way to do this. For any final conjecture G, the probability that a number is lower than G is zero, and the probability that it is higher is equal to 1 - therefore there is no final conjecture that has the expectation of being higher than a number.

ANSWER TO JOHN EDIT :

For the same reasons, it is expected that degrees 10 are better than degrees 2 (there is only a finite number of possible Ns for which degrees 2 are better, and an infinite number where degree 10 is better), a power of 20 can be better than degrees 10.

So, in principle, yes, the gain is in the fastest growing sequence (and for the same sequence - the highest starting point) - for any given sequence it can be shown that a faster growing sequence will win in an infinitely larger number of cases. And since for any sequence that you name, I can name one that grows faster, and for any integer that you name, I can name one above, there is no answer that cannot be improved. (And each algorithm that ultimately gives the correct answer has the expected number of guesses, which is infinite, anyway).

Answer 3

People who have never studied probability are inclined to think that “choosing a number from 1 to N” means “with equal probability of each,” and they act according to their intuitive understanding of probability.

Then, when you say, “choose any positive integer,” they still think it means “everyone is equally likely.”

This, of course, is impossible - there is no discrete probability distribution with a region of positive integers, where p (n) == p (m) for all n, m.

So, the person choosing the number had to use a different probability distribution. If you don't know anything about this distribution at all, you should base your guessing scheme on this knowledge in order to have the “fastest” solution.

The only way to calculate how “fast” a given guessing scheme is to calculate the expected number of guesses to find the answer. You can only do this by assuming a probability distribution for the target number. For example, if they chose n with a probability of (1/2) ^ n, then I think your best guessing scheme is "1", "2", "3", ... (on average 2 guesses). However, I did not prove this, maybe this is some other sequence of conjectures. Of course, guesswork should start small and grow slowly. If they chose 4 with probability 1 and all other numbers with probability 0, then your best guessing scheme is “4” (on average 1 guess). If they chose a number from 1 to a trillion with a uniform distribution, you should perform a binary search (an average of about 40 guesses).

I say the only way to define “fast” is by looking at the worst case. You must accept the binding to the target in order to prevent all circuits from having the same speed, namely: "there is no binding to the worst case." But you don’t have to accept the distribution, and the answer to the “fastest” algorithm in this definition is obvious - a binary search starting at the border you choose. So I'm not sure this definition is terribly interesting ...

In practice, you do not know the distribution, but you can make a few educated guesses based on the fact that the collector is a person, and what figures people can understand. As someone says, if the number they chose is Ackerman's function for the Graham number, then you probably have problems. But if you know that they are able to display their chosen number in numbers, then this actually sets the upper limit of the number that they could choose. But it all the same depends on what methods they could use to generate and record the number, and therefore what your best knowledge is, the probability that the number will be of each specific value.

Answer 4

Mathematically speaking:

You can never find this integer. In fact, strictly speaking, the statement “choose any positive integer” is meaningless because it is impossible to do: although you, as a person, can believe that you can do this, you actually choose from a limited set - you simply do not recognize the boundaries .

Computationally speaking:

Computationally, we never deal with infinities, since we would not have a way of storing or checking for any number greater than, say, the theoretical maximum number of electrons in the Universe. Thus, if you can estimate the maximum depending on the number of bits used in the register on the device in question, you can perform a binary search.

Answer 5

Binary search can be generalized: each time the set of possible options should be divided into subsets with a probability of 0.5. In this case, it is still applicable to infinite sets, but still requires knowledge of the distribution (for finite sets, this requirement is forgotten quite often) ...

Answer 6

My main guess is that I will start with a higher first guess instead of 2, about the average of what I expect from them. Starting at 64, you save 5 guesses, starting at 2 when the number is greater than 64, at a cost of less than 1-5. 2 makes sense if you expect the answer to be about 1 or 2 times. You could even keep a memory of past answers to decide the best of the first assumptions. Another improvement could be an attempt at denial when they say “lower” by 0.

Answer 7

Use a binary search starting with MAX_INT / 2, where MAX_INT is the largest number your platform can handle.

It makes no sense to pretend that we can have endless possibilities.

UPDATE: Given that you insist on entering the realms of infinity, I will just vote to close your question as non-programming :-)

Answer 8

If this guesses the upper bound of the number generated by the computer, I would start with 2 ** [number of bits / 2], and then increase or decrease the strength by two. This, at least, brings you as close as possible to the possible values ​​in the least number of jumps.

However, if this is a purely mathematical number, you can start with any value, since you have an infinite range of values, so your approach will be fine.

Answer 9

The standard standard assumption of a uniform distribution for all natural numbers does not lead to a solution, so you should start by determining the probability distribution of numbers for guessing.

Answer 10

Since you do not indicate the probability distribution of numbers (as others correctly noted, there is no uniform distribution over all positive integers), There is no free lunch theorem , give the answer: any method (which does not repeat the same number twice) is as good as any other.

As soon as you start making assumptions about the distribution (fx is a person or a binary computer, etc., that selects a number), this, of course, changes, but, as the task says, any algorithm is as good as any other averaging over all possible distributions.

Answer 11

I would probably start guessing with the Graham Number.

Answer 12

A practical answer in a computational context would be to start with what is the highest number that can (realistically) be represented by the type you are using. In the case of some type of BigInt, you probably want to make a judgment about what is realistic ... it is obvious that ultimately the border in this case is available memory ... but the performance compared to something less can be more realistic.

Answer 13

Your starting point should be the largest number you can think of, plus 1.

There is no “effective search” for a number in the infinite range.

EDIT: just to clarify, for any number that you can think of, there are still infinitely more numbers that are “bigger” than your number, compared to a finite set of numbers that are “less” than your number. Therefore, assuming that the selected number is randomly selected from all positive numbers, you have zero | (approaching zero) chance to be "above" the selected number.