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

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

Categories: BeerCamp puzzle

© 2002-2017 Kirit & Tai Sælensminde. All forum posts are copyright their respective authors.

Licensed under a Creative Commons License. Non-commercial use is fine so long as you provide attribution.

kirit.com