Точный sqrt(1 + (x/2)^2) + x/2

Мне нужно вычислить sqrt(1 + (x/2)^2) + x/2 численно для положительного x. Использование этого выражения напрямую не работает для очень больших значений x. Как я могу переписать его, чтобы получить более точную оценку?


person becko    schedule 25.08.2020    source источник
comment
Для вашего языка может существовать числовая библиотека или библиотека больших значений, но спрашивать о ней не по теме (как вы должны знать). Вместо этого, что вы ищете? Что вы нашли? Что вы пробовали? А на каком языке вы программируете?   -  person Some programmer dude    schedule 25.08.2020
comment
@Someprogrammerdude Почему не по теме? Я программирую на Джулии, но вопрос должен относиться к любому языку, использующему плавающую точку. Я не прошу большого решения для библиотеки с плавающей запятой. Я прошу способ переписать это для большей точности.   -  person becko    schedule 25.08.2020
comment
Если вам нужно решение, не зависящее от языка, добавьте этот тег. Если вам нужно конкретное решение для Джулии, добавьте этот тег.   -  person Some programmer dude    schedule 25.08.2020
comment
@Someprogrammerdude Готово. Я думаю, что решение можно обсудить на уровне псевдокода.   -  person becko    schedule 25.08.2020
comment
Ньютон-Рафсон может быть полезен для квадратных корней.   -  person rossum    schedule 06.09.2020


Ответы (4)


Для очень больших x вы можете выделить x/2:

sqrt(1 + (x/2)^2) + x/2
 = (x/2) * sqrt( 1/(x/2)^2 + (x/2)^2/(x/2)^2) + x/2
 = (x/2) * sqrt( (2/x)^2 + 1 ) + x/2

Для x > 2/sqrt(eps) квадратный корень фактически будет равен 1, и все ваше выражение упростится до x. Предполагая, что вам нужно охватить весь диапазон [0, infinity], я бы предложил просто разветвиться в этой точке и вернуть x в этом случае и исходную формулу, иначе:

if x > 2/sqrt(eps)  // eps is the machine epsilon of your float type
    return x
else
    return sqrt(1 + (x/2)^2) + x/2
person chtz    schedule 25.08.2020
comment
Может быть, я могу просто использовать это выражение для всех x. - person becko; 25.08.2020
comment
Мне следует ветку на x = 1? - person becko; 25.08.2020
comment
Я добавил предложение, как покрыть все поплавки (нет необходимости в делении) - person chtz; 25.08.2020
comment
@BrettHale (4/x) может переполниться для очень маленьких x, поэтому по крайней мере один из них должен учитывать другой sqrt(4): sqrt(x) * sqrt((1/x) + x/4) + (x/2) -- но вам все равно нужно ветвление для 0 (и, возможно, для субнормальных значений) и вы необходимо вычислить два sqrt (вместо одного), а также один обратный. - person chtz; 26.08.2020
comment
@chtz - ты прав. И что (4/x) будет распространять +Inf в расчет, скажем, на небольшое ниже нормального значение - вопрос явно касается только (x > 0). - person Brett Hale; 26.08.2020

Многие языки программирования предлагают функцию hypot(x,y), которая вычисляет sqrt (x*x + y*y), избегая при этом переполнения и потери значимости в промежуточных вычислениях. Многие реализации hypot также вычисляют результат более точно, чем наивное выражение. Эти преимущества достигаются за счет умеренного увеличения времени работы.

С помощью этой функции данное выражение можно записать как hypot (1.0, 0.5*x) + 0.5*x. Если выбранный вами язык программирования не поддерживает hypot или эквивалентную функцию, вы можете адаптировать реализацию, которую я предоставил в этом ответе.

person njuffa    schedule 25.08.2020

Примечание. Было отмечено, что выражение, сгенерированное Херби, может не подходить во всех контекстах. В частности, метрики, используемые для улучшения выражения Херби, могут генерировать выражения, которые хуже работают для вашего конкретного сценария. Итак, примите его выход с зерновой солью. Я думаю, вы все еще можете проконсультироваться с Херби, чтобы получить представление, но не используйте его в качестве замены.

Херби (https://herbie.uwplse.org/) рекомендует следующую замену вашего выражения:

введите здесь описание изображения

Or, in C:

double code(double x) {
    return ((double) (((double) sqrt(((double) (1.0 + ((double) pow((x / 2.0), 2.0)))))) + (x / 2.0)));
}

становится:

double code(double x) {
    double VAR;
    if (((x / 2.0) <= -8569.643649604539)) {
        VAR = (1.0 / ((double) ((1.0 / ((double) pow(x, 3.0))) - ((double) (x + (1.0 / x))))));
    } else {
        double VAR_1;
        if (((x / 2.0) <= 7.229769585372425e-11)) {
            VAR_1 = ((double) ((x / 2.0) + ((double) sqrt(((double) (1.0 + ((double) pow((x / 2.0), 2.0))))))));
        } else {
            VAR_1 = ((double) ((x / 2.0) + ((double) (((double) ((1.0 / x) + ((double) (x * 0.5)))) - (1.0 / ((double) pow(x, 3.0)))))));
        }
        VAR = VAR_1;
    }
    return VAR;
}

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

person alias    schedule 25.08.2020
comment
Разделение на 7.23e-11 выглядит ложным — и действительно, попытка аргумента типа 1e-9 с использованием последней ветки дает что-то близкое к -1e27, в то время как это должно быть значение, близкое к 1. При предоставлении предварительного условия x>=0 это дает результат, который выглядит более правдоподобным, хотя : ссылка (не уверена, что это стабильная). - person chtz; 26.08.2020
comment
Я еще не видел ни одного случая, когда результаты работы Herbie не были бы (а) бесполезными или (б) явно неправильными. Даже что-то простое, например sqrt(1+x^2) - x (у которого есть числовые проблемы, которые решаются с помощью 1 / (sqrt(1+x^2) + x) для положительного x), дает сумасшедший результат. - person Mark Dickinson; 26.08.2020
comment
Это действительно прискорбно. Вы пытались сообщить им о найденных проблемах? По моему несколько ограниченному опыту, они довольно быстро реагируют на сообщения об ошибках, и запись проблем, которые вы видели, определенно поможет. - person alias; 26.08.2020
comment
@alias: я не уверен, что есть что-то конструктивное, что я мог бы поместить в отчет об ошибке, о котором еще не сообщили другие. Например, одна из проблем, которые я наблюдаю, заключается в следующем: github.com/uwplse/herbie/ Issues/261, который по сути закрыт, так как не будет исправлен. Я могу оставить комментарий по этому вопросу. - person Mark Dickinson; 26.08.2020
comment
Я также открыл github.com/uwplse/herbie/issues/333. - person Mark Dickinson; 27.08.2020
comment
@MarkDickinson Спасибо. Ваши опасения обоснованы. Я отредактировал ответ, чтобы указать, что вывод Herbie необходимо проверять отдельно. - person alias; 27.08.2020
comment
Похоже, то, что на самом деле здесь происходит, на самом деле не является ошибкой: Herbie работает так, как задумано, но метрики, которые использует Herbie, не обязательно хорошо соответствуют тому, что может потребоваться обычному пользователю. - person Mark Dickinson; 27.08.2020

hypot()

Гипотетические функции вычисляют квадратный корень из суммы квадратов x и y без чрезмерного переполнения или потери значимости. Может возникнуть ошибка диапазона.

Затем код может получить лучший результат с hypot(1,x/2) + x/2;

person chux - Reinstate Monica    schedule 25.08.2020