[FEATURE]
Aliqyan-21 opened this issue · 3 comments
Detailed description
Description:
What is the Karatsuba Algorithm?
The Karatsuba algorithm is a fast multiplication algorithm that was discovered by Anatolii Alexeevitch Karatsuba in 1960. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers, along with some additions and shifts.
Context
Karatsuba's Fast Multiplication is a Mathematics Algorithm which will fit in the math section of the repository.
Possible implementation
Algorithm Details
The algorithm works as follows:
If either of the input numbers is less than 10, it performs a simple multiplication.
Otherwise, it splits the input numbers into two halves and recursively applies the algorithm.
It calculates the product of the two numbers using the formula:
x _ y = (a _ c) _ 10^n + ((a + b) _ (c + d) - a _ c - b _ d) _ 10^(n/2) + b _ d
where:
a, b, c, d are the respective halves of the input numbers.
n is the number of digits in the input numbers.
Additional information
Additional Information:
This will be my implementation of the Karatsuba multiplication algorithm in C++. This implementation is my interpretation of the algorithm, according to me this is the easiest implementation out there, easier then what was on gfg atleast.
Please assign me this issue with the label Hacktoberfest.
It is already present
However if you feel that your implementation is better, I think you can make a pr suggesting modification or maybe even a new implementation according to CONTRIBUTING.md. Better consult a maintainer.
Ohh ok @ritk20 I am sorry for not checking it before.
I'll close the issue.