Нахождение квадратного корня без использования функции sqrt?
Я выяснил алгоритм нахождения квадратного корня без использования функции sqrt, а затем попытался применить его в программировании. Я в конечном итоге с этим рабочим кодом в C ++
#include <iostream>
using namespace std;
double SqrtNumber(double num)
{
double lower_bound=0;
double upper_bound=num;
double temp=0; /* ek edited this line */
int nCount = 50;
while(nCount != 0)
{
temp=(lower_bound+upper_bound)/2;
if(temp*temp==num)
{
return temp;
}
else if(temp*temp > num)
{
upper_bound = temp;
}
else
{
lower_bound = temp;
}
nCount--;
}
return temp;
}
int main()
{
double num;
cout<<"Enter the number\n";
cin>>num;
if(num < 0)
{
cout<<"Error: Negative number!";
return 0;
}
cout<<"Square roots are: +"<<sqrtnum(num) and <<" and -"<<sqrtnum(num);
return 0;
}
Теперь проблема заключается в инициализации количества итераций nCount в объявлении (здесь оно составляет 50). Например, для определения квадратного корня из 36 требуется 22 итерации, поэтому проблем не возникает, тогда как для поиска квадратного корня из 15625 требуется более 50 итераций, поэтому он будет возвращать значение temp после 50 итераций. Пожалуйста, дайте решение для этого.
Решение
Существует лучший алгоритм, который требует не более 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) примерно на столько же. Другими словами, это будет сходиться очень быстро.
ОБНОВИТЬ: Для ускорения сходимости на очень больших или очень малых числах, изменено sqrt() функция для извлечения двоичного показателя и вычисления квадратного корня из числа в [1, 4) спектр. Теперь нужно frexp() от <math.h> получить двоичный показатель, но его можно получить, извлекая биты из числового формата IEEE-754 без использования frexp(),
Другие решения
Почему бы не попробовать использовать Вавилонский метод для нахождения квадратного корня.
Вот мой код для этого:
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;
}
Удачи!
Удалить свой 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;
}
если вам нужно найти квадратный корень без использования sqrt()используйте root=pow(x,0.5),
Где х — это значение, квадратный корень которого вам нужно найти.
Как я обнаружил, этот вопрос старый и у меня много ответов, но у меня есть простой ответ, который отлично работает ..
#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;
}
Я надеюсь, что это будет полезно для будущих пользователей.
//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;
}
Здесь очень просто, но небезопасный подход, чтобы найти квадратный корень из числа.
Небезопасно, потому что он работает только с натуральными числами, когда вы знаете, что основанием и показателем степени являются натуральные числа. Я должен был использовать его для задачи, где мне не разрешили использовать #включают<CMATH> -библиотека, ни мне было разрешено использовать указатели.
потенция = база ^ показатель степени
// 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;
}
Вот очень хороший код для поиска 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;
}