29-Karatsuba Algorithm-23-05-2023

TEST TIME ON EUCLID’S ALGORITHM
URL:https://forms.gle/2Qag3HhHTrpx5fna8
QR CODE:
KARATSUBA
ALGORITHM
Karatsuba Algorithm
Introduction
The Karatsuba algorithm is a fast multiplication algorithm. It was

discovered by Anatoly Karatsuba in 1960 and published in 1962.
A fast multiplication algorithm uses a divide and conquer approach

to multiply two numbers.
The naive algorithm for multiplying 2 numbers has a running time

of O(n2), where karatsuba algorithm has a runtime of
Karatsuba Algorithm
Introduction
Being able to multiply numbers quickly is very important. Computer

scientists often consider multiplication to be a constant time ~
O(1) operation which is reasonable for small numbers.
Whereas for larger numbers, the actual running times need to be

factored in, which is O(n2)
Karatsuba Algorithm
Naive Method
The naive method is to follow the elementary school
multiplication method, i.e. to multiply each digit of the
second number with every digit of the first number and
then add all the multiplication results.
This algorithm takes O(n2) time.
Naive Method Karatsuba Algorithm
public static int multiplication(int X, int Y) { carry = num / 10;
// Convert numbers into string }
String x = Integer.toString(X); // else the digit is append to the
String y = Integer.toString(Y); intermediate result
int result = 0; // And assign carry as zero
// Looping over y else {
for (int i = 0; i < y.length(); i++) { inter_res =
int carry = 0; // intermediate carry Integer.toString(num) + inter_res;
String inter_res = ""; // intermediate carry = 0;
result }
// Looping over x. }
for (int j = x.length() - 1; j >= 0; j--) { // Adding the intermediate
// intermediate multiplication of each results
digit and addition of carry. result *= 10;
int num = result +=
Character.getNumericValue(y.charAt(i)) * Integer.parseInt(inter_res);
Character.getNumericValue(x.charAt(j)) + carry; }
if (num > 9 && j > 0) { System.out.print("result: ");
inter_res = Integer.toString(num % 10) return result;
+ inter_res; }}
Karatsuba Algorithm
Karatsuba Algorithm
Let’s consider two 4-digit numbers x and y where x=1234
and y=5678.
First of all, we should divide the n-digit numbers into
n/2-digit numbers as shown below.
a and c represent the first n/2 digits of x and y. Similarly,

b and d represent the last n/2 digits of x and y
Karatsuba Algorithm
The Karatsuba algorithm involves 4 main steps
Step 1: Compute a.c = 12 x 56 = 672

Step 2: Compute b.d = 34 x 78 = 2652
Step 3: Compute (a+b)(c+d) = 46 x 134 = 6164
Step 4: Compute (3)-(2)-(1)=6164-2652-672 = 2840
Finally, multiply the output of step 1 by 10n, the output of

step 4 by 10n/2, and add them both with the output of step 2.
6720000 + 284000 + 2652 = 7006652
Karatsuba Algorithm
To multiply X = 1234 and Y = 2345 using the Karatsuba algorithm
a b c d
X = 12 34 Y = 23 45
Steps:
Step 2: Compute b.d = 34 x 45 = 1530
Step 3: Compute (a+b)(c+d) = 46 x 68 = 3128
Step 4: Compute (3) - (2) - (1) = 3128 - 1530 - 276 = 1322
Finally, multiply the output of step 1 by 10000 (104), the output of step 4 by
100 (102), and add them both with the output of step 2.
Result: 2760000 + 132200 + 1530 = 2893730
The product of 1234 and 2345 using the Karatsuba algorithm is 2897730.
Karatsuba Algorithm
compute the product of 23 and 67 using the Karatsuba algorithm.
a b c d
X = 2 3 Y = 6 7

Step 2: Compute b.d = 3 x 7 = 21
Step 3: Compute (a+b)(c+d) = (2+3)(6+7) = 5 x 13 = 65
Step 4: Compute (3) - (2) - (1) = 65 - 21 - 12 = 32
Finally, multiply the output of Step 1 by 10^n (where n is the number of digits),
the output of Step 4 by 10^n/2, and add them both with the output of Step 2.
1200 + 320 + 21 = 1541
product of 23 and 67 using the Karatsuba algorithm is 1541.
Karatsuba Algorithm
Time Complexity
Assuming that we replace two of the multiplications with only one

makes the program faster.
Karatsuba improves the multiplication process by replacing the

initial complexity from quadratic to
Where n is the number of digits of the numbers multiplying.
The Time Complexity of the algorithm can be represented as follows

