Karatsuba algorithm: Difference between revisions

Revision as of 03:46, 7 October 2007

Revision as of 21:09, 3 November 2007

Line 40:

:''Z'' = (12 + 34)(56 + 78) - ''X'' - ''Y'' = 46 ⋅ 134 - 672 - 2652 = 2840

:''X'' 10^2⋅2 + ''Y'' + ''Z'' 10² = 672 0000 + 2652 + 2840 00 = '''7006652''' = 1234 ⋅ 5678

==Algorithm==

==Complexity==

If ''T''(''n'') denotes the time it takes to multiply two ''n''-digit numbers with Karatsuba's method, then we can write