How to implement multiplication of large numbers in Java?

Question

Java

I'm going through an online course, the second day I'm struggling with the task. Unable to pass the test, gives an error: “Failed test #7. Time limit exceeded” . You have to complete the task within 5 seconds. Tell me how to speed up, or point out errors, if any
. Task:

Implement the multiplication of two numbers by the Karatsuba algorithm, the length of which does not exceed 100000. Print their product.

My code

import java.math.*;
import java.io.*;
class prog{
  public static void main(String[] args) throws Exception {					
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger A = new BigInteger(br.readLine().trim());
        BigInteger B = new BigInteger(br.readLine().trim());                
    System.out.printf((kara(A, B)).toString());
  }	
  public static BigInteger kara(BigInteger x, BigInteger y) {
    int N = Math.max(x.bitLength(), y.bitLength());
        if (N <= 2000) return x.multiply(y);
        N = (N / 2) + (N % 2);
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));
        BigInteger ac = kara(a, c);
        BigInteger bd = kara(b, d);
        BigInteger abcd = kara(a.add(b), c.add(d));
        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
    }
  }

UPD: is it possible to somehow display BigInteger faster on the screen, without converting to a string?

Answer 1

The solution is still not found, there are no more ideas ...

Answer 2

Before you need to exit the recursion, treat these large numbers as if they were strings. As soon as you need a numeric value - only then convert.