sqrt()

[Doe]

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.

[Alvaro]

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.

[Darryl]

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

[tomcant]

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();
      }
   }
}

[Alvaro]

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

How does one get access to these functions? asm?

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.

[hmily]

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;
}

[ventsyv]

I fail to see how is this related ??

[Darryl]

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

[tomcant]

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!

[Alvaro]

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.

[tomcant]

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

[Wizard]

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.

[tomcant]

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!

[tomcant]

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?

[GeekDog]

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