Что быстрее, чем std :: pow?

17

Моя программа тратит 90% времени процессора в функции std::pow(double,int) . Точность здесь не является главной проблемой, поэтому мне было интересно, есть ли более быстрые альтернативы. Одна вещь, о которой я думал, - это бросить плавать, выполнить операцию, а затем вернуться к двойному (еще не пробовал); Я обеспокоен тем, что это не переносимый способ повышения производительности (не все ли процессоры работают по принципу удвоения?)

Приветствия     

задан quant 28.05.2013 в 03:55
источник
  • В зависимости от того, какие полномочия вы рассчитываете, укажите код и / или укажите свои данные. –  paddy 28.05.2013 в 03:57
  • Аппаратное обеспечение быстрее, чем программное обеспечение в общем случае, это своего рода точка зрения ... вы не можете победить его, если не можете наложить дополнительные ограничения на то, что вы делаете. –  Mehrdad 28.05.2013 в 03:58
  • Эта статья может быть полезна: martin.ankerl.com/2012/01/25/... –  Shafik Yaghmour 28.05.2013 в 03:58
  • Что относительно 2 ^ (y * log2 (x))? Смотрите: stackoverflow.com/questions/4638473/how-to-powreal-real-in-x86 –  Derek 28.05.2013 в 04:01
  • Спасибо. Это заставит меня заняться какое-то время. Проделает некоторое профилирование и отчитается. –  quant 28.05.2013 в 04:06
Показать остальные комментарии

3 ответа

15

Похоже, что у Мартина Анкерла есть несколько статей по этому поводу, Оптимизированная аппроксимативная pow () в C / C ++ является одной и имеет две быстрые версии: один из них выглядит следующим образом:

inline double fastPow(double a, double b) {
  union {
    double d;
    int x[2];
  } u = { a };
  u.x[1] = (int)(b * (u.x[1] - 1072632447) + 1072632447);
  u.x[0] = 0;
  return u.d;
}

, который полагается на тип punning через объединение, которое является неопределенным поведением в C ++, из проекта стандартного раздела 9.5 [class.union] :

  

В объединении не более чем один из нестатических членов данных может быть активным в любое время, то есть значение at   большинство из нестатических элементов данных могут быть сохранены в союзе в любое время. [...]

, но большинство компиляторов, включая gcc поддерживают это с четко определенным поведением :

  

Практика чтения из другого члена профсоюза, чем тот, который был недавно написан (называемый «пингом типа»), является обычным явлением. Даже при использовании -fstrict-aliasing допускается использование пула типа, при условии, что доступ к памяти осуществляется через тип объединения

, но это не универсально, поскольку эта статья указывает на и как I в моем ответе здесь , используя memcpy , должен генерировать идентичный код и не вызывать неопределенное поведение.

Он также ссылается на второй Оптимизированный pow ( ) для Java, C / C ++ и C # .

В первой статье также содержатся ссылки на его микрообъекты здесь

    
ответ дан Shafik Yaghmour 28.05.2013 в 04:03
9

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

    
ответ дан hobbs 28.05.2013 в 03:59
4

Насколько велики ваши целые числа? Известны ли они во время компиляции? Гораздо лучше вычислить x^2 как x*x , а не pow(x,2) . Примечание. Почти все приложения pow() для целочисленной мощности включают в себя повышение числа до второй или третьей мощности (или мультипликативного обратного в случае отрицательных показателей). Использование pow() является избыточным в таких случаях. Используйте шаблон для этих малых целых степеней или просто используйте x*x .

Если целые числа являются небольшими, но неизвестными во время компиляции, скажем между -12 и +12, умножение по-прежнему будет бить pow() и не потеряет точность. Вам не нужно одиннадцать умножений для вычисления x ^ 12. Четверо будут делать. Используйте тот факт, что x ^ (2n) = (x ^ n) ^ 2 и x ^ (2n + 1) = x * ((x ^ n) ^ 2). Например, x ^ 12 есть ((x * x * x) ^ 2) ^ 2. Два умножения для вычисления x ^ 3 (x * x * x), еще один для вычисления x ^ 6 и один последний для вычисления x ^ 12.

    
ответ дан David Hammen 28.05.2013 в 04:10
  • Конечно, это предполагает, что ausairman работает с целыми числами. Неясно, так ли это. –  jamesdlin 28.05.2013 в 04:22
  • @jamesdin: Конечно, он есть. Моя программа тратит 90% времени процессора в функции std :: pow (double, int). –  David Hammen 28.05.2013 в 08:26
  • Ой, извините. Ты прав; Я думаю, что мой мозг был в отпуске сегодня. > _ < –  jamesdlin 28.05.2013 в 10:59
  • Этот ответ неверен в отношении последних оптимизаторов. std :: pow (x, {2, 3, 4}) ... компилируется в тот же самый код, что и соответствующие умножения. –  Jean-Michaël Celerier 18.10.2016 в 16:36
  • @ Jean-MichaëlCelerier ICC на godbolt делает это довольно хорошо. Но GCC и Clang делают это только для 2 и вызывают pow для более крупных экспонентов, если вы не укажете -Ofast. –  Christoph 21.02.2017 в 08:46