image

Rishabh Agarwal Hacker Noon profile picture

Multiplying numbers is one of the few things we learn while starting on the unique learning journey. The grid method used to perform the multiplication of two numbers is something we grow up doing at least a thousand times.

Yet, we all agree that this method is often time-consuming, especially when numbers involved in the process have a large number of digits. This inefficiency of grid multiplication amplifies when computers try to perform this multiplication. The inefficiency limits the computers to perform large multiplication.

Karatsuba Integer Multiplication is a fast multiplication method proposed by Anatoly Karatsuba in 1960. The method/algorithm proposed is a typical example of the divide-and-conquer algorithm. The procedure is preferred over grid multiplication, especially when numbers involved have many digits in them.

Task Definition

Given two large numbers, a and b, we have to find their product c such that c is

(a*b)

.

Numbers can have a large number of digits. Consider numbers to be represented as an array where the least significant digit is at the lowest index of the array. Each index of the array can hold an integer from 0 to 9 only.

With the task now defined clearly, we can formally start working on the problem and slowly form the solution proposed by Karatsuba.

Addition and Multiplication we Learnt at School

The addition of two numbers having n digits each (consider 0 paddings if one of the numbers has fewer digits) can be easily performed using the school addition method. Here we go from least significant digit to most significant digit, taking the carry each time we add numbers at the same significance level. It should not be difficult to digest if the addition method takes O(n) complexity.

Multiplication of two numbers, each having n digits (again consider 0 paddings if one of the numbers has fewer digits), is performed by the grid method. The first step is to create the grid, which is going over each digit of the first number and performing multiplication with all digits of the other number. Thus making the grid takes

O(n*n)

times itself. Once the grid is completed, we have to perform the last addition of adding all the rows. Since we have n rows and at max

2n+1

cols, the time to solve the problem would be

O(n*n)

. Thus the multiplication method taught in school is of order 2, which is not the fastest way.

First Attempt at the Problem

Consider a simple algorithm aimed at solving the multiplication problem slightly differently. Split the…

Continue reading: https://hackernoon.com/divide-and-conquer-karatsuba-integer-multiplication-xz8d35kh?source=rss

Source: hackernoon.com