Karatsuba Algorithm for Multiplying Two Integers

A divide and conquer approach for multiplication

Photo by Antoine Dautry on Unsplash

All of us learned how to multiply two numbers when we were kids. In case we have forgotten (😄), let’s look at how to multiply two numbers 19 and 95.

Multiplying 19 and 95 requires 4 (2²) elementary operations as shown above. Similarly multiplying 123 and 456 would require 9…