Поиск квадратного корня без использования функции sqrt?

Ответ 1

Ваш алгоритм довольно плох. Существует лучший алгоритм, которому требуется не более 6 итераций, чтобы сходиться к максимальной точности для двойных чисел:

#include <math.h>

double sqrt(double x) {
    if (x <= 0)
        return 0;       // if negative number throw an exception?
    int exp = 0;
    x = frexp(x, &exp); // extract binary exponent from x
    if (exp & 1) {      // we want exponent to be even
        exp--;
        x *= 2;
    }
    double y = (1+x)/2; // first approximation
    double z = 0;
    while (y != z) {    // yes, we CAN compare doubles here!
        z = y;
        y = (y + x/y) / 2;
    }
    return ldexp(y, exp/2); // multiply answer by 2^(exp/2)
}

Алгоритм начинается с 1 в качестве первого приближения для значения квадратного корня. Затем на каждом шаге он улучшает следующее приближение, беря среднее значение между текущим значением y и x/y. Если y= sqrt(x), это будет одинаково. Если y > sqrt(x), то x/y < sqrt(x) примерно на ту же сумму. Другими словами, он будет сходиться очень быстро.

UPDATE. Чтобы ускорить конвергенцию на очень больших или очень малых числах, изменилась функция sqrt(), чтобы извлечь двоичный показатель и вычислить квадратный корень из числа в диапазоне [1, 4). Теперь требуется frexp() из <math.h>, чтобы получить двоичный показатель, но этот показатель можно получить, извлекая биты из формата номера IEEE-754 без использования frexp().

Ответ 2

если вам нужно найти квадратный корень без использования sqrt(), используйте root=pow(x,0.5).

Где x - значение, квадратный корень которого вам нужно найти.

Ответ 3

Удалите ваш nCount вообще (так как есть некоторые корни, для которых для этого алгоритма потребуется много итераций).

double SqrtNumber(double num)
{
    double lower_bound=0; 
    double upper_bound=num;
    double temp=0;

    while(fabs(num - (temp * temp)) > SOME_SMALL_VALUE)
    {
           temp = (lower_bound+upper_bound)/2;
           if (temp*temp >= num)
           {
                   upper_bound = temp;
           }
           else
           {
                   lower_bound = temp;
           }
    }
    return temp;
 }

Ответ 4

Как я понял, этот вопрос старый и у меня много ответов, но у меня есть ответ, который прост и работает отлично.

#define EPSILON 0.0000001 // least minimum value for comparison
double SquareRoot(double _val) {
    double low = 0; 
    double high = _val;
    double mid = 0; 

    while (high - low > EPSILON) {
            mid = low + (high - low) / 2; // finding mid value
            if (mid*mid > _val) {
                high = mid;
            } else {
                low = mid;
            }    
    }   
    return mid;
}

Я надеюсь, что это будет полезно для будущих пользователей.

Ответ 5

Почему бы не попробовать использовать вавилонский метод для поиска квадратного корня.

Вот мой код для него:

double sqrt(double number)
{
    double error = 0.00001; //define the precision of your result
    double s = number;

    while ((s - number / s) > error) //loop until precision satisfied 
    {
        s = (s + number / s) / 2;
    }
    return s;
}

Удачи!

Ответ 6

//long division method.
#include<iostream>
using namespace std;
int main() {
int n, i = 1, divisor, dividend, j = 1, digit;
cin >> n;
while (i * i < n) {
    i = i + 1;
}
i = i - 1;
cout << i << '.';

divisor  = 2 * i;
dividend = n - (i * i );
while( j <= 5) {
    dividend = dividend * 100;
    digit = 0;
    while ((divisor * 10 + digit) * digit < dividend) {
        digit = digit + 1;
    }
    digit = digit  - 1;
    cout << digit;
    dividend = dividend - ((divisor * 10 + digit) * digit);
    divisor = divisor * 10 + 2*digit;
    j = j + 1;
}
cout << endl;
return 0;
}

