Categories

the russian peasants are multiplying!

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.