时间戳

首页 > 解决方案 > Java中没有BigInteger的Karatsuba算法，递归时出现意外行为

java - Java中没有BigInteger的Karatsuba算法，递归时出现意外行为

问题描述

所以我想在 Java 中不使用类 BigInteger 来运行 Karatsuba 算法，所以在遵循伪代码和这个问题之后，我得到了以下代码

public static long recKaratsuba(long i1, long i2){

        if(i1<10 || i2<10) {
            return i1*i2 ;
        }

        long len = Math.round(Long.toString(Math.max(i1,i2)).length());
        long N  = Math.round(len/2) ;


        long b = (long) (i1% Math.pow(10, N)) ;
        long a = (long) (i1/ Math.pow(10,N));
        long d = (long) (i2% Math.pow(10,N)) ;
        long c = (long) (i2/ Math.pow(10,N));

        //System.out.println("a,b,c,d :" + a + b + c + d);



        long ac = recKaratsuba(a, c) ;
        long bd = recKaratsuba(b, d) ;
        long pos = recKaratsuba(a+b,c+d) ;

        return ((long)(bd + ac*Math.pow(10,len) + (pos -ac -bd)*Math.pow(10,N) )) ;
    }

现在，问题在于它产生了错误的答案，1234*5678 给出了 11686652，应该是 7006652。作为 Java 和算法的初学者，我无法查明这段代码中的确切错误，我也是确实意识到这个程序效率非常低，并且不能用于超过 4 位数字（根据链接的问题）。但这是我在学习了伪代码后直观地想到的。

所以我的问题是，我的代码有什么问题，如何在不使用 BigInteger 方法的情况下执行以下算法？

标签： javaalgorithmmathkaratsuba

解决方案

我注意到一些事情：

  • 代替i1和i2可能使用x和y
  • 变量len和N是 int，不是 long
  • 无需四舍五入字符串表示的最大长度：长度是整数，整数是整数，不能四舍五入
  • 无需将除法四舍五入：整数除将始终得到整数（整数除法已完成）
  • 错误在返回语句中：Math.pow(10, len)应该是 Math.pow(10, 2 * N)，如果N不均匀，这很重要
  • 避免多次相同的计算：尤其是Math.pow(10, N)



固定代码为我测试过的所有示例提供了正确的结果。

    public static long recKaratsuba2(long x, long y) {
        if (x < 10 || y < 10) {
            return x * y;
        }

        int len = Long.toString(Math.max(x, y)).length();
        double den = Math.pow(10, len / 2);
        long a = (long) (x / den);
        long b = (long) (x % den);
        long c = (long) (y / den);
        long d = (long) (y % den);

        long ac = recKaratsuba2(a, c);
        long bd = recKaratsuba2(b, d);
        long pos = recKaratsuba2(a + b, c + d);

        return (long) (bd + den * (ac * den + (pos - ac - bd)));
    }

推荐阅读