Page 1 of 3

Bisection Method

Posted: Tue Jun 17, 2003 12:15 pm
by Observer
I've just used Bisection Method to solve 10341(Solve It) and 358(Don't Have a Cow, Dude).

I would like to know whether there are other problems which can be solved by this method.

Plz tell!!! Thx in advance.

Posted: Tue Jun 17, 2003 12:35 pm
by hager
The only one I can remember at the moment is 10297(Beavergnaw), but there are surely more of them. Anyway, it's a nice problem.

Best regards

Posted: Tue Jun 17, 2003 1:43 pm
by Observer
No, you don't need Bisection Method to solve Beavergnaw.
You can get the answer using just ONE formula! :lol:
Never mind, you can get ACC within 0.00.000 sec. with either method for sure!

Posted: Tue Jun 17, 2003 2:11 pm
by IIUC GOLD
Railway (10263) is a good problem which can be solved by Bisection method.

Posted: Tue Jun 17, 2003 10:29 pm
by Faizur
I am a new in computational geometry :( and wanna solve the problems related to it. Can any one give me any tips how to make the initial approximation while solving any problems like 358 using bisection method or N-R method.
In bisection method for a & b f(a) & f(b) should be of opposite sign.But how to determine a & b while implementing it in C???????

Posted: Wed Jun 18, 2003 5:03 am
by Observer
Faizur wrote:In bisection method for a & b f(a) & f(b) should be of opposite sign.But how to determine a & b while implementing it in C???????
Easy!

For instance, in Q358, first you should derive a formula f(x) = 0.
Then, you can clearly see that the function f(x) is strictly increasing.
Now choose the upper and lower limit. You may set 0 as the lower limit, and 2R as the upper limit.
Next, do the bisection!!
Finally, you get the answer easily!!!!!

By the way, what's "N-R Method"?? :-?

Railway is quite interesting! I didn't use bisection, though...

Posted: Wed Jun 18, 2003 7:45 am
by Dominik Michniewski
Newton-Raphson Method .... second name I may write wrong :( ...


Best reagrds
DM

Posted: Wed Jun 18, 2003 1:29 pm
by IIUC GOLD
You are correct Dominik Michniewski. NR is Newton-Raphson Method.

Another very good problem of Numerical method is The roots (10428). At first I tried it with Bisection method. But got either TLE or WA. Then I got accepted by applying NR method with Synthetic Division.

I am intersted to know the name of some other problems which should be solved numerically.

Posted: Thu Jun 19, 2003 5:04 am
by Observer
IIUC GOLD wrote:Another very good problem of Numerical method is The roots (10428). At first I tried it with Bisection method. But got either TLE or WA. Then I got accepted by applying NR method with Synthetic Division.
Hmm...... Multiple roots......... Let me think deeply......... Any hints??

Posted: Thu Jun 19, 2003 8:52 am
by anupam
i think nr method is preferrable and uses much less time than interval bisection methos.
because it's convergency is much greater than the former.
again nr method has some difficulty.
you must explicitely check whether it finds an infinity loop ro it finds roots in a very little distance.
this is the difficulties that is withdrawn by secant methos.
so i uses secant method. nr is also simpler to use.

Posted: Fri Jun 20, 2003 2:18 pm
by Junayeed
What will be condition for No Solution in the problem 10341 - Solve It.
I am using Bisection Method.

Posted: Fri Jun 20, 2003 3:20 pm
by anupam
actually, u can use a dfinite number of iteration.
after the no. of iteration if the value dnot converges then u can tell no soln.
but if it converges then it is the answer.
i think u 've go it.
--
anupam :oops: :oops:

Posted: Fri Jun 20, 2003 6:22 pm
by Moni
Yes! But be concious about the TOLERANCE !!!

Posted: Fri Jun 20, 2003 7:52 pm
by Junayeed
Thanks for the reply.

Thanks to all.

Posted: Sun Jun 22, 2003 2:07 pm
by anupam
well moni bhai,
i don't understand abt tollarence.
would u plz decribe a little bit more.
i used floor(x)==0 and ceil(x)==1 to check whether the ans is between 0 and 1.
then what is tollarence here>>? :oops: :oops: