Как я могу улучшить этот метод квадратного корня?

Question

Я знаю, это звучит как домашнее задание, но это не так. В последнее время меня интересуют алгоритмы, используемые для выполнения определенных математических операций, таких как синус, квадратный корень и т. Д. В настоящее время я пытаюсь написать вавилонский метод вычисления квадратных корней в C #.

Пока у меня есть это:

public static double SquareRoot(double x) {
    if (x == 0) return 0;

    double r = x / 2; // this is inefficient, but I can't find a better way
                      // to get a close estimate for the starting value of r
    double last = 0;
    int maxIters = 100;

    for (int i = 0; i < maxIters; i++) {
        r = (r + x / r) / 2;
        if (r == last)
            break;
        last = r;
    }

    return r;
}

Он работает просто отлично и каждый раз выдает тот же самый ответ, что и метод Math.Sqrt () .NET Framework. Как вы, вероятно, можете догадаться, однако, он медленнее, чем собственный метод (примерно на 800 тиков). Я знаю, что этот конкретный метод никогда не будет быстрее, чем собственный метод, но мне просто интересно, есть ли какие-либо оптимизации, которые я могу сделать.

Единственной оптимизацией, которую я сразу увидел, был тот факт, что вычисление будет выполнено 100 раз, даже после того, как ответ уже будет определен (в этот момент значение r всегда будет одним и тем же значением). Итак, я добавил быструю проверку, чтобы увидеть, совпадает ли вновь вычисленное значение с ранее вычисленным значением и выходит из цикла. К сожалению, это не имело большого значения для скорости, но казалось, что это правильно.

И прежде чем вы скажете: «Почему бы просто не использовать вместо этого Math.Sqrt ()?» ... Я делаю это в качестве учебного упражнения и не собираюсь фактически использовать этот метод в любом производственном коде.

Answer 1

Ну, встроенная функция Sqrt (), вероятно, не реализована в C #, скорее всего, это будет сделано на низкоуровневом языке, и, безусловно, будет использоваться более эффективный алгоритм. Так что пытаться соответствовать его скорости, вероятно, бесполезно.

Однако, что касается только попытки оптимизировать вашу функцию для heckuvit, на странице Википедии, которую вы связали, рекомендуется «начальное предположение» равное 2 ^ floor (D / 2), где D представляет количество двоичных цифр в число. Вы можете попробовать, я не вижу ничего, что можно было бы значительно оптимизировать в вашем коде.

Answer 2

Вы можете попробовать r = x >> 1;

вместо / 2 (также в другом месте ваше устройство на 2). Это может дать вам небольшое преимущество. Я бы также переместил 100 в цикл. Вероятно, ничего, но мы говорим о тиках здесь.

просто проверяю это сейчас.

EDIT: Исправлено> в >>, но оно не работает для двойников, так что не берите в голову. встраивание 100 не дало мне увеличения скорости.