Revision as of 09:10, 22 July 2023 edit 2001:2020:32b:bfa2:acfc:3caf:6259:4cf (talk) →Karatsuba multiplication ← Previous edit		Revision as of 09:12, 22 July 2023 edit undo 2001:2020:32b:bfa2:acfc:3caf:6259:4cf (talk) →Karatsuba multiplication Next edit →
Line 295: Karatsuba multiplication is an O(''n''<sup>log<sub>2</sub>3</sup>) ≈ O(''n''<sup>1.585</sup>) divide and conquare algorithm, that uses recursion to merge together sub calculations. By rewriting the formula, one makes it possible to do sub calculations / recursion. By doing recursion, one can solve this in a fast manner.

Multiplication algorithm: Difference between revisions