10

我一直在尝试在不使用 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();
}

编辑:

多亏了魏子尧,问题是把“第三”换成了“第二”。但是我现在有另一个问题是:

如果调用 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 的情况下提出更大数字(超过四位数)的解决方案,请告诉我。谢谢。

4

9 回答 9

5

你的公式是错误的。

第一 * 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)
于 2013-07-08T16:06:39.423 回答
2

最后一个错误是 round(n) 应该是 2*round(n/2)。对于奇数 n,它们显然不同。

关于int n=getCount(i);它是不对称的来源,所以应该改变它。为了提高效率,我在上面的评论中读到的
不应将其替换为. 事实上,Karatsuba 只有在拆分平衡良好的数字时才有意义。 尝试分解使用 max 和 min 执行的操作,以确保...max(getCount(i),getCount(j))min

于 2014-03-04T20:49:28.730 回答
1

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

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 不能为奇数,但现在乘法对于我编写的一堆测试工作正常。我会尽快解释这种行为。

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

如其他地方所述,分解输入的关键是确保 b 和 d 的长度相同,以便 a 和 c 具有与系数相同的 10 次幂。无论那种力量是什么,都会成为你的 n/2;...因此,10^n 中的 n 值实际上并不是输入的总长度,而是 n/2*2。

因此,如果您以 3 位数字为例:

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

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

希望这是有道理的。

于 2015-01-19T19:24:26.363 回答
1

这是使用 long 的正确实现:

import java.util.Scanner;

/**
 * x=5678 y=1234
 * 
 * a=56,b=78
 * 
 * c=12,d=34
 * 
 * step 0 = m = n/2 + n%2
 * 
 * step 1 = a*c
 * 
 * step 2 = b*d
 * 
 * step 3 = (a + b)*(c + d)
 * 
 * step 4 = 3) - 2) - 1)
 * 
 * step 5 = 1)*pow(10, m*2) + 2) + 4)*pow(10, m)
 *
 */
public class Karatsuba {

    public static void main(String[] args) {
        long x, y;
        try (Scanner s = new Scanner(System.in)) {
            x = s.nextLong();
            y = s.nextLong();
        }
        long result = karatsuba(x, y);
        System.out.println(result);
    }

    private static long karatsuba(long x, long y) {
        if (x < 10 && y < 10)
            return x * y;

        int n = Math.max(Long.valueOf(x).toString().length(), (Long.valueOf(y).toString().length()));
        int m = n / 2 + n % 2;

        long a = x / (long) Math.pow(10, m);
        long b = x % (long) Math.pow(10, m);
        long c = y / (long) Math.pow(10, m);
        long d = y % (long) Math.pow(10, m);
        long step1 = karatsuba(a, c);
        long step2 = karatsuba(b, d);
        long step3 = karatsuba(a + b, c + d);
        long step4 = step3 - step2 - step1;
        long step5 = step1 * (long) Math.pow(10, m * 2) + step2 + step4 * (long) Math.pow(10, m);
        return step5;
    }

}

使用大整数:

import java.math.BigInteger;
import java.util.Scanner;

/**
 * x=5678 y=1234
 * 
 * a=56,b=78
 * 
 * c=12,d=34
 * 
 * step 0 = m = n/2 + n%2
 * 
 * step 1 = a*c
 * 
 * step 2 = b*d
 * 
 * step 3 = (a + b)*(c + d)
 * 
 * step 4 = 3) - 2) - 1)
 * 
 * step 5 = 1)*pow(10, m*2) + 2) + 4)*pow(10, m)
 *
 */
public class Karatsuba {

    public static void main(String[] args) {
        BigInteger x, y;
        try (Scanner s = new Scanner(System.in)) {
            x = s.nextBigInteger();
            y = s.nextBigInteger();
        }
        BigInteger result = karatsuba(x, y);
        System.out.println(result);
    }

    private static BigInteger karatsuba(BigInteger x, BigInteger y) {
        if (x.compareTo(BigInteger.valueOf(10)) < 0 && y.compareTo(BigInteger.valueOf(10)) < 0)
            return x.multiply(y);

        int n = Math.max(x.toString().length(), y.toString().length());
        int m = n / 2 + n % 2;

        BigInteger[] a_b = x.divideAndRemainder(BigInteger.valueOf(10).pow(m));
        BigInteger a = a_b[0];
        BigInteger b = a_b[1];
        BigInteger[] c_d = y.divideAndRemainder(BigInteger.valueOf(10).pow(m));
        BigInteger c = c_d[0];
        BigInteger d = c_d[1];

        BigInteger step1 = karatsuba(a, c);
        BigInteger step2 = karatsuba(b, d);
        BigInteger step3 = karatsuba(a.add(b), c.add(d));
        BigInteger step4 = step3.subtract(step2).subtract(step1);
        BigInteger step5 = step1.multiply(BigInteger.valueOf(10).pow(m * 2)).add(step2)
                .add(step4.multiply(BigInteger.valueOf(10).pow(m)));
        return step5;
    }

}
于 2018-03-18T22:46:29.950 回答
0

