<div dir="ltr"><div>Is the original question here not about pow(int, int), rather than pow(float, int)? In which case the problem about rounding or precision becomes less of an issue (of course, for larger values, there will be overflows instead - but that's still a problem if you do `int a = pow(x, y) where x**y is out of range for the int value). <br><br>In my experience, it's not at all unlikely to find code like `int a = pow(2, 3);` in code, often with the resulting questions about "why is my result 7, not 8", because even with 0.5 ulp, it's not (always) EXACTLY the integer value that comes out of the function... <br><br>--<br></div>Mats<br></div><div class="gmail_extra"><br><div class="gmail_quote">On 13 January 2017 at 08:32, Francois Fayard via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Bare in mind that writing a very efficient x^n is not that straightforward. Even if it’s a corner cases, the example of x^7 is interesting. If you apply the divide and rule algorithm, you get the following algorithm:<br>
<br>
double pow_7(double x) {<br>
  const double x2 = x * x;<br>
  const double x3 = x * x2;<br>
  const double x6 = x3 * x3;<br>
  const double x7 = x * x6;<br>
<br>
  return x7;<br>
}<br>
<br>
But you can also write<br>
<br>
double pow_7(double x) {<br>
  const double x2 = x * x;<br>
  const double x3 = x * x2;<br>
  const double x4 = x2 * x2;<br>
  const double x7 = x3 * x4;<br>
<br>
  return x7;<br>
}<br>
<br>
which is a different algorithm using the same number of application. But, because of instruction level parallelism, they don’t get the same performance. In the first implementation every single instruction has to wait for the previous instruction to start. In the second one x3 and x4 could be computed using instruction level parallelism as they don’t depend upon each other.<br>
<br>
The performance difference in between the two are (compiled with -O3 and -mavx2):<br>
- clang 3.9.1: The first one is 25% slower than the second one<br>
- intel 17.0.1: The first one is 05% slower than the second one<br>
- gcc 6.2.0: The first one is 3% slower than the first one (but both are 2 times slower than clang and intel)<br>
<br>
Attached is the code asserting my claim.<br>
<br>
François Fayard<br>
<br>
=====<br>
<br>
#include <chrono><br>
#include <iostream><br>
<br>
int main() {<br>
  const int n = 1000000000;<br>
  const int length = 10;<br>
  double* x = new double[length];<br>
  for (int i = 0; i < length; ++i) {<br>
    x[i] = 1.0;<br>
  }<br>
<br>
  asm volatile("" : : "g"(x) : "memory");<br>
<br>
  auto begin = std::chrono::high_resolution_<wbr>clock::now();<br>
  for (int k = 0; k < n; ++k) {<br>
    for (int i = 0; i < length; ++i) {<br>
      const double x1 = x[i];<br>
      const double x2 = x1 * x1;<br>
      const double x3 = x1 * x2;<br>
      const double x4 = x2 * x2;<br>
      const double x7 = x3 * x4;<br>
      x[i] = x7;<br>
    }<br>
  }<br>
  auto end = std::chrono::high_resolution_<wbr>clock::now();<br>
  double time_fast =<br>
      1.0e-9 *<br>
      std::chrono::duration_cast<<wbr>std::chrono::nanoseconds>(end - begin).count();<br>
<br>
  begin = std::chrono::high_resolution_<wbr>clock::now();<br>
  for (int k = 0; k < n; ++k) {<br>
    for (int i = 0; i < length; ++i) {<br>
      const double x1 = x[i];<br>
      const double x2 = x1 * x1;<br>
      const double x3 = x1 * x2;<br>
      const double x6 = x3 * x3;<br>
      const double x7 = x1 * x6;<br>
      x[i] = x7;<br>
    }<br>
  }<br>
  end = std::chrono::high_resolution_<wbr>clock::now();<br>
  double time_divide_and_rule =<br>
      1.0e-9 *<br>
      std::chrono::duration_cast<<wbr>std::chrono::nanoseconds>(end - begin).count();<br>
<br>
  std::cout << "Optimized x^7: "<br>
            << 1.0e9 * time_fast / (static_cast<double>(n) * length) << " ns"<br>
            << std::endl;<br>
  std::cout << "  Classic x^7: "<br>
            << 1.0e9 * time_divide_and_rule / (static_cast<double>(n) * length)<br>
            << " ns" << std::endl;<br>
<br>
  delete[] x;<br>
<br>
  return 0;<br>
}<br>
<br>
=====<br>
<span class="im HOEnZb"><br>
> On Jan 9, 2017, at 6:43 PM, Wei Ding via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
><br>
> Hi,<br>
><br>
> I want an efficient way to implement function pow in LLVM instead of invoking pow() math built-in. For algorithm part, I am clear for the logic. But I am not quite sure for which parts of LLVM should I replace built-in pow with another efficient pow implementation. Any comments and feedback are appreciated. Thanks!<br>
<br>
<br>
</span><div class="HOEnZb"><div class="h5">______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div>