function - 平方根函数是如何实现的？

Question

平方根函数是如何实现的？

Answer 1

使用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在处理十进制数时使用，它可以节省一些特殊情况的处理，并从类似的小循环中获得非常准确的结果，1000甚至500（对于几乎所有数字，两者都会给出相同的结果但为了安全起见）。

编辑：查看这篇Wikipedia 文章，了解专门用于计算平方根的各种 - 特殊用途 - 方法。

编辑 2：应用 @jorgbrown 建议的更新以在输入小于 1 的情况下修复该函数。此外，应用优化以使目标根的边界缩小 10 倍

Answer 2

在英特尔硬件上，它通常在硬件 SQRT 指令之上实现。有些库只是直接使用该结果，有些库可能会对其进行几轮牛顿优化，以使其在极端情况下更加准确。

Answer 3

FDLIBM (Freely Distributable LIBM) 有一个非常好的 sqrt 文档版本。e_sqrt.c。

有一个版本，它使用整数算术和一次修改一位的递归公式。

另一种方法使用牛顿法。它从一些黑魔法和一个查找表开始以获取前 8 位，然后应用递归公式

 y_{i+1} = 1/2 * ( y_i + x / y_i)

其中 x 是我们开始的数字。这是赫伦方法的巴比伦方法。它可以追溯到公元第一个世纪的亚历山德拉英雄。

还有另一种方法称为快速反平方根或 reciproot。它使用一些“邪恶的浮点位级黑客”来找到 1/sqrt(x) 的值。i = 0x5f3759df - ( i >> 1 );它使用尾数和指数利用浮点数的二进制表示。如果我们的数字 x 是 (1+m) * 2^e，其中 m 是尾数，e 是指数，结果 y = 1/sqrt(x) = (1+n) * 2^f。记录日志

lg(y) = - 1/2 lg(x)
f + lg(1+n) = -1/2 e - 1/2 lg(1+m)

所以我们看到结果的指数部分是数字的指数的-1/2。黑魔法基本上对指数进行按位移位，并对尾数使用线性近似。

一旦你有了一个好的第一个近似值，你就可以使用牛顿的方法来获得更好的结果，最后一些位级别的工作来修复最后一个数字。

Answer 4

这是牛顿算法的一个实现，参见https://tour.golang.org/flowcontrol/8。

func Sqrt(x float64) float64 {
  // let initial guess to be 1
  z := 1.0
  for i := 1; i <= 10; i++ {
    z -= (z*z - x) / (2*z) // MAGIC LINE!!
    fmt.Println(z)
  }
  return z
}

以下是魔术线的数学解释。假设您要找到多项式 $f(x) = x^2 - a$ 的根。通过牛顿法，您可以从初始猜测 $x_0 = 1$ 开始。下一个猜测是 $x_1 = x_0 - f(x_0)/f'(x_0)$，其中 $f'(x) = 2x$。因此，您的新猜测是

$x_1 = x_0 - (x_0^2 - a)/2x_0$

Answer 5

Formula: root(number, <root>, <depth>) == number^(root^(-depth))

Usage: root(number,<root>,<depth>)

Example: root(16,2) == sqrt(16) == 4
Example: root(16,2,2) == sqrt(sqrt(16)) == 2
Example: root(64,3) == 4

Implementation in C#:

static double root(double number, double root = 2f, double depth = 1f)
{
    return Math.Pow(number, Math.Pow(root, -depth));
}

Answer 6

sqrt(); 功能幕后。

它总是检查图表中的中点。示例：sqrt(16)=4; sqrt(4)=2;

现在，如果您在 16 或 4 内输入任何输入，例如 sqrt(10)==？

它找到 2 和 4 的中点，即 = x ，然后再次找到 x 和 4 的中点（它不包括此输入中的下限）。它一次又一次地重复这个步骤，直到它得到完美的答案，即 sqrt(10)==3.16227766017。它位于 b/w 2 和 4。所有这些内置函数都是使用微积分、微分和积分创建的。

Answer 7

到目前为止的解决方案主要是浮点......并且还假设除法指令可用且快速。

这是一个不使用 FP 或除法的简单直接例程。每一行计算结果中的另一位，除了第一个 if 语句，它在输入较小时加速例程。

constexpr unsigned int root(unsigned int x) {
  unsigned int i = 0;
  if (x >= 65536) {
    if ((i + 32768) * (i + 32768) <= x) i += 32768;
    if ((i + 16384) * (i + 16384) <= x) i += 16384;
    if ((i + 8192) * (i + 8192) <= x) i += 8192;
    if ((i + 4096) * (i + 4096) <= x) i += 4096;
    if ((i + 2048) * (i + 2048) <= x) i += 2048;
    if ((i + 1024) * (i + 1024) <= x) i += 1024;
    if ((i + 512) * (i + 512) <= x) i += 512;
    if ((i + 256) * (i + 256) <= x) i += 256;
  }
  if ((i + 128) * (i + 128) <= x) i += 128;
  if ((i + 64) * (i + 64) <= x) i += 64;
  if ((i + 32) * (i + 32) <= x) i += 32;
  if ((i + 16) * (i + 16) <= x) i += 16;
  if ((i + 8) * (i + 8) <= x) i += 8;
  if ((i + 4) * (i + 4) <= x) i += 4;
  if ((i + 2) * (i + 2) <= x) i += 2;
  if ((i + 1) * (i + 1) <= x) i += 1;
  return i;
}

