Алгоритм Карацубы: различия между версиями

При этом чтобы вычислить всё произведение, достаточно вычислить только <math>1234 \cdot 9876</math>, <math>5678\cdot 5432</math> и <math>(1234+5678)(9876+5432)</math>.

 

 

На практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка ста разрядов, на числах меньшей длины алгоритм может уступать наивному из-за большой константы, скрытой под [[«O» большое и «o» малое|О-нотацией]].