81

平方根関数はどのように実装されていますか?

4

15 に答える 15

22

C++ による二分探索を使用した簡単な実装

double root(double n){
  // Max and min are used to take into account numbers less than 1
  double lo = min(1, n), hi = max(1, n), mid;

  // Update the bounds to be off the target by a factor of 10
  while(100 * lo * lo < n) lo *= 10;
  while(100 * hi * hi > n) hi *= 0.1;

  for(int i = 0 ; i < 100 ; i++){
      mid = (lo+hi)/2;
      if(mid*mid == n) return mid;
      if(mid*mid > n) hi = mid;
      else lo = mid;
  }
  return mid;
}

whileループはバイナリ検索で最も一般的ですが、個人的にforは 10 進数を扱うときに使用することを好みます。これにより、いくつかの特殊なケースの処理が節約され、そのような小さなループからかなり正確な結果が得られ1000ます500(両方ともほとんどすべての数値に対して同じ結果が得られます)。ただし、念のため）。

編集：平方根の計算に特化したさまざまな-特別な目的の方法については、このウィキペディアの記事をご覧ください。

編集 2: @jorgbrown によって提案された更新を適用して、入力が 1 未満の場合に関数を修正します。また、最適化を適用して、ターゲット ルートから境界を 10 倍にします。

于 2016-09-26T21:49:27.577 に答える
11

Intelハードウェアでは、多くの場合、ハードウェアSQRT命令の上に実装されます。一部のライブラリは、その結果をそのまま使用します。一部のライブラリは、コーナーケースでより正確にするために、ニュートン最適化を数回実行する場合があります。

于 2010-08-27T09:42:09.643 に答える
0

平方根を計算するには (組み込みの math.sqrt 関数を使用せずに):

SquareRootFunction.java

public class SquareRootFunction {

    public double squareRoot(double value,int decimalPoints)
    {
        int firstPart=0;


        /*calculating the integer part*/
        while(square(firstPart)<value)
        {
            firstPart++;            
        }

        if(square(firstPart)==value)
            return firstPart;
        firstPart--;

        /*calculating the decimal values*/
        double precisionVal=0.1;
        double[] decimalValues=new double[decimalPoints];
        double secondPart=0;

        for(int i=0;i<decimalPoints;i++)
        {
            while(square(firstPart+secondPart+decimalValues[i])<value)
            {
                decimalValues[i]+=precisionVal;
            }

            if(square(firstPart+secondPart+decimalValues[i])==value)
            {
                return (firstPart+secondPart+decimalValues[i]);
            }

            decimalValues[i]-=precisionVal;
            secondPart+=decimalValues[i];
            precisionVal*=0.1;
        }

        return(firstPart+secondPart);

    }


    public double square(double val)
    {
        return val*val;
    }

}

MainApp.java

import java.util.Scanner;

public class MainApp {

public static void main(String[] args) {

    double number;
    double result;
    int decimalPoints;
    Scanner in = new Scanner(System.in);

    SquareRootFunction sqrt=new SquareRootFunction();   
    System.out.println("Enter the number\n");               
    number=in.nextFloat();  

    System.out.println("Enter the decimal points\n");           
    decimalPoints=in.nextInt();

    result=sqrt.squareRoot(number,decimalPoints);

    System.out.println("The square root value is "+ result);

    in.close();

    }

}
于 2015-08-06T16:00:17.383 に答える
-1 
long long int floorSqrt(long long int x) 
{
    long long r = 0;
    while((long)(1<<r)*(long)(1<<r) <= x){
        r++;
    }
    r--;
    long long b = r -1;
    long long ans = 1 << r;
    while(b >= 0){
        if(((long)(ans|1<<b)*(long)(ans|1<<b))<=x){
            ans |= (1<<b);
        }
        b--;
    }
    return ans;
}
于 2017-12-25T14:45:39.950 に答える