## sqrt()

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### sqrt()

I tried a lot of efforts to discover how sqrt is done, and found a slower algorithm. It takes more clock cycles... How the fuc* is the standard sqrt made? I wanna know because I want to make a unsigned long sqrt, not a double, and type-casting from double to int is very slow...

Can someone help me here? Please..

By the way; the algorythm I tried to make was based on splitting the number into two parts, then see if the middle is lower. If it is, then check the higher sub-part. Else, check the lower sub-part. If the middle is higher, then check the higher part, and so on... Damn, I can't post any code because I was so angry at that time that sqrt() is faster, and I deleted my code and I was so angry.
Doe

sqrt() is implemented in hardware, probably using Newton-raphson. It's a mechanism that refines a previous guess for the square root.

guess = (guess^2+n)/(2*guess);

Apply that several times and you get really, really close to your number. The initial guess is actually easier to make with floating point numbers, because dividing the exponent by two gets you pretty close.

The problem is that hardware is very hard to beat. You might be able to do something slightly faster for integers with the help of some precomputed tables.

Most of the time the fastest option is to not compute the square root at all, since often it can be avoided.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

Alvaro wrote:sqrt() is implemented in hardware, probably using Newton-raphson. It's a mechanism that refines a previous guess for the square root.
...

Really!, that's interesting, are there other higher functions implented in hardware too? How does one get access to these functions? asm? I am working on a large interger class and this is one of the functions I need to implement. Is Newton-raphson what you'd recommend? My class uses an vector of integers to store base 1000 digits.

Darryl

Darryl

Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

I'v always been able to calculate square roots in my head, even of fairly large numbers (sounds crazy, I know). Once, someone gave me a 6 digit number and I got it down to 0.05 out. It's actually quite easy. I wrote a program to do it using the method I use, and just to make things slightily complicated, I obfuscated it. Oh and its in C#.

Code: Select all
`using System;namespace sqr{   class MainClass   {      private static double O_(long o)      {         if(o==1)return(1);         double _o=0,_O=0;;                       while(_O*_O<=o)        _o=++_O-((                 _O)---_O++            );_o+=((o-          _o*_o)/(++              _o*_o---_o                      *_o));         return(_o);      }            public static void Main()      {         long _o;         while((_o=Convert.ToInt32(Console.ReadLine()))!=0)            Console.WriteLine(O_(_o).ToString());         Console.Read();      }   }}`
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Darrylsh wrote:
Alvaro wrote:sqrt() is implemented in hardware, probably using Newton-raphson. It's a mechanism that refines a previous guess for the square root.
...

Really!, that's interesting, are there other higher functions implented in hardware too?

sin(), cos(), log()...

Yup. They are called FSQRT, FSIN, FCOS, FLOG... There is also an FSINCOS, which computes sine and cosine at the same time, and a weird instruction FYL2XP1, which has two operands and computes Y*log(X+1)/log(2).

I am working on a large interger class and this is one of the functions I need to implement. Is Newton-raphson what you'd recommend? My class uses an vector of integers to store base 1000 digits.

For square root, I would start with something that has the correct number of digits (half the original number of digits), and with the correct first digit. For that you only need a lookup in a small table. Then use Newton-Raphson until it stabilizes, then you might have to adjust by one. That's what I would try, but I've never implemented a serious long integer class.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### Re: sqrt()

Hi,I think this will be helpful to you.

Code: Select all
`long sqrt(long num){  long i;  for(i=1;num>0;++i){     num=num-(2*i-1);  }  return i;}`

hmily

Posts: 4
Joined: Wed Jan 12, 2005 3:50 am

I fail to see how is this related ??

ventsyv

Posts: 2810
Joined: Mon Sep 22, 2003 5:25 pm
Location: MD USA

maybe hmily thought that was a solution for getting sqrt.

I tried it out and it gives 6 for sqrt of 25, so I guess it needs more work

D

Darryl

Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Darryl wrote:I tried it out and it gives 6 for sqrt of 25, so I guess it needs more work

Ha! I tried it on exactly the same number... weird!
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

I guess the algorithm can be slightly modified so it works out. The problem I have with it is that it's really slow. Binary search would be much faster.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

Alvaro wrote:I guess the algorithm can be slightly modified so it works out. The problem I have with it is that it's really slow. Binary search would be much faster.

Huh? How can you use binary search to find a square root? I'm lost...
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

The square root of any number is somewhere between 0 and itself. So divide the number by two, and try that. If it's too high, go half lower, if too low, go half higher. Just like a binary search. You keep going, until you've got the precision you're looking for.
For example, sqrt(2)
low = 0, high = 2, mid = low+high /2 = 1
1*1 = 1, 1 < 2, so low = mid = 1, mid = low+high /2 = 1.5
1.5*1.5 = 2.25 too high, so high = 1.5, mid = low+high /2 = 1.25
... and so on, until you hit 1.414 or more precision if you so choose.

Wizard

Posts: 3226
Joined: Mon Sep 22, 2003 4:52 pm
Location: ON, CA

Wizard wrote:The square root of any number is somewhere between 0 and itself. So divide the number by two, and try that. If it's too high, go half lower, if too low, go half higher. Just like a binary search. You keep going, until you've got the precision you're looking for.
For example, sqrt(2)
low = 0, high = 2, mid = low+high /2 = 1
1*1 = 1, 1 < 2, so low = mid = 1, mid = low+high /2 = 1.5
1.5*1.5 = 2.25 too high, so high = 1.5, mid = low+high /2 = 1.25
... and so on, until you hit 1.414 or more precision if you so choose.

Ah right, I see. Thanks!
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

I just had a quick go at implementing this. Here it is:
[syntax="cpp"]double sqr(double num) {
double hi=num,lo=0.0,m;
while(lo<hi) {
m=(double)(lo+hi)/2.0;
if(m*m==num) return m;
else if(m*m<num) lo=m;
else hi=m;
}
return 0.0;
}[/syntax]

It will calculate the root of any square number, but when you give it a number thats not square, the function never returns anything. The reason is, double does not support the precision needed for most square roots and therefore the function will never return `m' because it's square is not equal to `num'.

How can I get round this?
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Set a tolerance limit. If the answer is close enough to what you need, accept it.

GeekDog

Posts: 1160
Joined: Sun Sep 28, 2003 1:42 pm
Location: UK

Next