Power function zoo

[Qhartb]

Continued from the "Programming Homework" thread. Emporius started that thread asking help on writing a program that raises a number to an integer exponent.

It's not a hard problem, but it's the sort of little problem that can concisely show off a coder's style and approach to a problem.

So I'm interested to see how coders here would write the function, in any language:

power, a function that takes a real base and an integer exponent and returns the real equal to the base raised to the exponent power. (If you want, you can assume the exponent to be unsigned.)

Don't worry if your solution isn't as good as someone else's. The point isn't to write the perfect power function, it's to show how you'd do it.

 

[Pesmerga]

int x, y;

cin >> x;
cin >> y;

for (int z(x); y!=0; y--) {
x*=z;
}

cout << x;
return 0;

 

[Qhartb]

How about a log time and space recursive one?

// power(b, n) computes b^n
double power(double b, unsigned int n) {
    if (n == 0)
        return 1.0;

    int ret = power(b, n >> 1);
    ret *= ret;
    if (n & 1) // n is odd
        ret *= b;
    return ret;
}

Mathematically, it's built on:

b^0      = 1
b^(2n)   = (b^n)^2
b^(2n+1) = (b^n)^2 * b

I also have a non-recursive one that only takes constant space.

edit (Feb 26 '08 6:18pm EST):

Here's the log-time constant-space function I wrote:

// power(b, n) computes b^n
double pow( double b, unsigned int n ) {
	double a = 1.0;
	double p = b;
	while(n) {
		if ( n & 1 ) { a *= p; }
		p *= p;
		n >>= 1;
	}
	return a;
}

 

[mindless_moder]

very interesting , I'm afraid i do not have anything new to contribute , how ever I'd love to do another one of these little exercises. also what do you mean by constant space? .

 

[Qhartb]

very interesting , I'm afraid i do not have anything new to contribute , how ever I'd love to do another one of these little exercises. also what do you mean by constant space? .

Often you want to know about the space and time complexities of an algorithm.

"Time" means runtime, so "constant time" means your algorithm will take the same amount of time no matter how big a job your throw at it.

"Constant space" means the same thing, except worrying about memory usage instead of runtime.

Pesmerga's function takes constant space (just the 3 ints x, y & z), but takes linear time in y (his variable name for the exponent), since the for-loop gets run y times -- if y is twice as big, the program takes twice as long to run.

My log time and space function is faster: doubling the exponent takes some amount of time longer, quadrupling it only takes twice that amount longer, and multiplying it by eight only takes three times that amount longer. Basically, it only had to take 3 more steps where Pesmerga's algorithm took 8 times as many steps.

The trade-off is that my function took up a little more memory for each of those steps and Pesmerga's didn't. (The extra memory is taken up because each level of recursion gets its own copy of b & n.) This is a classic time-space trade-off that happens all the time in computer science.

My last algorithm still runs in logarithmic time, but only takes constant space, getting the best of both worlds. You could, however, still argue that there's a trade-off: it runs fast and takes up very little memory, but it's less obvious how it works, and therefore potentially harder to debug and maintain.

I can explain how it works, if anyone wants.

 

[theGreenBunny]

Python semi-oneliner:

import operator

def pow_reduce(a, b):
	return reduce(operator.mul, [a]*b)

This creates a list filled with 'a' elements of length b, and then reduces that list to a single result by multiplying the elements like (((a * a) * a) * a) if b=4, which is of course equal to a * a * a * a = a^4.

To digress a bit, depending on the inner workings of reduce() in python, it might rival the basic python for-loop approach to this function:

def pow_for(a, b):
	temp = a
	for i in range(b-1):
		a *= temp
	return a

Because python's for-loop always iterates over a sequence (rather than specifying a lower and upper bound), one uses range to generate the sequence [0, 1, ... n-1] in order to iterate from 0 to n-1. Seeing as both the for-loop and reduce() require a list of numbers of length b (or b-1), and both are likely to be similar in their use of intermediate storage and the multiplication operation, they may be similar or equivalent in runtime and storage complexity. Of course, when the base (ie. 'a') is a real number, it requires twice as much memory, and consequently so will the sequence produced for reduce(), in which case the for-loop wins in that regard. Not to mention the higher compile-time optimisation potential of the for-loop.

Still, I would say the reduce implementation is more elegant.

For something completely different, there's the generator option:

def power_generator(a):
	i = a
	while True:
		i *= a
		yield i

def pow_gen(a, b):
	gen = power_generator(a)
	for i in range(b-2):
		gen.next()
	return gen.next()

... but that goes a bit far, just for a pun in the generator's name.