Divide and Conquer: Karatsuba Integer Multiplication

Written by infinity | Published 2021/08/30
Tech Story Tags: data-structures-and-algorithms | divide-and-conquer | karatsuba-algorithm | mathematics | mathematics-and-programming | mathematical-algorithms | analysis-of-algorithms | algorithmic-complexity

TLDR Karatsuba Method is preferred over grid multiplication, especially when numbers involved in the process have a large number of digits. The method/algorithm proposed is a typical example of the divide-and-conquer algorithm. It is a fast multiplication method proposed by Anatoly Karatsub in 1960. The procedure involves splitting numbers into two halves to represent the product of the original two numbers in the form of these four numbers. The algorithm is a linear time algorithm, which does not improve over the naive way of performing the multiplication.via the TL;DR App
no story
Written by infinity | Tech Enthusiast!
Published by HackerNoon on 2021/08/30
ABOUTHow hackers start their afternoons. We publish tech stories and build publishing software.

READEntirely free library read by hundreds of millions to learn anything about any technology.

WRITEHackerNoon elevates quality technology writing far and wide across the interwebs.

PARTNERHackerNoon works directly with tech companies to place ads by content relevancy