How to deal with an 64 digit input for a Karatsuba algorithm implementation in java

Question

This is my implementation and what i need for it is to calculate the multiplication of two 64 digit number. So type Long is not enough (even tho the one with parameter type of long worked just fine). However when running with String, this popped up

    Exception in thread "main" java.lang.NumberFormatException: For input string: ""
at java.base/java.lang.NumberFormatException.forInputString(NumberFormatException.java:67)
at java.base/java.lang.Long.parseLong(Long.java:721)
at java.base/java.lang.Long.parseLong(Long.java:836)
at IntegerMultipl.karatsuba(IntegerMultipl.java:60)
at IntegerMultipl.karatsuba(IntegerMultipl.java:51)
at IntegerMultipl.karatsuba(IntegerMultipl.java:54)
at IntegerMultipl.main(IntegerMultipl.java:17) 

Any help would be appreciated. This is my implementation of it.

public class IntegerMultipl {
    
    // 24 * 19 = 456
    /**
     *  a = 2 b = 4 
     *  c = 1 d = 9 
     * ac = 2 bd = 36
     * (a+b)(c+d) -ac -bd = 6 * 9 - 2 - 36 = 22
     * ac * (10 ^2 ) + bd + (22)* 10 
     * = 200 + 36 +220 
     */

    public static void main(String[] args) {
        long res = karatsuba(19,22);
        System.out.println(res);
        String result = karatsuba("19", "22");
        System.out.println(result);
        
        
    }
    /** only works when the in put is incide the range of long */
    public static long karatsuba(long x, long y){
        long n = Long.toString(x).length();
        long half = n / 2 ;
        if( x / 10 >= 1 ){
            long a = x / (long)Math.pow(10, half);
            long b = x % (long)Math.pow(10, half);
            long c = y / (long)Math.pow(10, half);
            long d =  y % (long)Math.pow(10, half);
            long fst = karatsuba(a, c);
            long lst = karatsuba(b, d);
            long trick = karatsuba(a+b, c+d) - fst - lst;
            return (long)Math.pow(10, n)* fst + lst + (long)Math.pow(10, half) * trick;
        }
        else{
                return x*y;
        }

    }
    public static String karatsuba(String x, String y){
        int n = x.length();
        int m = y.length();
        int half = n / 2 ;
        if( n > 1 ){
            String a = x.substring(0, half);
            String b = x.substring(half);
            String c = y.substring(0,half);
            String d =  y.substring(half);
            String fst = karatsuba(a, c);
            String lst = karatsuba(b, d);
            Long firstarg = Long.parseLong(a)+ Long.parseLong(b);
            Long secondarg = Long.parseLong(c)+ Long.parseLong(d);
            String mdl = karatsuba(Long.toString(firstarg), Long.toString(secondarg));
            Long gauss = Long.parseLong(mdl) - Long.parseLong(fst) - Long.parseLong(lst);
            Long res = ((long)Math.pow(10, n)* Long.parseLong(fst) + Long.parseLong(lst) + (long)Math.pow(10, half) * gauss);
            return Long.toString(res);
        }
        if(n ==1 || m ==1){
            long res = Long.parseLong(x) * Long.parseLong(y);
            return Long.toString(res);
        }
        return "Error !";

    }
   
}

Answer 1

Use java.math.BigInteger. Here's an example multiplying Long.MAX_VALUE with Long.MAX_VALUE, also showing the output:

BigInteger maxLong = BigInteger.valueOf(Long.MAX_VALUE);
BigInteger result = maxLong.multiply(maxLong);
System.out.println(result);

85070591730234615847396907784232501249