Karatsuba Algorithm
Time Complexity
Karatsuba Algorithm
Implementation
Algorithm
1. Compute starting set (a*c)
2. Compute set after starting set may it be ending set (b*d)
3. Compute starting set with ending sets (a+b)(c+d)
4. Subtract values of Step 3 from Step 2 from Step 1
5. Add all the values with the following modifications:-
1. Pad up 10n to the number obtained from Step 1
2. Step 2 value unchanged
3. Pad up 10n/2 to the value obtained from Step 4.
Karatsuba Algorithm
Program
Sample IO
Karatsuba Multiplication Algorithm Test
Enter the first number: 1234

Enter the second number: 2345
Product: 2893730
Karatsuba Algorithm
import java.math.BigInteger; BigInteger z0 = karatsuba(xLow, yLow);
import java.util.Scanner; BigInteger z1 = karatsuba(xLow.add(xHigh),
public class KaratsubaAlgorithm { yLow.add(yHigh));
public static BigInteger karatsuba(BigInteger BigInteger z2 = karatsuba(xHigh, yHigh);
x, BigInteger y) { // Combine the results
int n = Math.max(x.bitLength(), BigInteger result = z2.shiftLeft(2 *
y.bitLength()); half).add(z1.subtract(z2).subtract(z0).shiftLeft(h
// Base case: if either x or y is small, alf)).add(z0);
use standard multiplication return result;
if (n <= 2000) { }
return x.multiply(y); public static void main(String[] args) {
} Scanner scanner = new Scanner(System.in);
// Split the numbers into two halves System.out.print("Enter the first number:
int half = (n + 32) / 64 * 32; // round ");
up to the nearest multiple of 64 bits BigInteger x = scanner.nextBigInteger();
BigInteger mask = System.out.print("Enter the second number:
BigInteger.ONE.shiftLeft(half).subtract(BigInteger ");
.ONE); BigInteger y = scanner.nextBigInteger();
BigInteger xLow = x.and(mask); BigInteger product = karatsuba(x, y);
BigInteger yLow = y.and(mask); System.out.println("Product: " + product);
BigInteger xHigh = x.shiftRight(half); }}
BigInteger yHigh = y.shiftRight(half);
Interview questions
What is the Karatsuba algorithm?
The Karatsuba algorithm is a fast multiplication algorithm

that allows multiplying large integers in a more efficient
manner than the traditional multiplication algorithm. It
reduces the number of recursive multiplications required by
breaking down the numbers into smaller parts.
Interview questions
How does the Karatsuba algorithm work?
The Karatsuba algorithm works by splitting the input numbers

into two halves and recursively calculating three products.
These three products are combined using some arithmetic
operations to obtain the final product.
Interview questions
What are the advantages of the Karatsuba algorithm over

traditional multiplication?
The Karatsuba algorithm has a lower time complexity than
traditional multiplication algorithms for large numbers. It
reduces the number of multiplications required and, therefore,
improves the overall efficiency of the multiplication
operation.
Interview questions
Can you explain the recursive steps involved in the Karatsuba

algorithm?
In the Karatsuba algorithm, the input numbers are split

into two halves. Three recursive multiplications are
performed: one for the lower halves, one for the sum of
the halves, and one for the upper halves. These
products are combined using arithmetic operations to
obtain the final result.
/ethnuscodemithra Ethnus Codemithra /ethnus /code_mithra
https://learn.codemithra.com
[email protected] +91 7815 095 095 +91 9019 921 340

29-Karatsuba Algorithm-23-05-2023

Uploaded by

Copyright:

Available Formats

29-Karatsuba Algorithm-23-05-2023

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

29-Karatsuba Algorithm-23-05-2023

Uploaded by

Copyright:

Available Formats

TEST TIME ON EUCLID’S ALGORITHM

The Karatsuba algorithm is a fast multiplication algorithm. It was

A fast multiplication algorithm uses a divide and conquer approach

The naive algorithm for multiplying 2 numbers has a running time

Being able to multiply numbers quickly is very important. Computer

Whereas for larger numbers, the actual running times need to be

a and c represent the first n/2 digits of x and y. Similarly,

The Karatsuba algorithm involves 4 main steps

Step 1: Compute a.c = 12 x 56 = 672

Finally, multiply the output of step 1 by 10n, the output of

Step 1: Compute a.c = 2 x 6 = 12

Assuming that we replace two of the multiplications with only one

Karatsuba improves the multiplication process by replacing the

Where n is the number of digits of the numbers multiplying.

The Time Complexity of the algorithm can be represented as follows

Enter the first number: 1234

What is the Karatsuba algorithm?

The Karatsuba algorithm is a fast multiplication algorithm

How does the Karatsuba algorithm work?

The Karatsuba algorithm works by splitting the input numbers

What are the advantages of the Karatsuba algorithm over

Can you explain the recursive steps involved in the Karatsuba

In the Karatsuba algorithm, the input numbers are split

[email protected] +91 7815 095 095 +91 9019 921 340

You might also like