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

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 :)