Toom3
|
|
Toom-Cook or Toom-3 is a method of multiplying two integers.
Each integer's digits are divided into three 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
- Toom-Cook 3-Way Multiplication from GMP Documentations (http://www.swox.com/gmp/manual/Toom-Cook-3-Way-Multiplication.html#Toom-Cook%203-Way%20Multiplication)