Ответ 7

Вот очень простой, но небезопасный подход, чтобы найти квадратный корень числа. Небезопасно, потому что он работает только по натуральным числам, где вы знаете, что база, соответственно, является натуральными числами. Я должен был использовать его для задачи, где мне не разрешалось использовать # include <cmath> -библиотеку, и мне не разрешалось использовать указатели.

potency = base ^ exponent

// FUNCTION: square-root
int sqrt(int x)
{
    int quotient = 0;
    int i = 0;

    bool resultfound = false;
    while (resultfound == false) {
        if (i*i == x) {
          quotient = i;
          resultfound = true;
        }
        i++;
    }
    return quotient;
}

Ответ 8

Вот очень удивительный код для поиска sqrt и даже быстрее, чем оригинальная функция sqrt.

float InvSqrt (float x) 
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f375a86 - (i>>1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    x = x*(1.5f - xhalf*x*x);
    x = x*(1.5f - xhalf*x*x);
    x=1/x;
    return x;
}

Ответ 9

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

Это рабочая функция корня, способная решать любой n-й корень

(по умолчанию это квадратный корень для этого вопроса)

#include <cmath> 
// for "pow" function

double sqrt(double A, double root = 2) {
    const double e = 2.71828182846;
    return pow(e,(pow(10.0,9.0)/root)*(1.0-(pow(A,-pow(10.0,-9.0)))));
}

Объяснение:

нажмите здесь для просмотра графика

Это работает через ряд Тейлора, логарифмические свойства и бит алгебры.

Возьмите, например:

log A = N
   x

* Примечание: для квадратного корня, N = 2; для любого другого корня вам нужно только изменить одну переменную, N.

1) Измените базу, преобразуйте базовую функцию "x" в естественный журнал,

log A   =>   ln(A)/ln(x) = N
   x

2) Перегруппируйте, чтобы изолировать ln (x), и в конечном итоге просто "x",

ln(A)/N = ln(x)

3) Установите обе стороны как экспоненты 'e', ​​

e^(ln(A)/N) = e^(ln(x))  >~{ e^ln(x) == x }~>  e^(ln(A)/N) = x

4) Ряд Тейлора представляет "ln" как бесконечный ряд,

ln(x) = (k=1)Sigma: (1/k)(-1^(k+1))(k-1)^n

           <~~~ expanded ~~~>

[(x-1)] - [(1/2)(x-1)^2] + [(1/3)(x-1)^3] - [(1/4)(x-1)^4] + . . .

* Примечание. Продолжайте серию для повышения точности. Для краткости 10 ^ 9 используется в моей функции, которая выражает последовательность сходимости для естественного логарифма с примерно 7 цифрами или 10-миллионным местом для точности,

ln(x) = 10^9(1-x^(-10^(-9)))

5) Теперь просто вставьте это уравнение для естественного логарифма в упрощенное уравнение, полученное на шаге 3.

e^[((10^9)/N)(1-A^(-10^-9)] = nth-root of (A)

6) Эта реализация может показаться излишней; однако его цель - продемонстрировать, как вы можете решить корни, не догадываясь и не проверяя. Кроме того, это позволит вам заменить функцию pow из библиотеки cmath вашей собственной функцией pow:

double power(double base, double exponent) {
    if (exponent == 0) return 1;
    int wholeInt = (int)exponent;
    double decimal = exponent - (double)wholeInt;
    if (decimal) {
        int powerInv = 1/decimal;
        if (!wholeInt) return root(base,powerInv);
        else return power(root(base,powerInv),wholeInt,true);
    }
    return power(base, exponent, true);
}

double power(double base, int exponent, bool flag) {
    if (exponent < 0) return 1/power(base,-exponent,true);
    if (exponent > 0) return base * power(base,exponent-1,true);
    else return 1;
}

int root(int A, int root) {
    return power(E,(1000000000000/root)*(1-(power(A,-0.000000000001))));
}