Ever since the first OMGWTF Programming Contest, I've always wanted to bring back some element of "coding challenges" to the site. Ideally, this would be in the form of a second contest... but considering that contests require a ton of work, and the fact that interns around town have come to learn that interning at Inedo basically mean means shipping mugs, mailing stickers, testing contest entries, and acting as human ottomans, we'll have to go with something a bit scaled back. And that's where Programming Praxis will come in.

The goal of Programming Praxis is simple: provide an outlet for you, the enquiring software developer, to sharpen your programming skills on a problem a bit more interesting than the normal, boring stuff. That, and to put your code where you mouth is, so to say. There is no “right” answer and no perfect solution, but some will certainly be better than others. The best of these will get a TDWTF sticker.

So, without further ado, here is your first Programming Praxis.

"It is said that Russian peasants multiply using a most curious method," writes Phil Bewig. "They start by writing the two numbers to be multiplied at the head of two columns. Then they repeatedly divide the number in the left column by two (dropping any remainder) and double the number in the right column, writing the two new numbers immediately below their predecessors, until the number in the left column is one. Then they cross out all rows where the number in the left column is even, and add the remaining numbers in the right column, which is the desired product. For instance, the product eighteen times twenty-three is found like this."

"It is easy to see why this method works if you use the grade-school method of multiplication, but with binary numbers instead of decimal numbers."

       10010                             18
     x 10111                           x 23
     -------                          -----
       00000       0 x  1 x 23            0     
      101110       1 x  2 x 23           46
     0000000       0 x  4 x 23            0
    00000000       0 x  8 x 23            0
 + 101110000       1 x 16 x 23        + 368
 -----------                         ------
 = 110011110                          = 414
   

"In binary," Phil continues, "18 is 1x2⁴ + 0x2³ + 0x2² + 1x2¹ + 0x2⁰. The odd numbers in the left column correspond to the 1 bits in the binary representation of the multiplicand."

Your challenge: write a function that multiplies two numbers using the Russian peasant algorithm. There is no language restriction, though anything on the esoteric language list will probably be ignored. Spoiler alert: the solution(s) will undoubtedly appear in the comments.