@all
Using Newton's method as described above, the time complexity of
calculating a root of a function f(x) with n-digit precision, provided that
a good initial approximation is known, is O((\log n) F(n)) where F(n) is
the cost of calculating f(x)/f'(x)\, with n-digit precision.
However,
when ever you need to calculate values or solve a equations,apply discrete
mathematics
like newton raphson method it coverges very fast.
On Thu, Jan 5, 2012 at 3:50 PM, WgpShashank shashank7andr...@gmail.comwrote:
you may also like it , explained two algorithm , discussed about
complexities ,
@gene:
I checked the wiki link given..In that it is mentioned that initial root is
chosen as 2.10^n or 6.10^n based on the number of digits being even or odd
in the number.
The concept of choosing 2 or 6 in this formula is based on some geometric
mean concept mentioned. Can you please clarify what
ok.. thanks guys...
one doubt now... if this ques is asked in an interview(its already been
asked in ms interview)... then u cant just write the code... u hv to explain
the whole approach like why u r choosing that way to narrowing dowm the
range...
so pls explain how this sol is derived...
On
@vikram
the one which i posted(link) it was newton raphson method which is used to
derive the square root of a number , there are many other methods if u r
interested visit wikipedia ,
and coming to this method write the code and xplain to him with an
xample...
--
You received this message
double sqrt(double c)
{
if (c 0) return error;
double err = 1e-15;
double t = c;
while (fabs(t*t - c) err)
t = (c/t + t) / 2.0;
return t;
}
On Sun, Sep 25, 2011 at 2:57 PM, teja bala pawanjalsa.t...@gmail.comwrote:
@vikram
the one which i posted(link) it was newton raphson method which
Binary search isn't the right term. Rather you want bisection. But
for each iteration it adds only one bit to the precision of the
answer.
You should also look at Newton's method. It doubles the number of bits
of precision in each iteration.
Algorithm: float sqrt(float x)
root = intial guess
//bakhshali approximation for calculating square root
/* S=number for which squareroot is reqd.
N=nearest perfect square
d=S-N*N; //difference
P=d/(2*N)
A=N+P;
ans=A-(p*P)/(2*A)
*/
#includestdio.h
#includeconio.h
void main(){
float S;
float P,A,d,ans;
int N;
http://www.geeksforgeeks.org/archives/3187
check dis one.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
one of the simplest way is to do binary search... :)
On Sat, Sep 24, 2011 at 8:42 PM, teja bala pawanjalsa.t...@gmail.comwrote:
http://www.geeksforgeeks.org/archives/3187
check dis one.
--
You received this message because you are subscribed to the Google Groups
Algorithm
On 24 September 2011 13:45, shady sinv...@gmail.com wrote:
one of the simplest way is to do binary search... :)
+1
On Sat, Sep 24, 2011 at 8:42 PM, teja bala pawanjalsa.t...@gmail.comwrote:
http://www.geeksforgeeks.org/archives/3187
check dis one.
--
You received this
let x be the number
initialize ans to some value like x or x/2
now repeatedly do the following
ans = (ans + x/ans)/2
each time you perform this operation you will move closer to the sqrt value
and depending upon the precision required stop
On Sat, Sep 24, 2011 at 11:17 PM, siddharth
binary search!!! :)
On Sat, Sep 24, 2011 at 11:38 PM, sunny agrawal sunny816.i...@gmail.comwrote:
let x be the number
initialize ans to some value like x or x/2
now repeatedly do the following
ans = (ans + x/ans)/2
each time you perform this operation you will move closer to the sqrt
13 matches
Mail list logo