技术派-不用sqrt手工计算平方根
题目：任意长度数串，不使用sqrt函数，手工计算平方根？
要求只准用加/减/乘/除四则运算，不准使用power/sqrt等函数。
算法如下：
1、以小数点为中心往两边每2位分隔为一组；
2、然后以组为单位，从左往右扫描计算；
3、先对第一组数，找个N*N最大但不超过第一组数的数N，作为结果R的第1位；
4、然后用第一组数减去N*N的余数，作为下次计算的数首部，将下一组两位往下移构成一个新的待计算数W；
5、将第3步已得结果R乘以20作为除数首部+尾数X，再乘于X，使得结果T最大但不超过待计算数，X作为结果R的第2位；
6、然后用W减去T作为余数，作为下次计算的数首部，将下一组两位往下移构成一个新的待计算数W；
7、然后再将已有结果R乘以20作为除数首部+尾数X，再乘于X，使得结果T最大但不超过待计算数W，X作为结果R的下一位；
8、重复6~7，直至达到你期望的精度位数为止
C/C++语言实现算法
(粘贴到这里无格式对齐了，请自行格式化)：
//以计算到小数点后32位为例；
//Written by 凌志辉.
//Email:251210269@qq.com
void square_root(char *pszNum)
{
#define IsZero(a) ( fabs(a) < 0.000001f)
#define PRECISIONCNT 32
#ifdef WIN32
#define _itoa_ _itoa_s
#define _strcpy_ strcpy_s
#define _sprintf_ sprintf_s
#else
#define _itoa_ itoa
#define _strcpy_ strcpy
#define _sprintf_ sprintf
#endif
int i = 0, nPrecisionCnt = 0;
double fLeft = 0.0f, fTail = 0.0f;
double fNum = 0.0f, tmp = 0.0f;
bool bEvenInteger = false; //整数部分偶数位
bool bCalcDecimal = false; //开始计算小数部分
char *pDot = strstr(pszNum, ".");
bool bInteger = (NULL == pDot); //整数吗
char szResult[1024] = {0}; //存结果R
char szCalcNum[1024] = {0}; //被除数W
char szDivision[1024] = {0}; //除数
char szZero[4] = {'0', '0', '0','\0'};
char *p = pszNum;
char *r = szResult;
char *d = szDivision;
char *c = szCalcNum;
if (NULL == pszNum)
return;
bEvenInteger = bInteger ? (0 == strlen(pszNum) % 2) : (0 == (pDot - pszNum) % 2);
//1、先计算首部
*c++=*p++;
if (bEvenInteger)
{
*c++=*p++;
}
fLeft = 0.0f;
fNum = atof(szCalcNum);
//第一组数的计算, 首位范围[0~99]
for ( i = 1; i <= 9; i++)
{
if (i * i > fNum)
{
i--;
fLeft = (fNum - i * i);
_itoa_((int)fLeft, szCalcNum, 10);
c = szCalcNum + strlen(szCalcNum);
break;
}
if ( IsZero(i * i - fNum) )
{
fLeft = 0.0f;
c = szCalcNum;
break;
}
}
_itoa_(i, szResult, 10);
_strcpy_(szDivision, szResult);
r = szResult + strlen(szResult);
d = szDivision + strlen(szDivision);
//2、计算第二组数以及以后,由于int型位数最大只占10位,故全采用double型
while (true)
{
if (0 == *p && IsZero(fLeft))
{ //正好完全平方数
*r = '\0';
break;
}
if (0 == *p && !IsZero(fLeft) && !bCalcDecimal)
{ //不是平方数，然后计算更多的小数部分
if (bInteger) /*整数计算，补小数点*/
*r++ = '.';
bCalcDecimal = true;
}
if (bCalcDecimal)
{
nPrecisionCnt++;
p = szZero;
if (nPrecisionCnt > PRECISIONCNT)
{
*r = '\0';
break;
}
}
//非整数运算，若遇到小数点
if (!bInteger && '.' == *p)
{
*r++ = '.';
p++;
}
*c++=*p++; *c++=*p++;
tmp = 20 * atof(szDivision);
fNum = atof(szCalcNum);
fTail = ceil(fNum / tmp);
while ( (tmp + fTail) * fTail > fNum) fTail--;
*r++ = (char)(fTail + 48);
*d++ = (char)(fTail + 48);
fLeft =fNum - (tmp + fTail) * fTail;
memset(szCalcNum, 0, 1024);
if ( !IsZero(fLeft) )
{
_sprintf_(szCalcNum, "%.0f", fLeft);
}
c = szCalcNum + strlen(szCalcNum);
}
printf ("%s\n", szResult);
#undef _itoa_
#undef _strcpy_
#undef _sprintf_
}
调用示例：
……
square_root("59");
square_root("72.25");
……