Introduction

If you want to implement Karatsuba multiplication without BigInteger, the usual approach is to treat the input numbers as strings or arrays of digits and perform the arithmetic manually. Karatsuba reduces the number of recursive multiplications from four to three, but it does not remove the need for careful string-based addition, subtraction, and shifting.

The Core Karatsuba Identity

For two numbers split into high and low halves,

• 'x = a * 10^m + b'
• 'y = c * 10^m + d'

The schoolbook approach computes four products: ac, ad, bc, and bd.

Karatsuba replaces that with three recursive products:

• 'z2 = ac'
• 'z0 = bd'
• 'z1 = (a + b) * (c + d) - z2 - z0'

The final result is:

• 'z2 * 10^(2m) + z1 * 10^m + z0'

That is the whole algorithmic win. The rest of the work is implementing the arithmetic without overflowing native integer types.

Represent the Numbers as Strings

In Java, using strings is the simplest way to avoid BigInteger while still supporting arbitrarily large inputs.

1public static String stripLeadingZeros(String value) {
2    int i = 0;
3    while (i < value.length() - 1 && value.charAt(i) == '0') {
4        i++;
5    }
6    return value.substring(i);
7}
8
9public static String padLeft(String value, int length) {
10    return "0".repeat(Math.max(0, length - value.length())) + value;
11}

Padding is important because the recursive split is easier when both numbers have the same length.

Implement the Supporting Arithmetic

You need addition, subtraction, and decimal shifting.

1public static String addStrings(String x, String y) {
2    int i = x.length() - 1;
3    int j = y.length() - 1;
4    int carry = 0;
5    StringBuilder sb = new StringBuilder();
6
7    while (i >= 0 || j >= 0 || carry > 0) {
8        int dx = i >= 0 ? x.charAt(i--) - '0' : 0;
9        int dy = j >= 0 ? y.charAt(j--) - '0' : 0;
10        int sum = dx + dy + carry;
11        sb.append(sum % 10);
12        carry = sum / 10;
13    }
14
15    return sb.reverse().toString();
16}
17
18public static String shiftLeftDecimal(String value, int zeros) {
19    if (value.equals("0")) return value;
20    return value + "0".repeat(zeros);
21}

Subtraction is similar, assuming the left side is greater than or equal to the right side. Without these helpers, the recursive formula cannot be combined safely.

Recursive Karatsuba Skeleton

Once the helpers exist, the recursive structure becomes straightforward.

1public static String karatsuba(String x, String y) {
2    x = stripLeadingZeros(x);
3    y = stripLeadingZeros(y);
4
5    if (x.length() == 1 && y.length() == 1) {
6        return Integer.toString((x.charAt(0) - '0') * (y.charAt(0) - '0'));
7    }
8
9    int n = Math.max(x.length(), y.length());
10    if (n % 2 != 0) n++;
11
12    x = padLeft(x, n);
13    y = padLeft(y, n);
14
15    int m = n / 2;
16    String a = x.substring(0, n - m);
17    String b = x.substring(n - m);
18    String c = y.substring(0, n - m);
19    String d = y.substring(n - m);
20
21    String z2 = karatsuba(a, c);
22    String z0 = karatsuba(b, d);
23    String z1 = subtractStrings(
24        subtractStrings(karatsuba(addStrings(a, b), addStrings(c, d)), z2),
25        z0
26    );
27
28    return stripLeadingZeros(addStrings(
29        addStrings(shiftLeftDecimal(z2, 2 * m), shiftLeftDecimal(z1, m)),
30        z0
31    ));
32}

This is the core idea. In production-quality code, you also need a correct subtractStrings implementation and a small-size cutoff to avoid excessive recursion overhead.

Use a Base-Case Cutoff

Karatsuba is faster asymptotically, but for very small inputs the recursive overhead can be worse than ordinary multiplication. A practical implementation often switches to schoolbook multiplication below a threshold length.

That cutoff is an engineering detail, but it matters. An algorithm that is asymptotically better is not automatically faster on every input size.

Common Pitfalls

• Assuming Karatsuba removes the need for manual addition and subtraction helpers.
• Forgetting to normalize lengths before splitting the numbers.
• Omitting a base-case cutoff and paying too much recursion overhead on small inputs.
• Mishandling leading zeros and producing awkward or incorrect results.
• Trying to store intermediate products in native integer types and reintroducing overflow.

Summary

• Without BigInteger, Karatsuba is usually implemented on strings or digit arrays.
• The algorithm's win comes from reducing four recursive multiplications to three.
• You still need reliable helper functions for addition, subtraction, padding, and shifting.
• A small-input cutoff often makes the implementation faster in practice.
• Karatsuba is an arithmetic-structure problem, not just a recursive formula.