2

最近、誰かのプログラミングクラスで問題に遭遇しました。整数のみを使用して平方根を計算するように求めました。1 つの整数を使用して小数点の前の部分を表し、別の整数を使用して小数点の後の部分を表す必要がありました。問題は、浮動小数点数の使用が許可されていないことを示していました。

しかし、しばらく考えてみると、浮動小数点を使わずにそれを行う方法が思いつかないようです。高低をグーグルで検索しましたが、答えが見つからないようです。

私は冗談めかして、これを行うために FPU を実装することを友人に提案しましたが、彼はあまり面白くありませんでした。

これを解決する方法について誰かアイデアがありますか?

4

5 に答える 5

2

元の番号が だとしましょうx。

  1. 小数点の前の部分を見つけるのは簡単です.2乗が元の数以下である最大数を見つけるだけです.

  2. 元の数値に 100 を掛け、sqrt の整数部分に 10 を掛けます。以下になるまで 1 を足し100xます。倍にして最後に でn割ると、最終的な答えが小数点以下に切り捨てられます。10^nn

于 2013-05-13T23:25:26.937 に答える
0

擬似コードでは、次のようになります。

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

于 2013-05-14T00:55:32.440 に答える
0

二分探索の修正された形式が、それを達成するのに役立つと思います。それを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;
}
于 2014-08-13T04:06:48.473 に答える
0

2 つの整数を作成するアルゴリズムがAありB、その比率A / Bによって適切な小数点以下の桁数の平方根の近似値が得られるとします。次に、必要な2つの数値は次のようになります。

  • 整数部は(A - (A % B)) / B.
  • 小数部分:XとするA % B。次に、X / B比率は小数部分を表します。次に、計算された小数部分は、必要な小数点以下の桁数が得られるまで、計算(10*X - (10*X % B)) / Bと設定を繰り返して連続する桁を構築することによって行われます。X = (10*X % B)

平方根に必要な分数近似を導出するために、平方根の連分数を計算できます。

于 2013-05-13T23:58:32.993 に答える
0

123.4567 の平方根を計算するとします。

次に、小数点を十分に右にシフトして、整数の基数 (この例では 4 桁) を取得するだけです。したがって、次のことが当てはまります。

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 の特性に依存しません。

于 2013-10-25T12:23:31.863 に答える