Почему извлечение квадратного корня - такая медленная операция?

Многие программисты предупреждали меня не использовать функцию извлечения квадратного корня, а вместо этого возводить числа в половинную степень. У меня двоякий вопрос:

  1. Какова ощутимая / реальная выгода от этого? Почему быстрее?

  2. Если это действительно быстрее, почему функция извлечения квадратного корня вообще существует?


c# vb.net operator-keyword math square-root
person Athena    schedule 11.03.2014    source источник
comment
Рейз до 1/2 также медленный, они оба просто exp(ln(x)/2).   -  person Blindy    schedule 11.03.2014
comment
Что показало ваше тестирование?   -  person Adam Zuckerman    schedule 11.03.2014
comment
Для меня это звучит так, как будто не добавляйте вычитание 1. Вместо этого добавьте отрицательный 1.   -  person hometoast    schedule 11.03.2014
comment
Ваше первое правило всегда должно заключаться в том, чтобы писать ясный, поддерживаемый и имеющий смысл код. Если у вас нет проблем с производительностью, не беспокойтесь о производительности. Если у вас действительно есть проблемы с производительностью, то первым шагом всегда должно быть профилирование вашего приложения. Когда вы это сделаете и определили горячие точки, вы можете начать беспокоиться о том, что вы можете сделать, чтобы их исправить. Если бы вы уже были на этом этапе, у вас не было бы проблем с заменой sqrt на pow и обнаружением из первых рук, насколько ухудшилась ваша ситуация.   -  person J...    schedule 12.03.2014
comment
Комментарии J. были очень хорошими. Я бы хотел отдать должное.   -  person duffymo    schedule 12.03.2014
comment
Связано лишь частично, но интересно прочитать о константе 0x5f3759df.   -  person Wai Ha Lee    schedule 27.12.2017

Ответы (2)


arrow_upward
17
arrow_downward

Я выполнил простой тест:

  Stopwatch sw = new Stopwatch();

  sw.Start();

  Double s = 0.0;

  // compute 1e8 times either Sqrt(x) or its emulation as Pow(x, 0.5)
  for (Double d = 0; d < 1e8; d += 1)
    // s += Math.Sqrt(d);  // <- uncomment it to test Sqrt
    s += Math.Pow(d, 0.5); // <- uncomment it to test Pow

  sw.Stop();

  Console.Out.Write(sw.ElapsedMilliseconds);

(Усредненный) результат на моей рабочей станции (x64):

  Sqrt:  950 ms 
  Pow:  5500 ms

Как видите, более конкретный Sqrt(x) в 5,5 раз быстрее, чем его эмуляция Pow(x, 0.5). Так что это всего лишь еще одна легенда (по крайней мере, на C #) о том, что Sqrt настолько медленный, что следует предпочесть замену Pow

person Dmitry Bychenko    schedule 11.03.2014
comment
При тестировании (особенно) математических функций также обычно стоит указать целевую платформу или протестировать как x86, так и x64. Поскольку аппаратные реализации часто сильно различаются, иногда могут быть неожиданные различия (хотя в данном случае не так много). С тех пор я бы предположил, что это был x64. Для x86 Pow просто немного быстрее (но все же намного медленнее, чем sqrt). - person J...; 11.03.2014
comment
Примечание: 5,5 секунд для 100 миллионов операций МЕДЛЕННЫЙ. Менее секунды на 100 миллионов БЫСТРЫХ операций. Узким местом будет ваш код, а не эти вызовы функций. - person duffymo; 11.03.2014
comment
@duffymo Это банальная истина. Узкие места всегда где-то в коде. Если вы случайно заменили sqrt на Pow в узком месте производительности, то вы выиграете, не сделав этого. - person J...; 11.03.2014
comment
Конечно, узкие места в чьем-то коде. Я хочу сказать, что наиболее важные из них, скорее всего, будут в коде OP, а не в этих функциях. Профилировщик вряд ли скажет, что функция извлечения квадратного корня убивает производительность. - person duffymo; 12.03.2014
comment
@duffymo А что, если вам нужно вычислять миллионы квадратных корней в секунду? В моем случае Sqrt занимает ›10% времени процессора, и я еще даже не начал оптимизировать некоторые другие части своего кода, поэтому он будет только увеличиваться ... - person Herman; 04.04.2017
comment
Не начинайте обсуждение в комментариях. Есть вопрос? Опубликуйте это. Квадратный корень - не ваша проблема; миллионы квадратных корней - вот в чем проблема. Распараллелить проблему или изменить ее другим способом - вот выход. - person duffymo; 04.04.2017
comment
Поэтому иногда можно избежать вычисления квадратного корня, просто опуская его, например для расчета расстояния, которое должно быть ниже порогового значения. - person stephanmg; 16.04.2019

arrow_upward
10
arrow_downward

Чтобы ответить на вопрос, вам нужно кое-что знать о том, как реализована каждая функция.

Функция извлечения квадратного корня использует метод Ньютона для итеративного вычисления квадратного корня. Он сходится квадратично. Ничто не ускорит это.

Другие функции, exp () и ln (x), имеют реализации, которые имеют свои собственные проблемы сходимости / сложности. Например, можно реализовать обе как сумм рядов. Для обеспечения достаточной точности требуется определенное количество терминов.

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

Зная это, вы сможете принять осознанное решение. Я бы не стал принимать это на веру, потому что эти программисты «знают» ответ.

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

person duffymo    schedule 11.03.2014
comment
А если вы занимаетесь серьезным научным программированием, то численная стабильность ваших алгоритмов и избегание катастрофическая отмена вполне может иметь такое же (или даже большее) значение, чем скорость. - person Dan Bryant; 11.03.2014
comment
В данном случае Sqrt реализован аппаратно, как для x87 FPU (fsqrt - 32-бит), так и для SSE / SSE2 (sqrtss, _4 _; _ 5_, sqrtpd - 64-бит). Это намного быстрее, чем программные реализации для Pow и т. Д. Даже на оборудовании x87, которое имеет реализации для f2xm1, fyl2x и т. Д., Один вызов f2xm1 (который только поможет вам начать реализацию Pow) почти так же дорог, как полный fsqrt, а fyl2x более чем в три раза длиннее fsqrt. Невозможно Pow быть быстрее, исключая очень специфические крайние случаи и умные алгоритмы. - person J...; 11.03.2014