Bisection Method

Observer · Post by **Observer** » Tue Jun 17, 2003 12:15 pm

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.

hager · Post by **hager** » Tue Jun 17, 2003 12:35 pm

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

Observer · Post by **Observer** » Tue Jun 17, 2003 1:43 pm

No, you don't need Bisection Method to solve Beavergnaw.
You can get the answer using just ONE formula!

Never mind, you can get ACC within 0.00.000 sec. with either method for sure!

IIUC GOLD · Post by **IIUC GOLD** » Tue Jun 17, 2003 2:11 pm

Railway (10263) is a good problem which can be solved by Bisection method.

Faizur · Post by **Faizur** » Tue Jun 17, 2003 10:29 pm

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???????

Observer · Post by **Observer** » Wed Jun 18, 2003 5:03 am

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...

Dominik Michniewski · Post by **Dominik Michniewski** » Wed Jun 18, 2003 7:45 am

Newton-Raphson Method .... second name I may write wrong

...

Best reagrds
DM

IIUC GOLD · Post by **IIUC GOLD** » Wed Jun 18, 2003 1:29 pm

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.

Observer · Post by **Observer** » Thu Jun 19, 2003 5:04 am

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??

anupam · Post by **anupam** » Thu Jun 19, 2003 8:52 am

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.

Junayeed · Post by **Junayeed** » Fri Jun 20, 2003 2:18 pm

What will be condition for No Solution in the problem 10341 - Solve It.
I am using Bisection Method.

anupam · Post by **anupam** » Fri Jun 20, 2003 3:20 pm

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

Moni · Post by **Moni** » Fri Jun 20, 2003 6:22 pm

Yes! But be concious about the TOLERANCE !!!

Junayeed · Post by **Junayeed** » Fri Jun 20, 2003 7:52 pm

Thanks for the reply.

Thanks to all.

anupam · Post by **anupam** » Sun Jun 22, 2003 2:07 pm

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>>?