Blog

Via this post, I found out about Russian Peasant Multiplication, a rather clever method of multiplication that only requires, doubling, halving and adding. So I wrote some code to display it:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
results=[]
indicator=' '

left=int(sys.argv[1])
right=int(sys.argv[2])

while right >= 1:
    indicator='X'
    if right % 2:
        indicator=' '              # right number is odd,
        results.append(left)       #  so add left number to results
    print (" %s %16d \t %16d %s") % (indicator, left, right, indicator)
    left *= 2
    right /= 2

print("%s × %s = %s = %d")%(sys.argv[1], sys.argv[2],
                            ' + '.join(map(str,results)), sum(results))

So to multiply 571 × 293:

$ ./rpmult.py 571 293
                571                   293  
 X             1142                   146 X
               2284                    73  
 X             4568                    36 X
 X             9136                    18 X
              18272                     9  
 X            36544                     4 X
 X            73088                     2 X
             146176                     1  
571 × 293 = 571 + 2284 + 18272 + 146176 = 167303

Python’s still got some weirdness compared to Perl; where I’d join the list of sum terms in Perl with join(' + ', @results), in Python you have to convert the integer values to strings, then call the join method of the separator string: ' + '.join(map(str,results)). Still, I’ll give Python props for having a built-in list sum() function, which Perl lacks.