Welcome, guest | Sign In | My Account | Store | Cart

The documentation in the function explains the algorithm but there are additional pages which provide additional visual help:

The function can handle a string as well as a sequence of digits. The test function is just to have a basic verification.

Python, 71 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
"""
    @file  lattice.py
    @brief multiplication of two numbers
"""

def lattice(valueA, valueB):
    """ the lattice calculation bases on a matrix writing
        the digits of the first value as column headers and
        writing the digits of the second value as row labels.
        Each matrix cell has a diagonal. Multiplicating the
        column digit with the row digit the result will be
        splitted like this: 9 x 8 = 72 -> 7 will written above
        the diagonal and 2 will be written below the diagonal.

        When each cell is filled - looking at the diagonals -
        you can see that - more or less - at the top right
        of a cell and at the bottom left the diagonal can be
        continued when there is a further cell. Starting at
        the bottom right of the matrix we sum up each digit
        of same diagonal.

        The last step is to adjust each sum that way that the
        value > 9 is transfered as "too much" to the next sum.
        Each time a digit remains being part of the final
        product of the multiplication. You have to start with
        the last diagonal (bottom right of matrix)
    """
    diagonals = [0] * (len(valueA) + len(valueB))
    for indexA, digitA in enumerate(valueA):
        for indexB, digitB in enumerate(valueB):
            value = int(digitA) * int(digitB)
            diagonals[indexA+indexB+0] += value // 10
            diagonals[indexA+indexB+1] += value %  10

    digits = []
    rest   = 0
    for value in reversed(diagonals):
        value += rest
        if value > 9:
            rest = value // 10
            digits.insert(0, value % 10)
        else:
            rest = 0
            digits.insert(0, value)

    if rest > 0:
        digits.insert(0, rest)

    if digits[0] == 0:
        del digits[0]
    return digits

def test():
    """ verifying lattice calculation """
    stringA = "1234567890"
    stringB = "1234567890"

    # python calculates:
    resultA = "%s" % (int(stringA) * int(stringB))
    print("%s x %s = %s" % (stringA, stringB, resultA))

    # string digits as input:
    resultB = lattice(stringA, stringB)
    assert resultB == list(map(int, resultA))

    # list of integer digits as input:
    resultC = lattice(list(map(int, stringA)), list(map(int, stringB)))
    assert resultC == list(map(int, resultA))

if __name__ == "__main__":
    test()
Created by Thomas Lehmann on Thu, 7 Jul 2011 (MIT)
Python recipes (4591)
Thomas Lehmann's recipes (18)

Required Modules

  • (none specified)

Other Information and Tasks