C++ program

[Shaharyar]

Write a program in C++ to calculate (a^b) without using any built-in function.

[Moschops]

Give me a pony.

[Cubbi]

Do you mean bitwise XOR between a and b, or a raised to b power? If power, is b integer of floating-point?

If this is an integer power question, a simple implementation which is reasonably fast is by repeated squaring:

double mypower(double x, int n)
{
    if(n < 0) return mypower(1/x, -n);
    else if(n == 0) return 1;
    else return n%2==1 ? x*mypower(x*x, n/2) : mypower(x*x, n/2);
}

[ResidentBiscuit]

Sounds like homework, which you gave him the answer to. How do you expect him/her to learn....?

[Cubbi]

@ResidentBiscuit: Easy: either they are able to follow the code and learn something new for themselves or they submit it as a homework "solution" and deal with the consequences of clearly ignoring the material that was taught. Either experience is helpful.

[ResidentBiscuit]

Hmm never thought about it that way. Fair enough

[ThangDo]

good point .
But I wouldnt give this guy the answer anyway .

He's even too bold to add any sorta comment or anything but the "homework" he needs the answer for.

[ausairman]

Cubbi; you got me curious now. How would you deal with this without using this kind of recursion? Better yet, how would you recreate the double pow(double,double) function, which presumably doesn't do any nasty looping/recursion?

I'm gonna guess the answer is lookup tables, but I thought I'd ask..

[ResidentBiscuit]

I dont think there is anyway besides looping/recursion.

[Cubbi]

@ausairman; that recursion can be trivially rewritten as a loop, at which point you will have reproduced your typical C math library pow() function for integer powers. Can't beat O(log n) complexity.

For pow(double, double), the usual library approach is to represent it in terms of available CPU instructions: x86 has base-2 logarithms, so it is calculated, roughly, as 2^{y log₂x}, see for example glibc source code sysdeps/i386/fpu/e_pow.S (note the integer power algorithm in the beginning of that file, which is the usual repeated squaring).

If nothing is avaiable, it is usually still done through logarithms, which are decomposed into sums of series and, you're right, lookup tables. Again if you have glibc source, check out sysdeps/ia64/fpu/e_pow.S for example.

[Moschops]

This one requires natural logarithm and exponential functions. Excuse the int parameters; it's just an example.

int pow(int a, int b)
{
  return exp(b*log(a));
}

[Gaminic]

Which does bring up the question: how far does "built-in function" go? I'd say "exp" and "log" were built-in functions, but I suppose technically operator+ and operator* are as well.

[Moschops]

The lowest level of "built-in" is presumably the processor's instruction set; if we say anything apart from those are excluded, we're looking at something like this work of art

http://www.nicktencate.com/blog/2011/06/10/math-pow-in-assembly/

which looks like it simply loops.

I'm sure there are other, less time-consuming options!

[Cubbi]

If that is "work of art", then so is the bubble sort.

[ResidentBiscuit]

Hey, now bubble sort isn't the worst...