patternMajor
What is the fastest algorithm to approximate an irrational number with specified precision?
Viewed 0 times
theapproximatenumberwhatwithprecisionirrationalalgorithmfastestspecified
Problem
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:
Given $k$, we need to find a number $b$ such that
$$
|a-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 t
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, the output is False.
Given $k$, we need to find a number $b$ such that
$$
|a-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 t
Solution
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 in the worst case, 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]$.
*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]$.
Context
StackExchange Computer Science Q#149446, answer score: 30
Revisions (0)
No revisions yet.