Powers summary

Created 21st October, 2008 09:36 (UTC), last edited 21st October, 2008 17:39 (UTC)

Only Nick Palevsky sent me something which he did in Ruby, but I can't find it on Facebook any more :( If Nick sends it to me again I'll post it on here because it was quite nice* [*I found it in my email. It's always the last place you look…] — he used a loop rather than the recursive formulation below, and the loop is much harder to get right.

The answer was very simple if you know it, not so easy if you don't. We start with this:

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

And add one line.

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

For any even power we square m and halve n. The answer to the question is:


I've broken this over a few lines.

Nick's solution

def peasant(n, power)
  case power.divmod(2).collect{|i|i.zero?}
    when [ true,true ] : 1
    when [ false,true ] : peasant(n * n, power/2)
    else n *  peasant(n * n, power/2)

puts peasant(3 ,1000).to_s

From memory I thought he was using a loop, but his is also recursive — recursion is cool! I think the divmod is kind of cool, but I do worry that it obfuscates the code too. I don't think that the logic shines through very clearly. I think there might be a simpler looking formulation that factors out the common true in the second item in the list (which is essentially a binary tuple here) for the two whens .


Discussion for this page