Manual Square Root Function...??

[usnsailorjeoff]

This is a simple Integer based Manual Square root function that i discovered on google ...

unsigned char sqrt(unsigned int N) {
unsigned int x,j;

for (j = 1<<7; j<>0; j >>= 1 )
{
x = x + j;
if (x*x > N )
x = x - j;
}
return(x);
}

COuld someone please explain the logic behind this function? I don't quite understand what the << and >> does??? Also, what is "unsigned" ? THe only data types im familiar with at the time is int, char, string, double, and void???? lol, thanks in advance .

[dcjr84]

Well the unsigned int just means the function will not take negative integers as an argument, or return a negative integer.

Most numerical data types in C++ have an unsigned counterpart; it just means it is not negative.

For example...
int -------- unsigned int
long -------- unsigned long
short -------- unsigned short
etc.
etc.

This makes sense because you cannot take the square root of a negative number.

Well, you can, but then you start dealing with imaginary numbers so we won't even go there

[VladimirF]

For example...
double -------- unsigned double

"unsigned double"? That's something new...

[VladimirF]

...COuld someone please explain the logic behind this function? I don't quite understand what the << and >> does???...

This is simple trial-and-error method: try adding various powers of 2 to the test value and check if it is over the target value - then subtract that last value.
>> and << are binary shift operators (right and left).
>>= - shift with assignment, j >>= 1 is the same as j = j >> 1

[dcjr84]

"unsigned double"? That's something new...

Yeah, I don't know what I was thinking there
I was just trying to get my point across about the
non-negatve values, it must have slipped.

[NMTop40]

the logic is use of binary arithmetic and "trial and error".

The input value is 16-bit. So the maximum square root is 1111111

For each of the 7 bits, try adding it and square the number. If we're too high, remove the bit again.