An algorithm for finding an arbitrarily large number
Here's something I thought about: suppose you have a number, x, that can be infinitely large, and you have to figure out what it is. All you know is if the other number, y, is greater or less than x. What's the quickest / best way to find x?
The evil adversary chooses a really large number somehow ... let's say:
int x = 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9
and provides functions isX
, isBiggerThanX
and isSmallerThanx
. Sample 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, after the number y is found (which is greater than x), does something to determine x (for example, divide the number in half and compare that, then repeat). The thing is, since x is arbitrarily large, I feel bad about using a constant to increase y.
This is something I've been curious about for a while, I'd love to hear what other people think.
source to share
Use Binary Search as you would in a normal Try My Number game. But since there is no final upper endpoint, we do the first phase to find the appropriate one:
- The initially specified upper endpoint is arbitrary (e.g. 1,000,000, although 1 or 1 ^ 100 would also work - given infinite workspace, all endpoints are equally disproportionate).
- Compare the meaning of the mystery
X
with the upper endpoint. - If it's not big enough, double it and try again.
- As soon as the high end point is greater than the mystery number, do a normal binary search.
The first phase itself is similar to a binary search. The difference is that instead of halving the search space with each step, it doubles it! The cost of each phase is O(log X)
. A small improvement would be to set a lower endpoint at each doubling step: we know that it X
is at least higher than the previous upper endpoint, so we can use that as the lower endpoint. The size of the search space still doubles at every step, but at the end it will be half what it would be. The cost of a binary search will be reduced by just 1 step, so its overall complexity will remain the same.
Some notes
A couple of notes in response to other comments:
This is an interesting question, and computer science is not only something that can be done on physical machines. As long as the question can be defined correctly, it is worth asking and thinking.
The range of numbers is endless, but any possible mystery number is finite. So the above method will eventually find it. It is ultimately determined, for example, that for any possible final input, the algorithm will complete with a finite number of steps. However, since the entrance is unlimited, the number of steps is also unlimited (it's just that in each case it "eventually" ends.)
source to share
If I understand your question correctly (please let me know if I don't), you are asking how to solve "pick a number from 1 to 10", except that instead of 10, the upper bound is infinite.
If your number space is truly infinite, then the following is true:
- The value will never be stored in
int
(or any other data type) on any physical hardware - Will NEVER find your number
If the space is very large but related, I think the best you can do is binary search. Start in the middle of the number range. If the desired number is higher or lower, divide that half of the number and repeat until the desired number is found.
In your proposed implementation, you are raising y ^ c
. However, no matter how large it is c
chosen, it doesn't even move the needle into infinite space.
source to share
This is funny. I have wondered the same for years, although I have never heard anyone else ask the question.
As simple as your scenario is, it still seems to provide insufficient information to enable you to choose the optimal strategy. All you can choose is a suitable heuristic. My heuristic was to double up y
, but I think I like yours better. Yours doubles log(y)
.
The beauty of your heuristic is that as long as an integer fits into the computer's memory, it finds a fit y
in logarithmic time.
Counterquestion. Once you find out y
, how are you progressing?
source to share
I agree with using binary search, although I believe that ONE-SIDED binary search would be more appropriate as the complexity here will NOT be O (log n) [where n is the range of valid numbers], but O (log k) - where k is the number chosen by your opponent.
It will work like this: (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 valid range is infinite, if your number is finite, you should find it :)
source to share
Your tetration method is guaranteed to take longer than the age of the universe to find an answer if the adversary is simply using a paradigm that is better (e.g. pentation). This is how you should do it:
- You can only do this with symbolic representations of numbers, because it is trivial to name a number that your computer cannot store in floating point representation, even if it uses arbitrary precision arithmetic and all of its memory.
- Reading Required: http://www.scottaaronson.com/writings/bignumbers.html - this pretty much sums it up
- How do you represent the number? You present it with a program that, when run to completion, will print this number. Even then, your computer cannot compute BusyBeaver (10 ^ 100) (if you dictated the program size is 1 terabyte, this is over the maximum number of trailing clock cycles that it could run without cycling forever). You can see that we could easily print out the computer
1
0
0
... every tick, making the maximum number it could say (if we waited almost forever) would be 10 ^ BusyBeaver (10 ^ 100). If you let him say more complex expressions likeeval(someprogram)
, power towers, Ackermann function, whatever - then I think it would be no better than increasing the original 10 ^ 100 by some constant proportionality to the complexity of what you described (plus some logarithmic interpretation coefficient, see Kolmogorov complexity).
So let's frame like this:
Your opponent chooses a finite computable number and gives you a function indicating whether the number is less than / greater than / equal by computing it. It also gives you an idea of the output (in the sane world it would be "you can only print numbers like 99999", but it can complicate things, it doesn't really matter). Continue to measure the size of this function in bits.
Now respond with your own function that is twice its function (in bits) and produces the largest number it can, while keeping the code less than 2N bits long. (You are using the same representation he chose: in a world where you can only print numbers like "99999" that's what you do. If you can define functions it gets a little more complicated.)
source to share
I don't understand the purpose here, but that's what I was thinking:
Reading your comments, I assume you are not looking for an infinitely large number, but instead a " super large number ". And whatever the number, it will have a big no. numbers. How you got them is not a problem. With this in mind:
No complicated calculations required. Just enter random keys on the numeric keypad to have a super large number and then add / remove / change the digits of that number at random. You get a list of very large numbers - choose any of them.
eg: 3672036025039629036790672927305060260103610831569252706723680972067397267209
and keep modifying/adding digits to get more numbers
PS: If you clearly state the goal in your question, we can provide better answers.
source to share