integer - 仅使用整数求平方根

Question

最近，我在某人的编程课上遇到了一个问题。它要求他们仅使用整数计算平方根；他们要用一个整数表示小数点前的部分，用另一个整数表示小数点后的部分。问题是不允许使用浮点数。

但是，在考虑了一段时间之后，我似乎无法想出一种不使用浮点数的方法。我用谷歌搜索了高低，似乎找不到答案。

我开玩笑地建议我的朋友实现一个 FPU 来做到这一点，但他并不那么好笑。

有没有人对如何解决这个问题有任何想法？

Answer 1

假设您的原始号码是x。

1. 查找小数点前的部分很容易 - 只需找到最大数，即小于或等于原始数的平方。

2. 将原始数字乘以 100，将 sqrt 的整数部分乘以 10。将 1 加到它上，直到它小于或等于100x。做n几次并在最后除以10^n得到截断到n小数位的最终答案。

Answer 2

我相信二进制搜索的修改形式将帮助您实现这一目标。让我用c代码详细说明一下。

int square_number = findSquareRootFloor(GivenValue);

int findSquareRootFloor(int number)
{
    int low = 0;
    int high = number;
    int mid = 0;
    while (low <= high)
    {
        int mid = (high + low) / 2;
        int target = mid * mid;
        if (target > number)
            high = mid - 1;
        else if (target < number)
            low = mid +1;
        else
           // exact match
           return mid;
    }
 
    // if we have come here mid stores the floor of the square root
    return high;
}

Answer 3

假设您要计算 123.4567 的平方根。

然后你所要做的就是将小数点向右移动足够远以获得整数radicand - 在这个例子中，四个位置 - 所以，以下是正确的：

sqrt(123.4567) = (1/100) * sqrt(1234567)

也就是说，您只需要知道如何求整数的平方根。为此，请考虑以下代码（在 C 中）：

unsigned int int_sqrt (unsigned int n) {

    unsigned int result = 0;
    unsigned int count  = 1;

    for (; count*count <= n; count += 1) {

        result = result + 1;

    }

    return result;

}

如果你想取消乘法，你也可以这样做：

unsigned int int_sqrt (unsigned int n) {

    unsigned int result = 0;
    unsigned int odd    = 1;
    unsigned int oddsum = 1;

    while (oddsum <= n) {

        result = result + 1;
        odd = odd + 2;
        oddsum = oddsum + odd;

    }

    return result;

}

这些显然不是最快的方法——但它们只使用整数，并且它们不依赖于特定 CPU 的特性，例如字长。

Answer 4

假设您有一个创建两个整数的算法，A并且B该比率A / B为您提供了所需的平方根近似值到适当的小数位数。然后，您想要的两个数字将是：

• 整数部分是(A - (A % B)) / B。
• 小数部分： Let Xbe A % B。然后，比率X / B代表小数部分。然后计算的小数部分通过一遍又一遍地计算(10*X - (10*X % B)) / B和设置来构建连续的数字，X = (10*X % B)直到你得到你想要的小数位数。

要导出平方根的所需分数近似值，您可以计算平方根的连分数。

Answer 5

在伪代码中，它会是这样的：

int whole_ans = sqrt(num); //stores final answer integer part
int dec_ans; //stores final answer decimal part

int num_of_decimals = x   //x is equal to the number of decimal places you want the answer to be
int targetNum = (num - (whole_ans^2)) * 100;  //initialize target to residual * 100
int currAns = whole_ans; //initialize target to residual of num - the answer so far

for(int i=0;i<x;i++)
{
    x = get_next_digit(targetNum,currAns));
    dec_ans = append(dec_ans, x);  //append the new found digit to the right of the current decimal answer
    targetNum = (targetNum - (currAns * 20 + x) * x) * 100; //update target number to be residual + 2 zero digits
    currAns = append(currAns,dec_ans) //append the decimal part of the answer to the current total answer so far

}

func get_next_digit(targetNum,currAns)
{
int attempt=0;
int i=0;
   while(attempt <= targetNum)
   {
       i++;
       attempt = (20 * currAns + i) * i;
   }
i--;
return i;
}

这个答案遵循手动计算平方根的步骤：http: //www.wikihow.com/Calculate-a-Square-Root-by-Hand