Toom-Cook method for multiplication


(Team) #1

Toom-Cook algorithm is an algorithm for multiplying two N digit numbers in O(N ^ 1.465) which takes O(N ^ 2) time complexity using the native method of multiplication.

The idea is based on divide-and-conquer technique. Given two large integers, a and b, Toom–Cook algorithm splits up a and b into k smaller parts each of length l, and performs operations on the parts. As k grows, one may combine many of the multiplication sub-operations, thus reducing the overall complexity of the algorithm.

Read this article to understand the basic idea behind this wonderful algorithm for multiplication with an example

This algorithm is used in production systems as well such as McEliece Cryptosystems.

Have a doubt or thought? Feel free to comment below

This is a companion discussion topic for the original entry at