不使用BigInteger的Karatsuba算法

Question

我一直试图在java中实现Karatsuba算法，而不使用BigInteger。我的代码只适用于两个整数相同的情况&具有相同的数字数。我没有得到正确的答案，但是我得到的答案非常接近正确的答案。例如，我在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();
}

编辑：

多亏了卫自耀，问题在于把“第三”改为“第二”。不过，我现在有另一个问题，就是：

如果叫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

你的公式是错的。

第一* Math.pow(10，n) +(第三-第一秒)* Math.pow(10，n/ 2) +第三

是错误的，公式应该是

第一* Math.pow(10，n) +(第三-第一秒)* Math.pow(10，n/ 2) +第二

维基百科：

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)

Answer 2

最后一个错误是圆(N)应该是2*圆(n/2)。对于奇数n，它们明显不同。

关于int n=getCount(i);，它是一个不对称的来源，所以它应该被改变。

为了提高效率，不应该像我在上面的评论中看到的那样，用max(getCount(i),getCount(j))来代替它，而应该用min来代替它。

事实上，卡拉特赛只有在分裂平衡的数字时才有意义。

试着分解使用max和min执行的操作以确保.

Answer 3

最后，经过几个小时的思考，我找到了正确的解决方案：

public static long karatsuba(long i, long j) {
    if (i < 10 || j < 10) {
        return i * j;
    }
    double n = Math.round(getCount(i));
    if (n % 2 == 1) {
        n++;
    }
    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, n)) + ((third - first - second) * Math.pow(10, Math.round(n / 2))) + second));
}

我无法解释为什么n不能是奇数，但是现在乘法对于我编写的一系列测试是正确的。一旦我发现，我会解释这一行为的。

更新：我正在学习算法:设计和分析，第1部分课程关于，并发布了一个关于这个行为的问题。以下是安德鲁·巴顿的回答：

正如其他地方所提到的，分解输入的关键是确保b和d是相同的长度，这样a和c的幂与系数相同。无论这种力量是什么，都会成为你的n/2；因此，10^n中n的值实际上不是输入的总长度，而是n/2*2。

因此，在3位数的情况下，请按照您的示例：

n = 3;   
n/2 = 2;
n != n/2 * 2;

所以在这个例子中，n应该等于n/2 *2=4。

希望这有意义。