Repository: TheAlgorithms/Java
Pull request #5719 (2024-10-11 11:00:00)

feat: add karatsuba multiplication
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5719?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `6.66667%` with `14 lines` in your changes missing coverage. Please review.
> Project coverage is 62.88%. Comparing base [(`7326ab2`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/7326ab2c121ff7059bd17e5745afa7d70b98d0f0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`84569f3`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/84569f3ee4f922e3cbabc655713d4bf7bbce277e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 2 commits behind head on master.

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5719?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...m/thealgorithms/maths/KaratsubaMultiplication.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5719?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fmaths%2FKaratsubaMultiplication.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9tYXRocy9LYXJhdHN1YmFNdWx0aXBsaWNhdGlvbi5qYXZh) | 6.66% | [13 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5719?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5719      +/-   ##
============================================
+ Coverage     62.77%   62.88%   +0.10%     
- Complexity     4025     4045      +20     
============================================
  Files           565      568       +3     
  Lines         15939    16045     +106     
  Branches       3076     3084       +8     
============================================
+ Hits          10006    10090      +84     
- Misses         5521     5538      +17     
- Partials        412      417       +5     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5719?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/src/main/java/com/thealgorithms/maths/KaratsubaMultiplication.java b/src/main/java/com/thealgorithms/maths/KaratsubaMultiplication.java
new file mode 100644
index 00000000..298fcb7e
--- /dev/null
+++ b/src/main/java/com/thealgorithms/maths/KaratsubaMultiplication.java
@@ -0,0 +1,93 @@
+package com.thealgorithms.maths;
+
+import java.math.BigInteger;
+
+/**
+ * This class provides an implementation of the Karatsuba multiplication algorithm.
+ *
+ * <p>
+ * Karatsuba multiplication is a divide-and-conquer algorithm for multiplying two large
+ * numbers. It is faster than the classical multiplication algorithm and reduces the
+ * time complexity to O(n^1.585) by breaking the multiplication of two n-digit numbers
+ * into three multiplications of n/2-digit numbers.
+ * </p>
+ *
+ * <p>
+ * The main idea of the Karatsuba algorithm is based on the following observation:
+ * </p>
+ *
+ * <pre>
+ * Let x and y be two numbers:
+ * x = a * 10^m + b
+ * y = c * 10^m + d
+ *
+ * Then, the product of x and y can be expressed as:
+ * x * y = (a * c) * 10^(2*m) + ((a * d) + (b * c)) * 10^m + (b * d)
+ * </pre>
+ *
+ * The Karatsuba algorithm calculates this more efficiently by reducing the number of
+ * multiplications from four to three by using the identity:
+ *
+ * <pre>
+ * (a + b)(c + d) = ac + ad + bc + bd
+ * </pre>
+ *
+ * <p>
+ * The recursion continues until the numbers are small enough to multiply directly using
+ * the traditional method.
+ * </p>
+ */
+public final class KaratsubaMultiplication {
+
+    /**
+     * Private constructor to hide the implicit public constructor
+     */
+    private KaratsubaMultiplication() {
+    }
+
+    /**
+     * Multiplies two large numbers using the Karatsuba algorithm.
+     *
+     * <p>
+     * This method recursively splits the numbers into smaller parts until they are
+     * small enough to be multiplied directly using the traditional method.
+     * </p>
+     *
+     * @param x The first large number to be multiplied (BigInteger).
+     * @param y The second large number to be multiplied (BigInteger).
+     * @return The product of the two numbers (BigInteger).
+     */
+    public static BigInteger karatsuba(BigInteger x, BigInteger y) {
+        // Base case: when numbers are small enough, use direct multiplication
+        // If the number is 4 bits or smaller, switch to the classical method
+        if (x.bitLength() <= 4 || y.bitLength() <= 4) {
+            return x.multiply(y);
+        }
+
+        // Find the maximum bit length of the two numbers
+        int n = Math.max(x.bitLength(), y.bitLength());
+
+        // Split the numbers in the middle
+        int m = n / 2;
+
+        // High and low parts of the first number x (x = a * 10^m + b)
+        BigInteger high1 = x.shiftRight(m); // a = x / 2^m (higher part)
+        BigInteger low1 = x.subtract(high1.shiftLeft(m)); // b = x - a * 2^m (lower part)
+
+        // High and low parts of the second number y (y = c * 10^m + d)
+        BigInteger high2 = y.shiftRight(m); // c = y / 2^m (higher part)
+        BigInteger low2 = y.subtract(high2.shiftLeft(m)); // d = y - c * 2^m (lower part)
+
+        // Recursively calculate three products
+        BigInteger z0 = karatsuba(low1, low2); // z0 = b * d (low1 * low2)
+        BigInteger z1 = karatsuba(low1.add(high1), low2.add(high2)); // z1 = (a + b) * (c + d)
+        BigInteger z2 = karatsuba(high1, high2); // z2 = a * c (high1 * high2)
+
+        // Combine the results using Karatsuba's formula
+        // z0 + ((z1 - z2 - z0) << m) + (z2 << 2m)
+        return z2
+            .shiftLeft(2 * m) // z2 * 10^(2*m)
+            .add(z1.subtract(z2).subtract(z0).shiftLeft(m)) // (z1 - z2 - z0) * 10^m
+            .add(z0); // z0
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/maths/KaratsubaMultiplicationTest.java b/src/test/java/com/thealgorithms/maths/KaratsubaMultiplicationTest.java
new file mode 100644
index 00000000..e184d998
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/KaratsubaMultiplicationTest.java
@@ -0,0 +1,58 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.math.BigInteger;
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+/**
+ * Unit test class for {@link KaratsubaMultiplication} class.
+ *
+ * <p>
+ * This class tests various edge cases and normal cases for the
+ * Karatsuba multiplication algorithm implemented in the KaratsubaMultiplication class.
+ * It uses parameterized tests to handle multiple test cases.
+ * </p>
+ */
+class KaratsubaMultiplicationTest {
+
+    /**
+     * Provides test data for the parameterized test.
+     * Each entry in the stream contains three elements: x, y, and the expected result.
+     *
+     * @return a stream of arguments for the parameterized test
+     */
+    static Stream<Arguments> provideTestCases() {
+        return Stream.of(
+            // Test case 1: Two small numbers
+            Arguments.of(new BigInteger("1234"), new BigInteger("5678"), new BigInteger("7006652")),
+            // Test case 2: Two large numbers
+            Arguments.of(new BigInteger("342364"), new BigInteger("393958"), new BigInteger("134877036712")),
+            // Test case 3: One number is zero
+            Arguments.of(BigInteger.ZERO, new BigInteger("5678"), BigInteger.ZERO),
+            // Test case 4: Both numbers are zero
+            Arguments.of(BigInteger.ZERO, BigInteger.ZERO, BigInteger.ZERO),
+            // Test case 5: Single-digit numbers
+            Arguments.of(new BigInteger("9"), new BigInteger("8"), new BigInteger("72")));
+    }
+
+    /**
+     * Parameterized test for Karatsuba multiplication.
+     *
+     * <p>
+     * This method runs the Karatsuba multiplication algorithm for multiple test cases.
+     * </p>
+     *
+     * @param x the first number to multiply
+     * @param y the second number to multiply
+     * @param expected the expected result of x * y
+     */
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void testKaratsubaMultiplication(BigInteger x, BigInteger y, BigInteger expected) {
+        assertEquals(expected, KaratsubaMultiplication.karatsuba(x, y));
+    }
+}