Tag: binary

  • 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.