Как правильно округлить функцию квадратного корня?

В настоящее время я работаю над математической библиотекой Java, которая будет включать в себя множество правильно округленных функций (например, sqrt, cbrt, exp, sin, gamma и ln). Я уже использовал вавилонский метод для написания алгоритма извлечения квадратного корня, который является правильным с точностью до 1 ulp от правильного ответа. Однако я не могу понять, как правильно рассчитать, каким образом следует округлить число, чтобы представить наилучшее возможное приближение к фактическому квадратному корню из входных данных. Ответы, содержащие принципы, которые можно распространить на другие функции, были бы предпочтительнее, но я слышал, что sqrt - более простой случай, чем многие трансцендентные функции, и специализированные решения также будут очень благодарны.

Кроме того, вот очищенная версия моего кода на момент первоначальной отправки этого вопроса:

public static double sqrt(double x) {
    long bits = Double.doubleToLongBits(x);

    // NaN and non-zero negatives:
    if (Double.isNaN(x) || x < 0) return Double.NaN;

    // +-0 and 1:
    if (x == 0d || x == 1d) return x;

    // Halving the exponent to come up with a good initial guess:
    long exp = bits << 1;
    exp = (exp - 0x7fe0000000000000L >> 1) + 0x7fe0000000000000L >>> 1 & 0x7ff0000000000000L;
    double guess = Double.longBitsToDouble(bits & 0x800fffffffffffffL | exp);
    double nextUp, nextDown, guessSq, nextUpSq, nextDownSq;

    // Main loop:
    while (true) {
        guessSq = guess * guess;
        if (guessSq == x) return guess;
        nextUp = Math.nextUp(guess);
        nextUpSq = nextUp * nextUp;
        if (nextUpSq == x) return nextUp;
        if (guessSq < x && x < nextUpSq) {
            double z = x / nextUp;
            if (z * nextUp > x) z = Math.nextDown(z);
            return z < nextUp ? nextUp : guess;
        }
        nextDown = Math.nextDown(guess);
        nextDownSq = nextDown * nextDown;
        if (nextDownSq == x) return nextDown;
        if (nextDownSq < x && x < guessSq) {
            double z = x / guess;
            if (z * guess > x) z = Math.nextDown(z);
            return z < guess ? guess : nextDown;
        }

        // Babylonian method:
        guess = 0.5 * (guess + x / guess);
    }
}

Как видите, в качестве теста я использовал деление. Однако я считаю, что для этого требуется округление деления до 0, чего, очевидно, не происходит в Java.

Это кажется немного широким; Рекомендую уточнение. У вас есть код, которым вы можете поделиться? С каким языком вы работаете?

ggorlen 10.09.2018 08:19

пожалуйста, покажите, что вы пробовали использовать вавилонский метод. Без кода это было бы не по теме и / или слишком широко

phuclv 10.09.2018 08:29
0
2
661
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

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

По теореме Тейлора функция квадратного корня локально аппроксимируется линейной функцией с положительным наклоном 1 / 2√x. Таким образом, вы можете связать ошибку с ошибкой в ​​квадрате, x - (√x) ², где √x понимается как приблизительный корень. Затем вы округляете в направлении, которое минимизирует эту ошибку.

В любом случае, вычисление x - (√x) ² подвергается катастрофической отмене, и вам может потребоваться повышенная точность для его надежного вычисления. Не уверен, что польза стоит затраченных усилий.

Так будет ли побитовый расчет быстрее?

Evan Bailey 11.09.2018 02:10

@EvanBailey: абсолютное излишество, не делайте этого.

Yves Daoust 11.09.2018 09:13

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