7
$\begingroup$

Problem Background:

Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean values according to the following rules:

  • When $x>a$, the output is True.
  • When $x<a$, the output is False.

Given $k$, we need to find a number $b$ such that

$$ |a-b|<10^{-k},\quad b>a,\quad \text{$b$ has $k$ decimal places} $$

For example, let $a=\sqrt{2}/2\approx0.70710678\cdots$, $k=3$, then $b$ should be $0.708$.

Here again: we don't know $a$, our purpose is to find $b$.

I thought of four ways to find $b$, listed below:

(The next four methods all use the above example)


Linear search:

Generate a list of length $1001$ in steps of $0.001$:

$$ [0, 0.001, 0.002, \cdots,0.998,0.999, 1] $$

Traverse this list, for each value $x$ in it, put it into the black box, if the output is True, stop traversing immediately, and $x$ at this time is $b$.

The time complexity of this method is: $O(10^k)$.


Binary Search:

Generate a list of length $1001$ in steps of $0.001$:

$$ [0, 0.001, 0.002, \cdots,0.998,0.999, 1] $$

Set two pointers. At first, the index of the left pointer is $0$ and the index of the right pointer is $1000$.

Calculate mid = (left + right) // 2.

Put the $x$ value at mid into the black box, if the output is True, move the right pointer to mid, otherwise move the left pointer to mid.

Repeat the above steps until left = right - 1, then the $x$ at the right pointer is $b$.

The time complexity of this method is: $O(k\log10)$.


Linear Search + Use Previous Results:

Step 1:

$$ [0, 1]\to[0.0, 0.1, 0.2, \cdots,0.9, 1.0]\to [0.7,0.8] $$

Step 2:

$$ [0.7,0.8]\to[0.70,0.71,0.72,\cdots,0.79,0.80]\to[0.70, 0.71] $$

Step 3:

$$ [0.70,0.71]\to[0.700,0.701,0.702,\cdots,0.709,0.710]\to[0.707, 0.708]\to 0.708 $$

The time complexity of this method is: $O(10k)$


Binary Search + Use Previous Results:

Similar to the method above, The time complexity of this method is: $O(k\log10)$


Are there any faster algorithms? If so, what is it?

$\endgroup$
4
  • 5
    $\begingroup$ A minor point: perhaps it is more realistic that the input to the black box is a rational number. After all, a rational has a finite representation, which is only the case for countably many reals, however you go about it. Moreover, if the input can be real, you have not specified the output when the input is $a$ itself. With rational numbers this is essentially how Dedekind cuts define the reals in terms of the rationals. $\endgroup$
    – PJTraill
    Feb 25 at 20:20
  • 5
    $\begingroup$ From what distribution is $a$ drawn? Any knowledge you have -- say, that larger numbers are more common -- can improve your efficiency. (Current answers appear to assume $a$ is drawn from a uniform distribution.) $\endgroup$ Feb 26 at 1:26
  • 6
    $\begingroup$ You can't get better than binary search, unless the probabilities of the possible results (a) are not equally distributed, or unless you get a better oracle (that e.g. tells you roughly how close you came, instead of just returning a boolean). $\endgroup$
    – Bergi
    Feb 26 at 18:09
  • $\begingroup$ What is the output of the black box when $a=x$ ? You cannot exclude this possibility without knowing $a$ as well (which you state is unknown) which would make the problem mute. If the output is not defined in that case then a test could return a false positive or negative which would make a mess of the search process. While the probability of $x=a$ is low it cannot be excluded and I see no point in excluding this possibility. $\endgroup$ Feb 27 at 2:19

3 Answers 3

28
$\begingroup$

You are in fact asked to find $b$ independent bits of information (such that $2^{-b}\sim10^{-k}$)*, using queries that return a single bit of information each. So you can't get an answer in less than $b$ queries, and this is achieved by binary search.


*Justification: the problem is equivalent to finding an integer $n$ such that $|a\cdot10^k-n|<1$, with $n$ in range $[0,10^k]\sim[0,2^b]$.

$\endgroup$
18
$\begingroup$

Let's suppose for a moment that instead of finding a decimal expansion, you're trying to find a binary expansion; you want to find the irrational number to $k$ binary places.

Then the information theory problem is straightforward. You are trying to discover $k$ bits of information. Each query gives you exactly $1$ bit of information. Therefore any correct algorithm must perform at least $k$ queries. There is no way around this.

Now in the decimal case, you are trying to discover between $\left\lfloor k \log 10\right \rfloor$ and $\left\lceil k \log 10\right \rceil$ bits of information. So, once again, any correct algorithm must perform at least $\left\lceil k \log 10\right \rceil$ queries in the worst case.

$\endgroup$
1
  • 8
    $\begingroup$ In the current case, a more fundamental, though essentially equivalent, approach is to observe that $k$ queries can have at most $2^k$ distinct outcomes, so can only distinguish that many numbers. Information theory, with the concept of a ''bit of information'', comes into its own when events have probability ≠ ½. $\endgroup$
    – PJTraill
    Feb 25 at 20:37
5
$\begingroup$

Well, $O(k\log10) = O(k) = O(k\log_210)$, and $k\log_210$ is the amount of bits of information needed, so if you have a process that can only return $1$ bit per query, you'll need that many queries. There are cases where the queries can return more than $1$ bit, however. For instance, there's something called a "timing attack" where you design the queries to take a different amount of time based on the number. Asking "Is $100$ greater than $1$?" might take less time than asking "Is $\pi$ greater than $\sqrt 10$?" Then the amount of time you have to wait to get your answer gives you additional information. But as long the number of additional bits doesn't depend on $k$, this doesn't affect the time complexity (big O notation doesn't care about constant multiples). Of course, using a timing attack usually means using more time, even if it's fewer queries.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.