Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Fast positive integer power function

Name: Anonymous 2012-04-15 6:00

I'm trying to figure out how to compute an integer power of a double efficiently with as little overhead as possible (trying to avoid loops and recursion to minimize the amount of calls and jumps). Calculation speed is the priority.
So far I got this trivial piece of code:

double f(double a,char b){
if(b==2)return a*a;
if(b==3)return a*a*a;
if(b==4)return a*a*a*a;
if(b==5)return a*a*a*a*a;
if(b==6)return a*a*a*a*a*a;
if(b==7)return a*a*a*a*a*a*a;
if(b==8)return a*a*a*a*a*a*a*a;
if(b==9)return a*a*a*a*a*a*a*a*a;
        return a*a*a*a*a*a*a*a*a*a;
}


...which of course assumes the exponent is at most 10. The code can easily be expanded if higher exponents are needed.
I'm thinking this is probably optimal, but I know you /prog/riders have some magic tricks up your sleeve, so hit me with them.

Name: Anonymous 2012-04-18 2:32

>>86

I dunno. It's a lot more concise when I change the unsigned long long to unsigned int though.

c:


double power3int(double x, unsigned int n) {
  double xs = x; // always x^(2^i) power on the ith run of the loop with i starting at zero.
  double mul = 1.0;
  for(; n; xs = xs*xs, n>>=1) {
    if(n & 1) {
      mul *= xs;
    }
  }
  return mul;
}


gcc -S -O3:


power3int:
  pushl %ebp
  movl  %esp, %ebp
  movl  16(%ebp), %eax
  fldl  8(%ebp)
  testl %eax, %eax
  je  .L16
  fld1
  jmp .L19
  .p2align 4,,7
  .p2align 3
.L21:
  fxch  %st(1)
  fmul  %st(0), %st
  fxch  %st(1)
.L19:
  testb $1, %al
  je  .L17
  fmul  %st(1), %st
.L17:
  shrl  %eax
  jne .L21
  fstp  %st(1)
  popl  %ebp
  ret
.L16:
  fstp  %st(0)
  fld1
  popl  %ebp
  ret

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List