In Q #1a you specify that if the function doesn't find a root, then it should return None. How many tries should the function perform? What is sufficient to satisfy "can't find"?
Date: 04 Dec 2012 19:07
Number of posts: 7
RSS: New posts
This is a good question, and there is no clear answer for that.
In general, you could set a maximum number of times the recursive function can be called - but we are not interested in that here.
Since you are performing a binary search, you can write the termination criteria in the binary search loop, and there is no need to limit the number of iterations using another mechanism. If the loop is exhausted (without finding the root), then it would return None.
I also have a questoin - Why in the example, findRoot(lambda x : x**2, -10, 10) given in the HW, the function doesn't return 0 as the result?
0 is a value of X that for this function will return 0…
What am I missunderstanding here?
Ohh. I figured out it happens because you added the contain that F(a) < 0 < F(b) or F(a) > 0 > F(b).
But in cases that the function is always possitive (like abs(x) or x**2), you will always give up because of this. Even if the function does have a root.
Should we remove this contain and have a different halting condition (I have thought about another one that in my opinion works better), or should we stick to your implementation because of your automatic tests?
Why do you expect that we use binary search ? It's not mentioned in the question. I managed to adapt Newton-Raphson algo to the expected input. The only problem is that it doesn't detect F(a) < 0 < F(b) or F(a) > 0 > F(b) constraint, so for X**2 it returns 0.
Bare in mind that Newton-Raphson assumes a differentiable function (see slide 8 in the lecture), which is not given in the question.
In additions, in this question we limit ourselves to an interval [a,b], which is not the case in NR.
ok thanks for clarification. And now for something somewhat different ;) : given function may oscillate before crossing x axis, meaning we have a non-sorted array of values, that is non-sortable as it's a function… so we have to do a binary search in both sides ?