1 post tagged “puzzles”

Today's DailyWTF presented a programming challenge: write a function to multiply two numbers "Russian Peasant"-style.  Reading that article, I immediately recognized two things.  The first is that the algorithm essentially used a stack to hold completed portions of the calculation and then sums up that stack at the end.  The 2nd is that stacks are fundamentally related to recursion.  If I could write a stack-based solution I could also write a recursive one as well, and the code for the recursive solution would likely be fairly simple.

Of course, by the time I finished reading the article there were also already 22 comments, most of them solutions, one of them in VB.Net (not very good, imo) and one recursive one in Java, but I want to make it clear that I did not read any of those until after I completed my own implementation.  It took less than 5 minutes to write and test the stack-based solution.  In the end I discarded the stack as unnecessary and just kept a running total instead.  It then required less then 5 additional minutes to adapt this to use recursion.  I now had a working function for a grand total of 4 lines of code, and I felt it safe to take a peek at what others had done.

The only thing I added to my code based on the comments was to use bit shifts to multiply and divide by two.  In one sense you could say it's cheating to write a multiplication function that uses the multiplication operator in any way, even if you're just multiplying or dividing by two.  In this case I'd argue that the actual "Russian Peasents" suffered from the same chicken and egg problem, and so you've still met the spirit of the problem.  But clearly the bit shifting is  "better" from a standpoint of keeping your function "pure", and so I incorporated that into my code, which you can now see here:

    Function multiply(ByVal x As Integer, ByVal y As Integer) As Integer
        multiply = IIf(x Mod 2 <> 0, y, 0)
        If x > 1 Then multiply += multiply(x >> 1, y << 1)
    End Function