Как реализована функция извлечения квадратного корня?

Простая реализация с использованием двоичного поиска с 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 (оба дадут одинаковый результат почти для всех номеров, но на всякий случай).

Изменить: ознакомьтесь с этой статьей в Википедии для различных-специальных целей- методы, специализирующиеся на вычислении квадратного корня.

Изменить 2: применить обновления, предложенные @jorgbrown, чтобы исправить функцию в случае ввода меньше 1. Кроме того, примените оптимизацию, чтобы границы выходили за пределы целевого корня в 10 раз.

На оборудовании Intel это часто реализуется поверх аппаратной инструкции SQRT. Некоторые библиотеки просто используют результат этого сразу, некоторые могут пройти через пару раундов оптимизации Ньютона, чтобы сделать его более точным в крайних случаях.

FDLIBM (Freely Distributable LIBM) имеет неплохую документированную версию sqrt. e_sqrt.c.

У них есть одна версия, которая использует целочисленную арифметику и формулу повторения, изменяющую один бит за раз.

Другой метод использует метод Ньютона. Он начинается с черной магии и таблицы поиска, чтобы получить первые 8 бит, а затем применяет формулу повторения

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

где x - это число, с которого мы начали. Это вавилонский метод метода Герона. Он восходит к герою Александры в первом веке нашей эры.

Существует еще один метод, называемый быстрым обратным квадратным корнем или обратным корнем. который использует «злой взлом уровня битов с плавающей запятой», чтобы найти значение 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 экспоненты числа. Черная магия в основном выполняет побитовый сдвиг показателя степени и использует линейное приближение мантиссы.

Получив хорошее первое приближение, вы можете использовать методы Ньютона для получения лучшего результата и, наконец, немного поработать на уровне битов, чтобы исправить последнюю цифру.

Это реализация алгоритма Ньютона, см. 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$

sqrt (); функция за кадром.

Он всегда проверяет средние точки на графике. Пример: sqrt (16) = 4; sqrt (4) = 2;

Теперь, если вы введете какой-либо ввод внутри 16 или 4, например sqrt (10) ==?

Он находит среднюю точку 2 и 4, т.е. = x, затем снова находит среднюю точку x и 4 (исключает нижнюю границу в этом вводе). Он повторяет этот шаг снова и снова, пока не получит идеальный ответ, то есть sqrt (10) == 3.16227766017. Он находится в ч / б 2 и 4. Все эти встроенные функции созданы с использованием исчисления, дифференцирования и интегрирования.

Реализация на 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

Я тоже делаю функцию sqrt, 100000000 итераций занимает 14 секунд, по-прежнему ничего по сравнению с 1 секундой sqrt

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

До сих пор решения были в основном с плавающей запятой ... и также предполагалось, что инструкция деления доступна и быстро.

Вот простая незамысловатая процедура, в которой не используются 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;
}

Чтобы вычислить квадратный корень (без использования встроенной функции 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();

    }

}

есть нечто, называемое вавилонским методом.

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/

Итак, на случай, если нет спецификаций о том, следует ли использовать встроенную функцию ceil или round, вот рекурсивный подход в Java к нахождению квадратного корня из числа без знака с использованием метода Ньютона-Рафсона.

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

Следуя моему решению в Голанге.

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

Дополнительную информацию см. здесь

Использование: корень (число, корень, глубина)

Пример: 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