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

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.

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 `when`

s .

Categories: BeerCamp puzzle

© 2002-2019 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