Saturday, September 19, 2015

Integral Perfect Square

Here is a C implementation of calculating integral square root.  Algorithm based on "long division" logic.  Test cases done with OpenMP and should be compiled as

g++ --std=c++0x -fopenmp -Wall IntegralPerfectSquare.cpp -o IntegralPerfectSquare


Reference:
http://www.math-only-math.com/square-root-of-a-perfect-square-by-using-the-long-division-method.html

Gihub:
https://github.com/kitsook/CPerfectSquare


long long perfectSquare(long long num)
{
// obvious cases
int lastDigit = num % 10;
if (num <= 0 || lastDigit == 2 || lastDigit == 3 || lastDigit == 7 || lastDigit == 8)
{
return 0;
}
long long section = 1;
long long pow100 = 1;
while (num / pow100 >= 100)
{
section++;
pow100 *= 100;
}
long long period = num / pow100; // first period
long long remainder = num % pow100;
long long quotient = 0;
while (section > 0)
{
section--;
pow100 /= 100;
long long divisor;
int newQuotientDigit;
long long multi;
for (newQuotientDigit = 9, divisor = quotient * 20 + newQuotientDigit; newQuotientDigit >= 0; newQuotientDigit--, divisor--)
{
multi = divisor * newQuotientDigit;
if (period >= multi)
{
break;
}
}
if (newQuotientDigit < 0)
{
return 0;
}
long long period_remain = period - multi;
quotient = quotient * 10 + newQuotientDigit;
if (section > 0)
{
period = period_remain * 100 + remainder / pow100;
remainder = remainder % pow100;
}
else if (section == 0 && period_remain == 0 && remainder == 0)
{
return quotient;
}
}
return 0;
}

No comments: