Main Page | See live article | Alphabetical index

Toom3

Toom-Cook or Toom-3 is a method of multiplying 2 integers.

Each integer's digits are divided into 3 equal length numbers, w digits wide. for example: a=37865512 will be divided to 037,865,512. w=3.
The numbers can now be represented as a=(A1,A2,A3) and b=(B1,B2,B3)

a=A1102w+A210w+A3
b=B1102w+B210w+B3

The result will be:

c=ab=C1104w+C2103w+C3102w+C410w+C5 which can be represented as c=(C1,C2,C3,C4,C5)

while:

C1=A1B1
C2=A1B2+A2B1
C3=A1B3+A2B2+A3B1
C4=A2B3+A3B2
C5=A3B3

External links