java 中的大整数乘法

Question

这是我自己的方法，我也在使用我自己的BigInt class我做了所有的事情，但我似乎无法找出我做错了什么，如果有人能帮助我，我将非常感激。

public BigInt mul(BigInt o) {
    int max = n.length > o.n.length ? n.length : o.n.length;
    int[] newdigits = new int[n.length + o.n.length];

    for (int i = 0; i < max; i++)
    {
        int carry = 0;
        for (int i2 = 0; i2 < o.n.length || carry > 0; i2++)
        {
        int otherDigit = i2 >= o.n.length ? 0: o.n[i2];
            int val = (n[i] * otherDigit) + carry;
            newdigits[i + i2] += val % 10;
            carry = val / 10;
         }
     }
     return new BigInt(newdigits);
}

到目前为止，这是我的代码，但结果我得到了一个额外的零，例如：当我乘以 100*10 时，我得到 01000 而不是 1000 和另一个问题是，当我乘以 9999*1999 我得到这个：1817262619101 但正确答案是 19988001。有人可以帮我解决这个问题吗？

这是我的 BigInt class:

 public class BigInt {

    public static void main(String[] args) {

        BigInt a = new BigInt(args.length == 2 ? args[0] : "9999");
        BigInt b = new BigInt(args.length == 2 ? args[1] : "1999");

        System.out.println(a + (a.equals(b) ? " equals " : " does not equal ") + b);

        System.out.println(a + (a.compareTo(b) < 0 ? " < " : (a.compareTo(b) > 0 ? " > " : " = ")) + b);

        System.out.println(a + " + " + b + " = " + a.add(b));
        if (a.compareTo(b) >= 0) {
            System.out.println(a + " - " + b + " = " + a.sub(b));
        }
        System.out.println(a + " * " + b + " = " + a.mul(b));
        if (a.compareTo(b) >= 0) {
            System.out.println(a + " / " + b + " = " + a.div(b));
        }
    }
}

final class BigInt implements Comparable<BigInt> {

   int[] digits;
   int size;


    public BigInt() {

        n = new int[1];
    }

    public BigInt(String s) {

        n = new int[s.length()];

        for (int i = 0; i < n.length; ++i) {
            n[n.length - i - 1] = s.charAt(i) - '0';
        }

        n = trim(n);
    }

    private BigInt(int[] n) {

        this.n = new int[n.length];

        for (int i = 0; i < n.length; ++i) {
            this.n[i] = n[i];
        }
    }

    public BigInt add(BigInt o) {
        return null;
    }

    public int compareTo(BigInt o) {

        if (n.length < o.n.length) {
            return -1;
        }
        else if (n.length > o.n.length) {
            return +1;
        }

        for (int i = n.length-1; i >= 0; --i) {
            if (n[i] < o.n[i]) {
                return -1;
            }
            else if (n[i] > o.n[i]) {
                return +1;
            }
        }

        return 0;
    }

    public BigInt div(BigInt o) {

        return null;
    }

    public boolean equals(Object o) {

        if (o instanceof BigInt) {
            if (n.length == ((BigInt)o).n.length) {
                for (int i = 0; i < n.length; ++i) {
                    if (n[i] != ((BigInt)o).n[i]) {
                        return false;
                    }
                }
                return true;
            }
        }

        return false;
    }

     public BigInt mul(BigInt o) {
        int max = n.length > o.n.length ? n.length : o.n.length;
        int[] newdigits = new int[n.length + o.n.length];

        for (int i = 0; i < max; i++)
        {
            int carry = 0;
            for (int i2 = 0; i2 < o.n.length || carry > 0; i2++)
            {
            int otherDigit = i2 >= o.n.length ? 0: o.n[i2];
                int val = (n[i] * otherDigit) + carry;
                newdigits[i + i2] += val % 10;
                carry = val / 10;
             }
         }
         return new BigInt(newdigits);
    }

    public BigInt sub(BigInt o) {

      return null;
    }
    public String toString() {

        String s = "";

        for (int i : n) {
            s = i + s;
        }

        return s;
    }

    private int[] trim(int[] nums) {

        int size = nums.length;

        for (int i = nums.length - 1; i > 0; --i) {
            if (nums[i] != 0) {
                break;
            }
            --size;
        }

        int[] res = new int[size];

        for (int i = 0; i < size; ++i) {
            res[i] = nums[i];
        }

        return res;
    }

    private int[] n;
}

Answer 1

首先，看看可能的长度：

[1] * [1] = [1] 或长度(1) + 长度(1) -> 长度(1)

[9] * [9] = [8,1] 或长度(1) + 长度(1) -> 长度(2)

一个解决方案

伪代码：

if (newdigits[ (length-1) ] == 0)
    int[] newarray = new int[ (length-1) ]
    copy newdigits to newarray
    return newarray

你必须查看前面数字之前最大数字的进位。

其次，您需要将找到的先前值添加到 val 变量中。

i=0 结束：

[1, 9, 9, 7, 1, 0, 0, 0]

在 i=1 期间添加：

[0, 1, 9, 9, 7, 1, 0, 0]

i=1 结束：

[1, 10, 18, 16, 8, 1, 0, 0]

我建议您以后尝试使用 Arrays.toString(newdigits) 或使用调试器来捕获这些问题。

Answer 2

不想调试您的代码，但这是我实现该乘法的方法。它的效率有点低，但更容易跟踪进位。

public BigInt mul(BigInt o) {
    int max = n.length > o.n.length ? n.length : o.n.length;
    int[] newdigits = new int[n.length + o.n.length];

    for (int i = 0; i < max; i++) {
        for (int i2 = 0; i2 < max; i2++) {
            int digit1 = i >= n.length ? 0 : n[i];
            int digit2 = i2 >= o.n.length ? 0 : o.n[i2];
            if (digit1 > 0 && digit2 > 0) {
                int value = digit1 * digit2;
                int pos = i + i2;
                while (value > 0) {
                    int newDigit = (newdigits[pos] + value) % 10;
                    value = (newdigits[pos] + value) / 10;
                    newdigits[pos] = newDigit;
                    pos++;
                }
            }
        }
    }

    return new BigInt(newdigits);
}

java 中的大整数乘法

Big integer multiplication in java

java

biginteger

multiplication