Author |
Topic: Efficient Algo for calculating SQUARE ROOT (Read 11223 times) |
|
solid
Newbie
Posts: 5
|
 |
Efficient Algo for calculating SQUARE ROOT
« on: Sep 4th, 2011, 11:21pm » |
 Quote  Modify
|
Does anyone know efficient and correct algorithm for calculating the Square Root of a number. I searched lot of interview, couldn't find any convincing method.
Pseudo code will be appreciated.
|
|
 IP Logged |
|
|
|
solid
Newbie
Posts: 5
|
|
Re: Efficient Algo for calculating SQUARE ROOT
« Reply #1 on: Sep 4th, 2011, 11:23pm » |
Quote Modify
|
is it the correct pseudo/formula to calculate square root:
repeat:
x = (x + a/x)/2;
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Efficient Algo for calculating SQUARE ROOT
« Reply #2 on: Sep 5th, 2011, 1:09am » |
Quote Modify
|
That is probably the simplest and is still reasonably fast.
If floating point division is not available, or too slow, you can do a binary search.
There is also a method using only integer additions and comparisons to compute the mantissa.
If you have a fast log and exp, you can do exp(log(x)/2).
|
|
IP Logged |
|
|
|
solid
Newbie
Posts: 5
|
|
Re: Efficient Algo for calculating SQUARE ROOT
« Reply #3 on: Sep 5th, 2011, 9:27am » |
Quote Modify
|
Could you please elaborate a bit? Or pseudo code?
|
|
IP Logged |
|
|
|
fizyka
Junior Member
Physics&Informa tics <3
Gender:
Posts: 54
|
|
Re: Efficient Algo for calculating SQUARE ROOT
« Reply #4 on: Dec 30th, 2011, 2:08pm » |
Quote Modify
|
So standard math.h from C language isn't enough fast?
For what You need faster code? I dont follow.
|
|
IP Logged |
fizyka , karta wzorów fizyka , książki z fizyki
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Efficient Algo for calculating SQUARE ROOT
« Reply #5 on: Dec 31st, 2011, 2:40am » |
Quote Modify
|
The idea of a puzzle is to figure out how to solve it, not to look up the answer in the back of the book.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
webtasarim
Newbie
  
Gender:
Posts: 47
|
|
Re: Efficient Algo for calculating SQUARE ROOT
« Reply #6 on: Oct 20th, 2013, 5:33pm » |
Quote Modify
|
Set the factor F to 16
If N < 1 Then N = 1 / N
Let X = N
Let LastX = X
Calculate X = X / F
If X*X > N then resume to step 10
Reduce factor F such that it approaches 1
Let X = LastX / F
Go to step 6
If |X*X - N| > Tolerance And |F - 1| > Tolerance then resume at step 4
Return X as the square root of N, or return 1/X if the original N was less than 1
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print