Russian multiplication

russian-multiplication.py

"""
A neat trick for multiplying two numbers if you're not a fan
of long multiplication.
I discovered this from a Johnny Ball Numberphile video,
https://www.youtube.com/watch?v=HJ_PP5rqLg0.
You repeatedly halve the first number, discarding fractions,
until you get to 1, keeping track of all the interim values.
At the same time, double the second number once for each halving.
Then you'll have a column of repeated halvings of the first
number and a column of repeated doublings of the second number,
so they make up pairs: one from each column.
Then strike out all the pairs where the first number, the one
from the halving column, is even.
Finally, add up all the remaining numbers in the second column,
and the result is the value of the original multiplication!
So you can multiply any two integers while only knowing how to
add, double, and halve.
See the video for why it works, but it's basically an
easy-to-understand (and hidden) way to convert the numbers into
binary.

This generates two random numbers and does the multiplication,
leading to results such as this:

  107 ×   268
   53     536
 ̶ ̶ ̶2̶6̶ ̶ ̶ ̶ ̶1̶0̶7̶2̶
   13    2144
 ̶ ̶ ̶ ̶6̶ ̶ ̶ ̶ ̶4̶2̶8̶8̶
    3    8576
    1   17152
        -----
        28676 = 268 + 536 + 2144 + 8576 + 17152
        28676 = 107 × 268 (actual answer)

"""

import random

STRIKE = {
    "0": "0̶",
    "1": "1̶",
    "2": "2̶",
    "3": "3̶",
    "4": "4̶",
    "5": "5̶",
    "6": "6̶",
    "7": "7̶",
    "8": "8̶",
    "9": "9̶",
    " ": " ̶"
}

def strikethrough(s):
    return "".join([STRIKE.get(x, x) for x in s])

a = random.randint(2, 1000)
b = random.randint(2, 1000)

pairs = [(a,b)]
while True:
    a = a // 2
    if a < 1: break
    b *= 2
    pairs.append((a, b))

first = True
bs = []
for a, b in pairs:
    mid = "×" if first else " "
    first = False
    line = f"{a:5d} {mid} {b:5d}"
    if a % 2 == 0:
        line = strikethrough(line)
    else:
        bs.append(b)
    print(line)
print("        -----")
print(f"        {sum(bs):5d} = {' + '.join([str(b) for b in bs])}")
print(f"        {pairs[0][0]*pairs[0][1]:5d} = {pairs[0][0]} × {pairs[0][1]} (actual answer)")