Karatsuba algorithm: Difference between revisions

Revision as of 08:28, 20 February 2007

Revision as of 22:17, 22 February 2007

Line 15:

::= ''x''₁''y''₁''B''^2''m'' + (''x''₁''y''₂ + ''x''₂''y''₁)''B''^''m'' + ''x''₂''y''₂

The standard method is to multiply the four subproducts seperatelyseparately, then finally shift and add; this is O(n²). However, Karatsuba observed that we can compute ''xy'' in only three multiplications:

:Let ''X'' = ''x''₁''y''₁

Line 30:

To compute these three products of ''m''-digit numbers, we can employ Karatsuba multiplication again, effectively using [[recursion]]. The shifts, additions and subtractions take linear time respectively, and can be considered negligible.

Karatsuba multiplication works best when the two operands are of similar size; thus while one can theoretically choose ''m'' arbitrarily, the best time bound would be acheivedachieved by choosing ''m'' such that the subproducts are roughly equal, that is setting ''m'' to be about ''n''/2.

==Example==