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=(A₁,A₂,A₃) and b=(B₁,B₂,B₃)

a=A₁10^2w+A₂10^w+A₃
b=B₁10^2w+B₂10^w+B₃

The result will be:

c=ab=C₁10^4w+C₂10^3w+C₃10^2w+C₄10^w+C₅ which can be represented as c=(C₁,C₂,C₃,C₄,C₅)

while:

C₁=A₁B₁
C₂=A₁B₂+A₂B₁
C₃=A₁B₃+A₂B₂+A₃B₁
C₄=A₂B₃+A₃B₂
C₅=A₃B₃

External links

• Toom-Cook 3-Way Multiplication from GMP Documentations