僅使用整數查找平方根

Question

最近，我在某人的編程課上遇到了一個問題。它要求他們只用整數計算平方根;他們將使用一個整數來表示小數點前的部分，並使用另一個整數來表示小數點後的部分。問題說使用浮點數是不允許的。

但是，在思考了一段時間之後，我似乎無法想出一種不使用浮點的方法。我谷歌搜索高低，我似乎無法找到答案。

我開玩笑地建議我的朋友實施FPU來做這件事，但他並沒有那麼好笑。

有沒有人有關於如何去解決這個問題的任何想法？

Answer 1

假設您的原始號碼是x。

1. 查找小數點前的部分很容易 - 只需找到最大數字，哪個平方小於或等於原始數字。

2. 將原始數字乘以100，並將sqrt的整數部分乘以10.將1加1，直至小於或等於100x。做到這一點n次，除以10^n在最後得到的最終答案截至n小數位。

Answer 2

假設你有一個創建兩個整數A和B使得比率A/B給你你想要的逼近平方根小數適當數量的算法。然後，你想要的兩個數字將是：

• 整數部分是(A - (A % B))/B。
• 小數部分：設X爲A % B。然後，0123,的比率代表小數部分。然後通過計算(10*X - (10*X % B))/B和設置一遍又一遍地構建連續的數字，直到獲得所需的小數位數，然後計算小數部分。

要導出所需的平方根逼近分數，可以計算平方根的連續分數。

Answer 3

在僞代碼將是這樣的：

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

Answer 4

假設你要計算的123.4567平方根。

然後，所有你需要做的是遠遠不夠轉移小數點得到一個整數開方的權利 - 在這個例子中，四個地方 - 所以，以下爲真：

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 5

我相信修改後的二進制二進制搜索形式可以幫助您實現這一點。 讓我詳細說明一下僞代碼。

int square_number = findSquareRootFloor（GivenValue）;

findSquareRootFloor(int number) 
{ 
    int low = 0; 
    int high = number; 
    while (low <=high) 
    { 
     int mid = number /2; // note use integer division 
     target = searchedValue * searchedValue`enter code here`; 
     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 
}