Karatsuba的算法不BigInteger的使用情况算法、情况、Karatsuba、BigInteger

2023-09-11 05:36:40 作者：春宵苦短

我一直在试图用Java实现Karatsuba的算法，而无需使用的BigInteger。我的code是适用的，只有当这两个整数是相同的＆放大器;的位数相同数目。我没有得到正确的答案，但是我得到的答案这是相当接近正确的。举例来说，我得到149时，12 * 12。我想不出有什么不对我的code，因为我相信我有（按章）所做的一切都是正确的。这是我的code。

I have been trying to implement Karatsuba Algorithm in java without using BigInteger. My code is applicable only when both the integers are same & have same number of digits. I do not get the correct answer however I get answer which is quite near to the right one. For instance I get 149 when 12*12. I can not figure out what is wrong with my code since I believe I have done everything right (by the book). Here's my code.

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伟，问题取代第三的第二。不过我还有一个问题，现在是：

Thanks to Ziyao Wei, the problem was replacing "third" by "second". However I have another issue now which is:

如果Karatsuba的（1234,5678）被称为我得到正确的答案然而，当我打电话Karatsuba的（5678,1234），我没有得到正确的答案。谁能可能知道什么原因呢？我的更新code是：

If karatsuba(1234,5678) is called I get the correct answer however when I call karatsuba(5678,1234) I do not get the right answer. Could anyone possibly know the reason for that? My updated code is:

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，因此它解决了问题，但是如果人数超过四位用于错误发生。这是我的更新code：的

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那么，请不要让我知道了较大的数字解决方案（超过四位数）。谢谢你。

If somebody comes up with the solution for larger numbers (more than four digits) without using BigInteger then please do let me know. Thanks.

Karatsuba的算法不BigInteger的使用情况算法、情况、Karatsuba、BigInteger

推荐答案