Вычисление квадратного корня без библиотечных методов

#алгоритм #математика #любой_язык

Как можно вычислить квадратный корень без использования sqrt(n) и n^0.5?
    

Ответы

Ответ 1

Вопрос на самом деле имеет множество решений.

Самый банальный - метод половинного деления.

double l = 0;
double r = 1e100; //большое число
double m;
while (r - l > 1e-8){ //точность
    m = l + (r - l)/2;
    if (m*m > n) l = m;
            else r = m; 
}
//ответ в l


Есть более оригинальные способы, например симуляция вычисления в столбик (вот пример,
код приводить не буду )

Способ больше для C, но думаю можно использовать и в Java. Объяснение

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

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       
    i  = 0x5f3759df - ( i >> 1 );                
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1 итерация
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2 итерация, можно удалить
    return 1/y;
}


Можно использовать логарифмы

return Math.exp( Math.log(n) / 2);


Можно использовать численные методы, например  метод Ньютона

double x = 1;
for (;;) {
   double nx = (x + n / x) / 2;
   if (abs (x - nx) < 1e-10)  break; //точность
   x = nx;
}


Существует и много других способов, всё зависит от конкретных требований.


Ответ 2

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

 :

public static double sqrt(int number) {
    double t;     
    double squareRoot = number / 2;     
    do {
        t = squareRoot;
        squareRoot = (t + (number / t)) / 2;
    } while ((t - squareRoot) != 0);     
    return squareRoot;
}


ideone


Ответ 3

Все зависит от контекста задачи. Про различные методы уже рассказали. Есть еще вариант
для случая если примерно известен диапазон входных параметров. Можно просто сделать
таблицу с уже готовыми ответами. 

Когда делали курсовую по микросхемотехнике для 8 битных систем, то самым простым
и быстрым решением была ПЗУ на 256 ячеек с уже зашитыми туда ответами. Но преподователь
с таким подходом не согласился. Предложил все же "посчитать".