Powers summary

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:

132207081948080663689045525975214436596542203275214816766
492036822682859734670489954077831385060806196390977769687
258235595095458210061891186534272525795367402762022519832
080387801477422896484127439040011758861804112894781562309
443806156617305408667449050617812548034440554705439703889
581746536825491613622083026856377858229022841639830788789
691855640408489893760937324217184635993869551676501894058
810906042608967143886410281435038564874716583201061436613
2173102768902855220001

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

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 .