My Math Forum Binary Search

 Applied Math Applied Math Forum

 May 7th, 2018, 12:44 PM #1 Newbie   Joined: Jan 2016 From: england Posts: 17 Thanks: 0 Binary Search If f(x)=0 and a0 f((a+b)/2)>0 By using a binary search, how many iterations would be needed to arrive at an answer correct to 4dp? I'm completely lost here, am I looking in the right place with Binary logarithms? I have found the following: log_2⁡x=n+log_2⁡y where y=2^(-n) x and y∈[1,2) But I'm not sure if I'm barking up the wrong tree here. Please help...!
May 7th, 2018, 12:51 PM   #2
Global Moderator

Joined: Dec 2006

Posts: 20,274
Thanks: 1959

Quote:
 Originally Posted by Skykai . . . would be needed to arrive at an answer correct to 4dp?

 May 7th, 2018, 02:04 PM #3 Newbie   Joined: Jan 2016 From: england Posts: 17 Thanks: 0 Sorry, the solution to f(x)=0. I am trying to determine the amount of calculations it would take, in terms of a and b, to find an answer that would be correct to 4dp. By calculations I mean, 1st calculation is f(a), 2nd is f(b) and 3rd is f((a+b)/2). These then repeat in the binary search
 May 7th, 2018, 02:31 PM #4 Global Moderator   Joined: May 2007 Posts: 6,683 Thanks: 658 There is no obvious solution, because the shape of the function may preclude it. A function which is almost flat {negative} from a to a point near be and then starts rising rapidly to be positive at be would have a zero near b which would take many steps to find.
 May 7th, 2018, 08:50 PM #5 Senior Member   Joined: Sep 2016 From: USA Posts: 556 Thanks: 321 Math Focus: Dynamical systems, analytic function theory, numerics This question is meaningless. Find an answer to what? Is $f$ continuous? monotone? Lipschitz? I suspect you are leaving out a great deal of information. Assuming you are looking to converge to a zero of $f$? How would you use binary search for the function $f(x) = \left\{ \begin{array}{cc} 1 & x \in \mathbb{Q} \\ 0 & x \notin \mathbb{Q} \end{array} \right.$ with $a,b$ irrational (and algebraically independent)? What about the function $f(x) = \frac{1}{x}$?
 May 8th, 2018, 12:32 AM #6 Senior Member   Joined: Aug 2012 Posts: 2,156 Thanks: 630 I think binary search just means that we take the midpoint of the interval and ask if the zero is in the left or right subinterval defined by that midpoint. Then we take the left or right subinterval and test with its midpoint. In this way we are guaranteed to be within $\frac{1}{2^n}$ of the zero after $n$ iterations. That's if we start with the interval $(a,b) = (0,1)$ for simplicity. In this case we are given that $f(\frac{a+b}{2}) > 0$. So we can skip the first iteration since we are told that the zero must be in the left half of the starting interval. Perhaps they mean for us to take this into account. Now four decimal places is $.0001 = \frac{1}{10^4} > \frac{1}{2^{10}}$ so normally we'd need 10 iterations to guarantee that our trial value is within four decimal places of the actual zero. But we got the first iteration for free, so the answer is 9. That last bit's a bit speculative but why else would they tell us the value at the initial midpoint? That's how I would interpret this problem. It's entirely independent of the nature of $f$, which could be arbitrarily wild and it would make no difference. The assumption is that there is an oracle that, given n, returns "left," "right," or "bingo" when you input the n-th subinterval. Once you have that it's just a matter of seeing how finely you need to chop up the original interval with negative integer power of 2 -sized subintervals to get as close as you want to the actual zero. Of course, this answer of 9 (or 10, depending how you interpret it) iterations is the max. In special cases it could be less. For example, if $f$ is the characteristic function of the rationals, you can pick any value of $x$ at all and be certain you're within four decimal places of some zero of the function. Thanks from Skykai Last edited by skipjack; May 8th, 2018 at 10:02 AM.
 May 8th, 2018, 12:47 AM #7 Newbie   Joined: Jan 2016 From: england Posts: 17 Thanks: 0 Thanks so much Maschke, this is exactly what I was looking for, you've explained it perfectly. Thank you!!
May 8th, 2018, 12:51 AM   #8
Senior Member

Joined: Oct 2009

Posts: 733
Thanks: 246

Quote:
 Originally Posted by Maschke I think binary search just means that we take the midpoint of the interval and ask if the zero is in the left or right subinterval defined by that midpoint. Then we take the left or right subinterval and test with its midpoint. In this way we are guaranteed to be within $\frac{1}{2^n}$ of the zero after $n$ iterations. That's if we start with the interval $(a,b) = (0,1)$ for simplicity. In this case we are given that $f(\frac{a+b}{2}) > 0$. So we can skip the first iteration since we are told that the zero must be in the left half of the starting interval. Perhaps they mean for us to take this into account. Now four decimal places is $.0001 = \frac{1}{10^4} > \frac{1}{2^{10}}$ so normally we'd need 10 iterations to guarantee that our trial value is within four decimal places of the actual zero. But we got the first iteration for free, so the answer is 9. That last bit's a bit speculative but why else would they tell us the value at the initial midpoint? That's how I would interpret this problem. It's entirely independent of the nature of $f$, which could be arbitrarily wild and it would make no difference. The assumption is that there is an oracle that, given n, returns "left," "right," or "bingo" when you input the n-th subinterval. Once you have that it's just a matter of seeing how finely you need to chop up the original interval with negative integer power of 2 -sized subintervals to get as close as you want to the actual zero. Of course, this answer of 9 (or 10, depending how you interpret it) iterations is the max. In special cases it could be less. For example, if $f$ is the characteristic function of the rationals, you can pick any value of $x$ at all and be certain you're within four decimal places of some zero of the function.
It's still crucial the function is continuous though, to even guarantee the existence of a root to begin with.

Last edited by skipjack; May 8th, 2018 at 10:03 AM.

May 8th, 2018, 09:48 AM   #9
Senior Member

Joined: Aug 2012

Posts: 2,156
Thanks: 630

Quote:
 Originally Posted by Micrm@ss It's still crucial the function is continuous though, to even guarantee the existence of a root to begin with.
As I understand this problem, it's only necessary that the function has at least one root; and that there's an oracle that responds "left" or "right" or "bingo" correctly. The OP said there's at least one root.

I agree with you that the condition that f(a) and f(b) are on opposite sides of the real line is a clue that OP was being asked about continuous functions, but we don't actually need that assumption for this problem.

Last edited by Maschke; May 8th, 2018 at 09:56 AM.

 May 9th, 2018, 07:36 PM #10 Senior Member   Joined: Aug 2012 Posts: 2,156 Thanks: 630 p.s.: $.0001 = \frac{1}{10^4} > \frac{1}{2^{10}}$ is wrong of course. The right-hand side of the inequality should be $\frac{1}{2^{14}}$. Last edited by skipjack; May 9th, 2018 at 07:57 PM.

 Tags binary, search

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post motant Computer Science 0 April 19th, 2015 01:43 PM flexdec Applied Math 0 July 16th, 2013 06:25 AM andreaugust Number Theory 2 July 15th, 2013 06:30 AM thescratchy Calculus 6 March 5th, 2011 07:41 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top