Algorithm to find an arbitrarily large number

Question

Here's something I've been thinking about: suppose you have a number, x, that can be infinitely large, and you have to find out what it is. All you know is if another number, y, is larger or smaller than x. What would be the fastest/best way to find x?

An evil adversary chooses a really large number somehow ... say:

int x = 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9

and provides isX, isBiggerThanX, and isSmallerThanx functions. Example code might look something like this:

int c = 2
int y = 2
while(true)
    if isX(y) return true
    if(isBiggerThanX(y)) fn()
    else y = y^c

where fn() is a function that, once a number y has been found (that's bigger than x) does something to determine x (like divide the number in half and compare that, then repeat). The thing is, since x is arbitrarily large, it seems like a bad idea to me to use a constant to increase y.

This is just something that I've been wondering about for a while now, I'd like to hear what other people think

Answer 1

Use a binary search as in the usual "try to guess my number" game. But since there is no finite upper end point, we do a first phase to find a suitable one:

• Initially set the upper end point arbitrarily (e.g. 1000000, though 1 or 1^100 would also work -- given the infinite space to work in, all finite values are equally disproportionate).
• Compare the mystery number X with the upper end point.
• If it's not big enough, double it, and try again.
• Once the upper end point is bigger than the mystery number, proceed with a normal binary search.

The first phase is itself similar to a binary search. The difference is that instead of halving the search space with each step, it's doubling it! The cost for each phase is O(log X). A small improvement would be to set the lower end point at each doubling step: we know X is at least as high as the previous upper end point, so we can reuse it as the lower end point. The size of the search space still doubles at each step, but in the end it will be half as large as would have been. The cost of the binary search will be reduced by only 1 step, so its overall complexity remains the same.

Some notes

A couple of notes in response to other comments:

It's an interesting question, and computer science is not just about what can be done on physical machines. As long as the question can be defined properly, it's worth asking and thinking about.

The range of numbers is infinite, but any possible mystery number is finite. So the above method will eventually find it. Eventually is defined such as that, for any possible finite input, the algorithm will terminate within a finite number of steps. However since the input is unbounded, the number of steps is also unbounded (it's just that, in every particular case, it will "eventually" terminate.)

Answer 2

If I understand your question correctly (advise if I do not), you're asking about how to solve "pick a number from 1 to 10", except that instead of 10, the upper bound is infinity.

If your number space is truly infinite, the following are true:

• The value will never be held in an int (or any other data type) on any physical hardware
• You will NEVER find your number

If the space is immensely large but bound, I think the best you can do is a binary search. Start at the middle of the number range. If the desired number turns out to be higher or lower, divide that half of the number space, and repeat until the desired number is found.

In your suggested implementation you raise y ^ c. However, no matter how large c is chosen to be, it will not even move the needle in infinite space.

Answer 3

Infinity isn't a number. Thus you can't find it, even with a computer.

Answer 4

That's funny. I've wondered the same thing for years, though I've never heard anyone else ask the question.

As simple as your scenario is, it still seems to provide insufficient information to allow the choice of an optimal strategy. All one can choose is a suitable heuristic. My heuristic had been to double y, but I think that I like yours better. Yours doubles log(y).

The beauty of your heuristic is that, so long as the integer fits in the computer's memory, it finds a suitable y in logarithmic time.

Counter-question. Once you find y, how do you proceed?

Answer 5

I agree with using binary search, though I believe that a ONE-SIDED binary search would be more suitable, since here the complexity would NOT be O( log n ) [ Where n is the range of allowable numbers ], but O( log k ) - where k is the number selected by your adversary.

This would work as follows : ( Pseudocode )

k = 1;

while( isSmallerThanX( k ) )
{
   k = k*2;
}

// At this point, once the loop is exited, k is bigger than x
// Now do normal binary search for the range [ k/2, k ] to  find your number :)

So even if the allowable range is infinity, as long as your number is finite, you should be able to find it :)

Answer 6

Your method of tetration is guaranteed to take longer than the age of the universe to find an answer, if the opponent merely uses a paradigm which is better (for example, pentation). This is how you should do it:

1. You can only do this with symbolic representations of numbers, because it is trivial to name a number your computer cannot store in floating-point representation, even if it used arbitrary-precision arithmetic and all its memory.
2. Required reading: http://www.scottaaronson.com/writings/bignumbers.html - that pretty much sums it up
3. How do you represent a number then? You represent it by a program which will, if run to completion, print out that number. Even then, your computer is incapable of computing BusyBeaver(10^100) (if you dictated a program 1 terabyte in size, this well over the maximum number of finite clock cycles it could run without looping forever). You can see that we could easily have the computer print out 1 0 0... each clock cycle, making the maximum number it could say (if we waited nearly an eternity) would be 10^BusyBeaver(10^100). If you allowed it to say more complicated expressions like eval(someprogram), power-towers, Ackermann's function, whatever-- then I believe that would be no better than increasing the original 10^100 by some constant proportional to the complexity of what you described (plus some logarithmic interpreter factor, see Kolmogorov complexity).

So let's frame this another way:

Your opponent picks a finite computable number, and gives you a function tells you if the number is smaller/larger/equal by computing it. He also gives you a representation for the output (in a sane world this would be "you can only print numbers like 99999", but he can make it more complicated; it actually doesn't matter). Proceed to measure the size of this function in bits.

Now, answer with your own function, which is twice the size of his function (in bits), and prints out the largest number it can while keeping the code to less than 2N bits in length. (You use the same representation he chose: In a world where you can only print out numbers like "99999", that's what you do. If you can define functions, it gets slightly more complicated.)

Answer 7

I do not understand the purpose here, but I this is what I thought of:

Reading your comments, I suppose you aren't looking for infinitely large number, but a "super large number" instead. And whatever be the number, it will have a large no. of digits. How you got them, isn't the concern. Keeping this in mind:

No complex computation is required. Just type random keys on your numeric keyboard to have a super large number, and then have a program randomly add/remove/modify digits of that number. You get a list of very large numbers - select any one out of them.

e.g: 3672036025039629036790672927305060260103610831569252706723680972067397267209 and keep modifying/adding digits to get more numbers

PS: If you state the purpose in your question clearly, we might be able to give better answers.