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!

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

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