Реализация функции Square Root в С++ не работает

double _sqrt(double n)
{
    double sqrt = 0, c = 0, prec = 1;

    for (;; sqrt += prec) //increments sqrt per precision
    {
        c = sqrt * sqrt;
        if (c == n)
        {
            return sqrt;
        }
        if (c > n) // if square is greater then..
        {
            sqrt -= prec; // decrement squareroot by previous precision
            prec *= 0.1; // increase precision eg. 1, 0.1, 0.01, 0.001 .....INF
        }
    }
}

Это функция квадратного корня, которую я сделал. Он работает для некоторых чисел, но для других он просто пуст, ничего не возвращает. Где я ошибаюсь?

Не все ваши пути в этой функции возвращают значение, поэтому у вас неопределенное поведение. Все может случиться.

πάντα ῥεῖ 20.11.2022 18:20

Ваш компилятор должен был предупредить, что не все пути управления возвращают значение.

drescherjm 20.11.2022 18:20

Сравнение двойников на точное равенство редко работает. Вам нужно сравнить абсолютную разницу с допуском, чтобы определить «достаточно близко».

Retired Ninja 20.11.2022 18:21
if (c == n) проблематична в математике с плавающей запятой. Здесь вы можете использовать некоторое значение эпсилон.
drescherjm 20.11.2022 18:21

Не помечайте C для вопросов C++.

Eric Postpischil 20.11.2022 18:22

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

Pete Becker 20.11.2022 18:43

@πάνταῥεῖ -- не вижу; единственный обратный путь — через оператор return sqrt;. Проблема, конечно, в потенциальном бесконечном цикле, но это не еще один обратный путь.

Pete Becker 20.11.2022 18:45

Числа с плавающей запятой не точны, они являются лишь приближением к реальным значениям (только столько битов для хранения информации). Это означает, что при выполнении расчетов всегда присутствуют небольшие ошибки либо в представлении числа, либо в самом расчете. Также см.: не работает математика с плавающей запятой. И именно из этого исходит ответ @RetiredNinja.

Pepijn Kramer 20.11.2022 19:11

Если бы double имел неограниченную точность, это заняло бы бесконечное количество времени для всех иррациональных корней, и вам все равно пришлось бы довольствоваться «достаточно близким» результатом.

molbdnilo 20.11.2022 19:13

1) Возможно, у вас есть бесконечный цикл; как сказали ниндзя на пенсии и drescherjm, == не рекомендуется для парного разряда. 2) Ньютон-Рафсон — лучший алгоритм и вполне может быть быстрее.

rossum 20.11.2022 19:28

Спасибо всем за ответ. Итак, @rossum существуют ли другие алгоритмы для таких сравнений, которые мне следует искать, чтобы решить эту проблему. Я проверю Ньютон-Рафсон, спасибо!

D_W 20.11.2022 19:35

См. комментарий отставного ниндзя. Вам нужно выбрать небольшой допуск, дельту, и сравнить с ним: if (abs(c - n) < delta) then ...

rossum 20.11.2022 21:38
Шаблоны Angular PrimeNg
Шаблоны Angular PrimeNg
Как привнести проверку типов в наши шаблоны Angular, использующие компоненты библиотеки PrimeNg, и настроить их отображение с помощью встроенной...
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Если вы веб-разработчик (или хотите им стать), то вы наверняка гик и вам нравятся "Звездные войны". А как бы вы хотели, чтобы фоном для вашего...
Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot
В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .
Начала с розового дизайна
Начала с розового дизайна
Pink Design - это система дизайна Appwrite с открытым исходным кодом для создания последовательных и многократно используемых пользовательских...
Шлюз в PHP
Шлюз в PHP
API-шлюз (AG) - это сервер, который действует как единая точка входа для набора микросервисов.
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
0
12
150
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

В вашем коде есть несколько проблем, первая из которых заключается в том, что ваш код может бесконечно зацикливаться, когда вы пытаетесь получить бесконечную точность для (возможно) иррационального числа. Хотя двойные числа не имеют бесконечной точности, я, конечно, не рекомендовал бы пытаться оценить эту функцию с такой высокой степенью точности. Решение этой проблемы состоит в том, чтобы добавить какое-то значение «точность» или «эпсилон» (как указано в комментариях ниже). Или даже лучше выйти из цикла, когда increment станет слишком маленьким (как предложил @Pete Becker):

double _sqrt(const double& n)
{
    const double precision = 0.000001;
    double increment = 1.0, sqrt = 0.0;

    while (true)
    {
        if (increment <= precision)
            break;
        else if (sqrt * sqrt > n)
        {
            sqrt -= increment;
            increment *= 0.1;
        }
        else 
            sqrt += increment;
    }

    return sqrt;
}

Вы, конечно, можете сделать это со стандартной библиотекой, используя std::sqrt, но я предполагаю, что вы делаете это для развлечения.

Если вас интересуют другие алгоритмы извлечения квадратного корня, в Википедии есть несколько страшных на вид здесь.

Лично мне нравится Метод Ньютона , но он для нахождения корней функций вообще. Применение этого для функции квадратного корня, которое я скопировал и изменил из здесь:

double _sqrt(const double& n)
{
    const double precision = 0.00001;
    double sqrt, x = n;

    while (true)
    {
        sqrt = 0.5 * (x + (n / x));

        if (std::abs(sqrt - x) < precision)
            break;

        x = sqrt;
    }

    return sqrt;
}

Другая возможность в первой версии — выйти из цикла, когда increment станет меньше некоторого предела.

Pete Becker 20.11.2022 21:18

Я полагаю, что ваше предложение на самом деле намного лучше, поскольку происходит определенно меньше. Я обновлю свой ответ, чтобы включить его.

UniformSoup 20.11.2022 21:59

Хороший и точный ответ! Большое спасибо.

D_W 24.11.2022 13:35

То, что вы пытаетесь сделать, похоже на бинарный поиск. Моя главная забота связана с prec = 1; и sqrt += prec, потому что, как только sqrt действительно большое число, выражение sqrt += prec никак не изменит sqrt из-за округления, и ваш цикл for застрянет...

поэтому вам нужно понять начальное значение prec и во сколько раз точность должна увеличиться на prec *= 0.1;

для чисел |x|>1 теперь у величины sqrt(x) есть половина целочисленных битов, которые необходимы для int(x), поэтому мы можем получить prec из этого

y = log2(|x|)
prec = y*0.1

log2 не обязательно должно быть реальным log2 вы можете просто взять показатель степени и разделить его на 2 и построить y как:

y = 2^((exponent_extracted_from_x>>1)+1)

для (|x|<=1) начните, например, с: prec = 0.5

Теперь конечным условием, которое вам не хватает, является остановка, как только sqrt перестанет меняться, например:

...
for (sqrt0=sqrt-prec; sqrt!=sqrt0; sqrt0=sqrt,sqrt+=prec)
 {
 ... your original code ...
 }
return sqrt;
}

Также я не вижу никакой обработки знаков (знаете на всякий случай x<0)

для получения дополнительной информации см.:

Действительно полезно. Большое спасибо. Я мог бы заставить вас ответить, если бы у меня было две квоты ответов.

D_W 24.11.2022 13:37

Другие вопросы по теме