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