математика — квадратный корень в C / переполнение стека

Question

математика — квадратный корень в C / переполнение стека

Я пытаюсь реализовать свою собственную функцию квадратного корня, которая дает только интегральную часть квадратного корня, например, квадратный корень из 3 = 1.

Я видел метод Вот и попытался реализовать метод

 int mySqrt(int x)
{
int n = x;
x = pow(2, ceil(log(n) / log(2)) / 2);
int y=0;

while (y < x)
{
y = (x + n / x) / 2;
x = y;
}

return x;

}

Приведенный выше метод не подходит для ввода 8. Кроме того, я не понимаю, почему он должен работать.

Также я попробовал метод Вот

int mySqrt(int x)
{

if (x == 0) return 0;
int x0 = pow(2, (log(x) / log(2))/2) ;
int y = x0;
int diff = 10;

while (diff>0)
{
x0 = (x0 + x / x0) / 2; diff = y - x0;
y = x0;
if (diff<0) diff = diff * (-1);

}

return x0;

}

Таким образом, для входа 3 цикл продолжается … бесконечно (x0 переключается между 1 и 2).

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

2

c++math square-root

Решение

Другие решения

Попробуй это

int n,i;//n is the input number
i=0;
while(i<=n)
{
if((i*i)==n)
{
cout<<"The number has exact root : "<<i<<endl;
}
else if((i*i)>n)
{
cout<<"The integer part is "<<(i-1)<<endl;
}
i++;
}

Надеюсь это поможет.

0

Источник

Accepted Answer

Этот работает для меня:

uintmax_t zsqrt(uintmax_t x)
{
if(x==0) return 0;
uintmax_t yn = x; // The 'next' estimate
uintmax_t y = 0; // The result
uintmax_t yp; // The previous estimate
do{
yp = y;
y = yn;
yn = (y + x/y) >> 1; // Newton step
}while(yn ^ yp); // (yn != yp) shortcut for dumb compilers
return y;
}

возвращается floor(sqrt(x))

Вместо проверки на 0 с одной оценкой, тест с 2 оценками.

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

1