Answer 8

我也在做一个 sqrt 函数，100000000 次迭代需要 14 秒，与 sqrt 的 1 秒相比仍然没有

double mysqrt(double n)
{
    double x = n;
    int it = 4;
    if (n >= 90)
    {
        it = 6;
    }
    if (n >= 5000)
    {
        it = 8;
    }
    if (n >= 20000)
    {
        it = 10;
    }
    if (n >= 90000)
    {
        it = 11;
    }
    if (n >= 200000)
    {
        it = 12;
    }
    if (n >= 900000)
    {
        it = 13;
    }
    if (n >= 3000000)
    {
        it = 14;
    }
    if (n >= 10000000)
    {
        it = 15;
    }
    if (n >= 30000000)
    {
        it = 16;
    }
    if (n >= 100000000)
    {
        it = 17;
    }

    if (n >= 300000000)
    {
        it = 18;
    }
    if (n >= 1000000000)
    {
        it = 19;
    }

    for (int i = 0; i < it; i++)
    {
        x = 0.5*(x+n/x);
    }
    return x;
}

但最快的实现是：

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

float mysqrt(float n) {return 1/Q_rsqrt(n);}

Answer 9

Python中的实现： 根值的下限是这个函数的输出。示例：8 的平方根是 2.82842...，此函数将给出输出 '2'

def mySqrt(x):
        # return int(math.sqrt(x))
        if x==0 or x==1:
            return x
        else:
            start = 0
            end = x  
            while (start <= end):
                mid = int((start + end) / 2)
                if (mid*mid == x):
                    return mid
                elif (mid*mid < x):
                    start = mid + 1
                    ans = mid
                else:
                    end = mid - 1
            return ans

Answer 10

因此，以防万一没有关于是否使用内置 ceil 或 round 函数的规范，这是 Java 中使用 Newton-Raphson 方法找到无符号数的平方根的递归方法。

public class FindSquareRoot {

    private static double newtonRaphson(double N, double X, double oldX) {

        if(N <= 0) return 0;

        if (Math.round(X) == Math.ceil(oldX))
            return X;

        return newtonRaphson(N, X - ((X * X) - N)/(2 * X), X);
    }

    //Driver method
    public static void main (String[] args) {
        System.out.println("Square root of 48.8: " + newtonRaphson(48.8, 10, 0));
    }
}

Answer 11

要计算平方根（不使用内置 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;
    }

}

主应用程序.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();

    }

}

Answer 12

有一种叫做巴比伦方法的东西。

static float squareRoot(float n)
{

    /*We are using n itself as 
    initial approximation This 
    can definitely be improved */
    float x = n;
    float y = 1;

    // e decides the accuracy level
    double e = 0.000001;
    while(x - y > e)
    {
        x = (x + y)/2;
        y = n/x;
    }
    return x;
}

更多信息链接：https ://www.geeksforgeeks.org/square-root-of-a-perfect-square/

Answer 13

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;
}

Answer 14

遵循我在 Golang 中的解决方案。

package main

import (
   "fmt"
)

func Sqrt(x float64) float64 {
   z := 1.0 // initial guess to be 1
   i := 0
   for int(z*z) != int(x) { // until find the first approximation
      // Newton root algorithm
      z -= (z*z - x) / (2 * z)
      i++
   }
   return z
}

func main() {
   fmt.Println(Sqrt(8900009870))
}

遵循经典/常见解决方案。

package main

import (
"fmt"
"math"
)

func Sqrt(num float64) float64 {
   const DIFF = 0.0001 // To fix the precision
   z := 1.0

   for {
      z1 := z - (((z * z) - num) / (2 * z))
      // Return a result when the diff between the last execution 
      // and the current one is lass than the precision constant
      if (math.Abs(z1 - z) < DIFF) {
         break
      }
      z = z1
   }

   return z
}


func main() {
   fmt.Println(Sqrt(94339))
}

欲了解更多信息，请点击此处

Answer 15

用法：根（数字，根，深度）

示例：root(16,2) == sqrt(16) == 4
示例：root(16,2,2) == sqrt(sqrt(16)) == 2
示例：root(64,3) == 4

C# 中的实现：

double root(double number, double root, double depth = 1f)
{
    return number ^ (root ^ (-depth));
}

用法：Sqrt（数字，深度）

示例：Sqrt(16) == 4
示例：Sqrt(8,2) == sqrt(sqrt(8))

double Sqrt(double number, double depth = 1) return root(number,2,depth);

作者：Imk0tter