A first improvement to long multiplication is the Karatsuba Algorithm.
http://en.wikipedia.org/wiki/Karatsuba_algorithm
This was invented in 1960, and has a time complexity of order n^(log_2(3)).
It relies on the observation that two-digit multiplication can be done with only 3, rather than 4, multiplications classically required. By "dividing and conquering" (ie splitting) the numbers to be multiplied this can be extended to larger numbers.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment