# Powers

Created 7th October, 2008 03:10 (UTC), last edited 7th October, 2008 03:28 (UTC)

After a brief hiatus in September due to the proper BarCamp taking place and then me being away.

It looks like the short problems are the most popular, so here is a fairly simple short one.

Write an O(log n) function that calculates m to the power n

Here is a very simple recursive function (in Haskell) which is O(n):

```power m n
| n == 0 = 1
| otherwise = m * power m ( n - 1 )```

To convert a function of this form to be O(log n) should be at most 2 lines of code (depending on the syntax rules for your language) — in Haskell it is only one line.

How much more work is it to extend the range of the answers?

This is largely a matter of the built in libraries that your language supports. The Haskell version can do some pretty big numbers without change and without losing precision:

```*Main> power 3 100
515377520732011331036461129765621272702107522001```

What is 3 to the 1,000?

If you have to write your own big number support to do this calculation then you're probably using the wrong tool for the job :)

Categories: