Как реализована функция квадратного корня?
Как реализована функция квадратного корня?
Ответ 1
Источник здесь.
Оператор задачи: если x> 0, найдите y так, что y ^ 2 = x => y = x/y (это ключевой шаг).
- Угадайте некоторое значение g для y и проверьте его.
- Вычислить x/g.
- Если 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 ... | ...
Ответ 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 (оба будет давать один и тот же результат почти для всех номеров, но только для безопасности).
Редактировать: проверить эту статью в Википедии о различных -special purpose- методах, специализирующихся на вычислении квадратного корня.
Ответ 3
На аппаратном обеспечении Intel он часто реализуется поверх аппаратной инструкции SQRT. Некоторые библиотеки просто используют результат этого сразу, некоторые из них могут пройти через пару раундов оптимизации Ньютона, чтобы сделать его более точным в угловых случаях.
Ответ 4
Существует множество способов вычисления квадратного корня. Wikipedia содержит детали для псевдо-компьютерного алгоритма. Вы ищете реализацию в конкретной библиотеке или для определенной точности?
Ответ 5
FDLIBM (свободно распространяемый LIBM) имеет довольно хорошую документальную версию sqrt. e_sqrt.c.
Есть одна версия, которая использует целочисленную арифметику и формулу повторения, изменяющую один бит за раз.
Другой метод использует метод Ньютона. Он начинается с черной магии и таблицы поиска, чтобы получить первые 8 бит, а затем применяет формулу повторения
y_{i+1} = 1/2 * ( y_i + x / y_i)
где x - номер, с которого мы начали. Это вавилонский метод метода Heron. Это восходит к Герою Александры в первом веке нашей эры.
Существует еще один метод, называемый Быстрый обратный квадратный корень или reciproot. который использует некоторый "злоумышленный взлом бит уровня с плавающей запятой", чтобы найти значение 1/sqrt (x). i = 0x5f3759df - ( i >> 1 ); Он использует двоичное представление float с использованием мантиссы и экспоненты. Если наше число 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 показатель числа. Черная магия в основном выполняет побитовое смещение экспоненты и использует линейную аппроксимацию на мантиссе.
Как только у вас есть хорошее первое приближение, вы можете использовать методы Ньютона, чтобы получить лучший результат, и, наконец, некоторый разрядный уровень для исправления последней цифры.
Ответ 6
Это реализация алгоритма Ньютона, см. 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 $
Ответ 7
SQRT(); Функция За кулисами.
Он всегда проверяет средние точки графика. Пример: sqrt (16) = 4; SQRT (4) = 2;
Теперь, если вы даете какой-либо вход внутри 16 или 4, как sqrt (10) ==?
Он находит среднюю точку 2 и 4 i.e = x, затем снова находит среднюю точку x и 4 (она исключает нижнюю границу этого входа). Он повторяет этот шаг снова и снова, пока не получится идеальный ответ. I.e sqrt (10) == 3.16227766017. Он лежит b/w 2 и 4. Все эти встроенные функции создаются с использованием исчисления, дифференцирования и интеграции.
Ответ 8
Реализация в 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
Ответ 9
Чтобы вычислить квадратный корень (без использования встроенной функции 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();
}
}
Ответ 10
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;
}
Ответ 11
есть нечто, называемое вавилонским методом.
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/
Ответ 12
Таким образом, на случай, если не будет никаких спецификаций относительно того, использовать ли встроенную функцию 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));
}
}
Ответ 13
Я делаю функцию 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);}
Ответ 14
После моего решения в Голанге.
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))
}
Для получения дополнительной информации проверьте здесь