查找任意大数的算法 [英] Algorithm to find an arbitrarily large number

问题描述

这是我一直在想的事情：假设您有一个数字x，它可以无穷大，您必须找出它的含义。您所知道的是，另一个数字y是否大于或小于x。

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

并提供 isX ， isBiggerThanX 和 isSmallerThanx 函数。示例代码可能如下所示：

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

其中， fn（）是一个函数，一旦找到数字y（大于x ）进行确定x的操作（例如将数字除半然后进行比较，然后重复）。问题是，由于x任意大，使用常数增加y对我来说似乎是个坏主意。

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

推荐答案

像往常一样使用二进制搜索尝试猜测我的号码游戏。但是由于没有上限，所以我们进行第一阶段以找到合适的上限：

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:

• 最初任意设置上限（例如1000000，尽管1或1 ^ 100也可以工作-给定无限的工作空间，所有有限值都是不成比例的。）


• 比较神秘数 X ，最高点。


• 如果大小不够，请将其加倍，然后重试。


• 一旦上端点大于神秘数，则继续进行常规的二进制搜索。

• 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.

第一阶段本身类似于二进制搜索。所不同的是，与其将搜索空间每一步减少一半，不如将其加倍！每个阶段的成本为 O（log X）。一个小的改进将是在每个加倍步骤中设置较低的端点：我们知道 X 至少与先前的较高端点一样高，因此我们可以将其重用为下端点。搜索空间的大小仍会在每一步增加一倍，但最终将是原来的一半。二进制搜索的成本将仅降低1步，因此其总体复杂性保持不变。

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.

一些说明

回应其他评论的几点注意事项：

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.)

这篇关于查找任意大数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！