卡拉茨巴乘法算法(Java 中不使用 BigInteger),递归过程中出现意外行为。

huangapple go评论66阅读模式
英文:

Karatsuba Algorithm without BigInteger in Java, unexpected behaviour while recursion

问题

以下是翻译好的内容:

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

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方法的情况下执行这个算法?

英文:

So I want to run Karatsuba Algorithm without using class BigInteger in Java, so upon following the pseudo-code and this question, I came with the following code

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

        if(i1&lt;10 || i2&lt;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(&quot;a,b,c,d :&quot; + 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) )) ;
    }

Now, the problem with this is that it's producing the wrong answer, 1234*5678 is giving 11686652, which should've been 7006652.
As a beginner to Java and algorithms, I am unable to pinpoint the exact bug in this code, also I do realize that this program is very inefficient and doesn't work for more than 4 digits (according to the linked question ). But this is intuitively what I came up with originally after learning the pseudo-code.

So my question is, what is the problem in my code and how do I execute the following algorithm without using the BigInteger method?

答案1

得分: 2

以下是您要翻译的内容:

有几件事情我注意到了:

  • 可以考虑使用 xy,而不是 i1i2
  • 变量 lenN 是整型,不是长整型
  • 没有必要对字符串表示的长度取最大值四舍五入:长度是整数,整数是整数,不需要四舍五入
  • 不需要对除以 2 进行四舍五入:整数相除的结果始终是整数(执行整数除法)
  • 错误在于 return 语句: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)));
	}

注意:由于您要求只返回翻译的内容,我已经移除了不属于翻译部分的说明性文字。如果您需要更多帮助,请随时提问。

英文:

There are a few things i notice:

  • Instead of i1 and i2 maybe use x and y
  • Variables len and N are int, not long
  • No need to round the maximum of the lengths of the string-representations: Lengths are ints, ints are whole numbers and cant be rounded
  • No need to round the division by 2: Dividing a whole number will always result in a whole number (integer division is done)
  • The error is in the return-statement: Math.pow(10, len) should be Math.pow(10, 2 * N) instead, this is important if N is uneven
  • Avoid multiple identical calculations: especially Math.pow(10, N)

<br><br>
The fixed code gives the correct results for all examples that i have tested.

	public static long recKaratsuba2(long x, long y) {
		if (x &lt; 10 || y &lt; 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)));
	}

huangapple
  • 本文由 发表于 2020年7月24日 02:21:04
  • 转载请务必保留本文链接:https://go.coder-hub.com/63060721.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定