to find square root of a number

\\\

http://www.geocities.com/cnowlen/Cathy/Emat4680/Squareroot.htm
http://www.homeschoolmath.net/other_topics/sqr-algorithm-why-works.php

Try this link.
http://www.csd.uwo.ca/courses/CS036a/asn1/example.htm

Hm, if this is not homework,

double dSquareRoot = pow ( <any number>, 0.5);

should do it :o)

well if the author didnt enjoy reading that, i sure did :)

The code I posted does exactly that, and is optimized to do it quickly on a range of cpu's. I didn't write it, I just found and posted it as a possible solution. I chose it from among several because I prefer it's method to the guessing game, which is nearly always slower.

John

It's far simpler than any of this...

The squareroot of any number (n) is equivalent to that number with the power of a half:

sqrt(n) == n^0.5

Hope that helps

:]

But in C, ^ means xor

Hi dmatter,

Care to demonstrate how n raised to the 1/2 power is simpler than anything else mentioned here?

Kent

Anyone else get the feeling we may have aided and abetted in homework here? <g>

John

>>Anyone else get the feeling we may have aided and abetted in homework here?

Check my comment :o)

Hi Kdo,

I'm not sure about the mathematical proof behind it but try it with a program:

for (int i = 0; i < 100; i++)
{
   if (pow (i, 0.5) == sqrt(i))
        printf ("Checks out! \n");
   else
        printf ("Does not check out \n");
}

I think that's right..  I'd never actually use a program like this for practical uses though.

see ya

Hi jkr,

I'm positive that this is homework.  My response was intended to "teach", not "do".  :)


Hi dmatter,

pow() may be a single API in a C program, but the object code isn't nearly so simple.   Using pow() might solve the original poster's requirements, but the mathematics involved is at least as complicated as anything posted here.  By the way, depending on how pow() and sqrt() have been implemented your test may fail.  Floating point math (especially division) is an imprecise science on Intel chips and the least significant bits often stray so pow() and sqrt() might return slightly different answers.


Hi jobrienct,

Glad that you enjoyed reading it.  I did enjoy typing it up and actually getting to think a little bit.  It's pretty sad that the world that Micro$oft has steered us into has removed the need for most of us to think.  A while back I had to write a checksum algorithm for a partner company when they discovered that their algorithm was full of holes.  A multi-million dollar company in the mathematics business and they had to rely on "an amateur" to do the math for them.  Sad.....


Kent

>>Hi jkr,
>>I'm positive that this is homework.  My response was intended to "teach", not "do".  :)

Well, that I know, and you are right, appropriate and correct in your answer :o)

Kdo,

Hmm, I never considered that point.  Perhaps a rounding routine could be used to elimate the LSBs (least sig bits) that may differ, although I'm pitching in the dark here - I'd have to look into it more but it doesn't rank particularly high on my agenda (Deadlines for other work are drawing near)   :?


Dave

All,

I've been programming for >20 years and I've never come across either of these really cute algorithms for sqrt (i.e. adding up odds and folding alternate bits). Is there a source of other cute stuff like this.

P.S. A small challenge, what does ( n ^ (n-1) ) + 1 achieve and can anyone remember ever using this in anger? (I mean '^' as in 'xor', not pow ;) ).

Paul

gives double the value of least significant 1 in the number ?

Close. Its the least significant bit of a binary value.

E.G. ( 10110001000000 ^ (10110001000000 - 1) ) + 1
-> ( 10110001000000 ^ 10110000111111 ) + 1
-> 111111 + 1
-> 1000000

Anyone ever used it?

Good call, Sunny.

n^(n-1) is a "lobit()" function that sets all of the bits to the left of the least significant 1 bit to zero and all of the bits to the right of it to 1, creating a mask in the low end of the word.  Adding 1 simply "rounds up" to the next power of 2.


N          (N ^ (N-1)) + 1

7          (111 ^ 110) + 1
             001            + 1    = 010

14        (1110 ^ 1101) + 1
             0011             + 1 = 0100

etc...

Hi Paul,

You missed a bit:

E.G. ( 10110001000000 ^ (10110001000000 - 1) ) + 1
-> ( 10110001000000 ^ 10110000111111 ) + 1
>> 1111111 + 1
>> 10000000


Kent

Thanks Kent :o)