java - 不使用 BigInteger 的 Karatsuba 算法

Question

我一直在尝试在不使用 BigInteger 的情况下在 Java 中实现 Karatsuba 算法。我的代码仅适用于两个整数相同且位数相同的情况。我没有得到正确的答案，但是我得到的答案非常接近正确的答案。例如我在 12*12 时得到 149。我无法弄清楚我的代码有什么问题，因为我相信我所做的一切都是正确的(按照书本)。这是我的代码。

public static void main(String[] args) {
    long ans=karatsuba(12,12);
    System.out.println(ans);
}

private static long karatsuba(long i, long j) {
    if (i<10 || j<10){
        return i*j;
    }
    int n=getCount(i);
    long a=(long) (i/Math.pow(10, n/2));
    long b=(long) (i%Math.pow(10, n/2));
    long c=(long) (j/Math.pow(10, n/2));
    long d=(long) (j%Math.pow(10, n/2));

    long first=karatsuba(a,c);
    long second=karatsuba(b,d);
    long third=karatsuba(a+b,c+d);

    return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10,n/2))+third));
}

private static int getCount(long i) {
    String totalN=Long.toString(i);
    return totalN.length();
}

编辑:

感谢 Ziyao Wei，问题是将“third”替换为“second”。但是我现在有另一个问题是:

如果调用 karatsuba(1234,5678)，我会得到正确的答案，但是当我调用 karatsuba(5678,1234) 时，我不会得到正确的答案。任何人都可能知道这样做的原因吗？我更新的代码是:

public static void main(String[] args) {
    //wrong answer
    long ans=karatsuba(5678,1234);
    System.out.println(ans);

    //correct answer
    long ans1=karatsuba(1234,5678);
    System.out.println(ans1);
}

private static long karatsuba(long i, long j) {
    if (i<10 || j<10){
        return i*j;
    }

    int n=getCount(i);

    long a=(long) (i/Math.pow(10, n/2));
    long b=(long) (i%Math.pow(10, n/2));
    long c=(long) (j/Math.pow(10, n/2));
    long d=(long) (j%Math.pow(10, n/2));

    long first=karatsuba(a,c);
    long second=karatsuba(b,d);
    long third=karatsuba(a+b,c+d);

    return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10, n/2))+second));

}

更新:

我已经设法将“n/2”的值四舍五入，因此它解决了问题，但是如果使用的数字超过四位，则会出现错误。这是我更新后的代码:

public static void main(String[] args) {
    System.out.println(Math.round(5.00/2));

    //correct answer
    long ans=karatsuba(5678,1234);
    System.out.println(ans);

    //correct answer
    long ans1=karatsuba(1234,5678);
    System.out.println(ans1);

    //wrong answer
    long ans2=karatsuba(102456,102465);
    System.out.println(ans2);
}


private static long karatsuba(long i, long j) {
    if (i<10 || j<10){
        return i*j;
    }

    double n=Math.round(getCount(i));

    long a=(long) (i/Math.pow(10, Math.round(n/2)));
    long b=(long) (i%Math.pow(10, Math.round(n/2)));
    long c=(long) (j/Math.pow(10, Math.round(n/2)));
    long d=(long) (j%Math.pow(10, Math.round(n/2)));

    long first=karatsuba(a,c);
    long second=karatsuba(b,d);

    long third=karatsuba(a+b,c+d);

    return ((long) ((first*Math.pow(10, Math.round(n)))+((third-second-first)*Math.pow(10, Math.round(n/2)))+second));

}

private static double getCount(long i) {
    String totalN=Long.toString(i);

    return totalN.length();
}

如果有人在不使用 BigInteger 的情况下提出了更大数字(超过四位数)的解决方案，请告诉我。谢谢。

Answer 1

你的公式是错误的。

first * Math.pow(10, n) + (third - first - second) * Math.pow(10, n / 2) + third

错了，公式应该是

first * Math.pow(10, n) + (third - first - second) * Math.pow(10, n / 2) + second

维基百科:

z0 = karatsuba(low1,low2)
z1 = karatsuba((low1+high1),(low2+high2))
z2 = karatsuba(high1,high2)
return (z2*10^(m))+((z1-z2-z0)*10^(m/2))+(z0)