Co jest szybsze niż std :: pow?

Question

Mój program spędza 90% czasu procesora w funkcji std::pow(double,int). Dokładność nie jest tutaj najważniejsza, więc zastanawiałem się, czy istnieją jakieś szybsze alternatywy. Jedną z rzeczy, o której myślałem, to próbowanie rzucania, aby wykonać float, wykonanie operacji, a następnie powrót do podwójności (jeszcze tego nie próbowałem); Obawiam się, że to nie jest przenośny sposób na poprawę wydajności (nie działają na większość procesorów podwaja wewnętrznie tak?)

Cheers

Answer 1

Wygląda Martin Ankerl ma kilka artykułów na ten temat, Optimized Approximative pow() in C/C++ jest jeden i ma dwie szybkie wersje, jedna jest w następujący sposób:

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; 
} 

która opiera się na typ paronomazja przez Unię, która jest niezdefiniowany zachowanie C++, z projektem normy części 9.5[class.union]:

w związku najwyżej jednym nie-statycznych pól może być w dowolnym momencie, to jest o wartości wynoszącej większość jednego z niestatycznych elementów danych może być przechowywana w dowolnym momencie w unii. [...]

ale większość kompilatorów tym gcc support this with well defined behavior:

Praktyka czytania z innego członka unii niż ten ostatnio zapisywane (zwanego „typu paronomazja”) jest powszechne. Nawet -fstrict-aliasing, typu paronomazja jest dozwolone, pod warunkiem, że pamięć jest dostępna za pośrednictwem Union Typ

ale to nie jest uniwersalny jak this article points out i jak point out in my answer here użyciu memcpy powinien wygenerować identyczny kod, a nie powoływać się niezdefiniowany zachowanie.

Dodaje także odnośnik do drugiego: Optimized pow() approximation for Java, C/C++, and C#.

Pierwszy artykuł również linki do swoich microbenchmarks here

Answer 2

W zależności od tego, co trzeba zrobić, działający w domenie dziennika może działać - to znaczy, zamieniasz wszystkie swoje wartości na ich logarytmy; mnożenie staje się dodatkiem, podział staje się odejmowaniem, a potęgowanie mnożeniem. Ale teraz dodawanie i odejmowanie stają się kosztownymi i nieco podatnymi na błędy operacjami.

Answer 3

Jak duże są twoje całkowite? Czy są znane w czasie kompilacji? Znacznie lepiej jest obliczyć x^2 jako x*x w przeciwieństwie do pow(x,2). Uwaga: Prawie wszystkie aplikacje o numerze pow() na moc całkowitą obejmują podniesienie pewnej liczby do drugiej lub trzeciej potęgi (lub odwrotności multiplikatywnej w przypadku wykładników ujemnych). Używanie pow() w takich przypadkach jest przesadą. Użyj szablonu dla tych małych liczb całkowitych lub po prostu użyj x*x.

Jeśli liczby całkowite są małe, ale nie są znane w czasie kompilacji, powiedzmy między -12 a +12, mnożenie będzie nadal bić pow() i nie straci dokładności. Aby obliczyć x^12, nie potrzebujesz 11 multiplikacji. Cztery zrobi. Wykorzystaj fakt, że x^(2n) = (x^n)^2 i x^(2n + 1) = x * ((x^n)^2). Na przykład x^12 to ((x * x * x)^2)^2.Dwie mnożniki do obliczenia x^3 (x * x * x), jeszcze jedna do obliczenia x^6 i jedna ostatnia do obliczenia x^12.