这是正确的方法(您的答案已修改):

public class KaratsubaMultiplication {

public static void main(String[] args) {
    //correct answer
    long ans=karatsuba(234,6788);
    System.out.println("actual    " + ans);
    System.out.println("expected  " + 234*6788);

    long ans0=karatsuba(68,156);
    System.out.println("actual    " +ans0);
    System.out.println("expected  " + 68*156);

    long ans1=karatsuba(1234,5678);
    System.out.println("actual    " + ans1);
    System.out.println("expected  " + 1234*5678);

    long ans2=karatsuba(122,456);
    System.out.println("actual    " +ans2);
    System.out.println("expected  " + 122*456);

    long ans3=karatsuba(102456,102465);
    System.out.println("actual    " + ans3);
    System.out.println("expected  " + 102456l * 102465l);
}


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

    double n=Long.toString(i).length();


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

    long first=karatsuba(a,c);

    long second=karatsuba(b,d);

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

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

}

}
于 2014-03-04T20:35:19.743 回答
0

您设置 i=a*B+b 和 j=c*B+d,其中 B=10^m 和 m=n/2。然后

i*j=B^2*(a*c)+B*(a*c+b*d-(a-b)*(c-d))+c*d

然而,在一半的情况下,B^2=10^(2m) 不等于 10^n,因为对于奇数 n,一个有 n=2*m+1,所以在这种情况下,B^2=10^(n -1)。

所以我建议定义一次 m=n/2 或更好m=(n+1)/2B=(long)Math.pow(10,m)并用它来计算 a,b,c,d 并在最终求和中使用因子 B*B。

于 2014-03-04T22:03:35.697 回答
0
first * Math.pow(10, 2*degree) + (third - first - second) * Math.pow(10, degree) + second

在哪里

degree = floor(n/2)

没有四舍五入,至少这是我所知道的......

例如,

normal: 5/2 = 2.5
floor: 5/2 = 2
round: 5/2 = 3

因此,你所做的...

round(n)

不一样

2*floor(n/2)

我是这么认为的,

问候

于 2013-08-28T15:20:09.367 回答
0

如果输入大小是奇数,我不是用 Math.round() 进行四舍五入,而是将输入大小的值(x 或 y 中数字的最小值)加 1。例如,如果 X = 127 & Y = 162,则输入大小为 3。将其增加 1 使其变为 4。然后,a = X/Math.pow(10,input_size/2) = 1。b = X%Math .pow(10,input_size/2) = 27。类似地,c = 1 和 d = 62。现在,如果我们计算 X*Y = (ac)*Math.pow(10,input_size)+(ad+bc)* Math.pow(10,input_size/2)+bd; 它给出了正确的答案。请记住,我们仅在奇数时将输入大小增加 1。完整的实现在这里 - https://github.com/parag-vijay/data_structures/blob/master/java/KaratsubaMultiplication.java

于 2017-08-15T03:58:33.727 回答
-1
/** Function to multiply two numbers **/
    public long multiply(long x, long y)
    {
        int size1 = getSize(x);
        int size2 = getSize(y);
        /** Maximum of lengths of number **/
        int N = Math.max(size1, size2);
        /** for small values directly multiply **/        
        if (N < 10)
            return x * y;
        /** max length divided, rounded up **/    
        N = (N / 2) + (N % 2);    
        /** multiplier **/
        long m = (long)Math.pow(10, N);

        /** compute sub expressions **/        
        long b = x / m;
        long a = x - (b * m);
        long d = y / m;
        long c = y - (d * N);
        /** compute sub expressions **/
        long z0 = multiply(a, c);
        long z1 = multiply(a + b, c + d);
        long z2 = multiply(b, d);          

        return z0 + ((z1 - z0 - z2) * m) + (z2 * (long)(Math.pow(10, 2 * N)));        
    }
    /** Function to calculate length or number of digits in a number **/
    public int getSize(long num)
    {
        int ctr = 0;
        while (num != 0)
        {
            ctr++;
            num /= 10;
        }
        return ctr;
    }

这就是 BigInteger 的实现:

http://www.nayuki.io/res/karatsuba-multiplication/KaratsubaMultiplication.java

于 2015-11-24T22:48:22.803 回答