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

Question

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

Answer 1

Источник здесь .

Постановка задачи: При заданном x> 0 найдите y таким, что y ^ 2 = x => y = x / y (это ключевой шаг).

1. Угадай некоторое значение g для y и проверь его.
2. Вычислить х / г.
3. Если x / g достаточно близко к g, вернуть g. В противном случае попробуйте лучше угадать.

double test(double x, double g) {
   if closeEnough(x/g, g)
      return g;
   else
      return test(x, betterGuess(x, g));
}

boolean closeEnough(double a, double b) {
   return (Math.abs(a - b) < .001);
}

double betterGuess(double x, double g) {
   return ((g + x/g) / 2);
}

---

sqrt(2)         | Guess g  x / g               | New guess, (g + x / g) / 2
----------------|------------------------------|-------------------------------
test(2, 1)      | 1        2 / 1      = 2      | (2      +      1) / 2 = 1.5
test(2, 1.5)    | 1.5      2 / 1.5    = 1.3333 | (1.3333 +    1.5) / 2 = 1.4167
test(2, 1.4167) | 1.4167   2 / 1.4167 = 1.4118 | (1.4167 + 1.4118) / 2 = 1.4142
test(2, 1.4142) | 1.4142   ...                 | ...

Answer 2

Простая реализация с использованием Бинарный поиск с C ++

double root(double n){
  double lo = 0, hi = n, mid;
  for(int i = 0 ; i < 1000 ; 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 (оба будут давать один и тот же результат почти для всех чисел, но только для безопасности).

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

SQRT (); Функция За кадром.

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

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

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

Answer 8

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

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 9

Я тоже создаю функцию 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);}

Answer 10

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

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