在 java 中实现乘法算法

Question

我有以下乘法算法，我正在尝试使用 Java:

来实现

m:是数字的个数

n:是b的位数

β: 是基数

这是我的 java 实现此算法的函数：

public BigInteger prodbigbig(BigInteger a, BigInteger b, Integer base ){

        ArrayList<Integer> listA = new ArrayList<Integer>();
        ArrayList<Integer> listB  = new ArrayList<Integer>();
        ArrayList<Integer> listC = new ArrayList<Integer>();
        int m = a.toString().length();
        int n = b.toString().length();
        Integer carry, temp;
        BigInteger result = BigInteger.ZERO;

        for(int i = 0; i < a.toString().length(); i++){
            listA.add(Character.getNumericValue( a.toString().charAt(i)));
        }
        for(int i = 0; i < b.toString().length(); i++){
            listB.add((Character.getNumericValue( b.toString().charAt(i))));
        }
        for(int i= 0; i <= m - 1; i++){
            listC.add(0);
        }

        for(int k = 0; k <= n - 1 ; k++) {
            carry = 0;
            for(int  i = 0; i <= m - 1; i++){
                temp = (listA.get(i) * listB.get(k)) + listC.get(i + k) + carry;
                listC.add(i+k,temp % base);
                carry = temp / base;
            }
            listC.add(k + m,carry);
        }
        for(int i = 0; i < m + n; i++) {
            result = result.add(BigInteger.valueOf((long) (listC.get(i)*(Math.pow(base, i)))));
        }

        return result;
    }

但我不知道为什么我没有得到正确的结果，直到现在我无法检测到它失败的地方。

Answer 1

listC.add(i+k,temp % base);

应该是

listC.set(i+k,temp % base);

并且您对 BigInteger 的最终转换将溢出足够大的数字。我会完全摆脱 ArrayLists 并使用 int 的数组，然后在最后将其转换为 byte[] 并将其直接提供给 BigInteger.[= 的构造函数16=]

Answer 2

看起来你应该在 listC 中使用 set 而不是 add，因为 add(index, value), shift other element after index, but set replaced.

public BigInteger prodbigbig(BigInteger a, BigInteger b, Integer base ){

        ArrayList<Integer> listA = new ArrayList<Integer>();
        ArrayList<Integer> listB  = new ArrayList<Integer>();
        ArrayList<Integer> listC = new ArrayList<Integer>();
        int m = a.toString().length();
        int n = b.toString().length();
        Integer carry, temp;
        BigInteger result = BigInteger.ZERO;

        for(int i = 0; i < a.toString().length(); i++){
            listA.add(Character.getNumericValue( a.toString().charAt(i)));
        }
        for(int i = 0; i < b.toString().length(); i++){
            listB.add((Character.getNumericValue( b.toString().charAt(i))));
        }
        for(int i= 0; i <= m - 1; i++){
            listC.add(0);
        }

        for(int k = 0; k <= n - 1 ; k++) {
            carry = 0;
            for(int  i = 0; i <= m - 1; i++){
                temp = (listA.get(i) * listB.get(k)) + listC.get(i + k) + carry;
                listC.set(i+k,temp % base);
                carry = temp / base;
            }
            listC.set(k + m,carry);
        }
        for(int i = 0; i < m + n; i++) {
            result = result.add(BigInteger.valueOf((long) (listC.get(i)*(Math.pow(base, i)))));
        }

        return result;
    }

Answer 3

我通过修改代码解决了这个问题：

public BigInteger prodBigBig(BigInteger a, BigInteger b, int base ){

            BigInteger result = BigInteger.ZERO;

            if(a.compareTo(result) == 0 || b.compareTo(result) == 0)
                return result;

            int m = a.toString().length();
            int n = b.toString().length();
            int carry;
            int temp;
            ArrayList<Integer>listA = new ArrayList<>();
            ArrayList<Integer>listB = new ArrayList<>();
            int[] listC = new int[m + n];

            for(int i = m - 1; i >= 0; i--){
                listA.add(Character.getNumericValue( a.toString().charAt(i)));
                listC[i] = 0;
            }

            for(int i = n - 1; i >= 0; i--) {
                listB.add(Character.getNumericValue(b.toString().charAt(i)));
            }

            for(int k=0; k < n; k++) {
                carry = 0;
                for(int i = 0; i < m ; i++){
                    temp = (listA.get(i) * listB.get(k)) + listC[i + k] + carry;
                    listC[i + k] = temp % base;
                    carry = temp / base;
                }
                listC[k + m] = carry;
            }

            for(int i= 0; i < m + n; i++){
                result = result.add(BigInteger.valueOf((long) (listC[i] * Math.pow(base, i))));
            }
            return result;

    }

在 java 中实现乘法算法

implementing multiplication algorithm in java

java

algorithm

biginteger

multiplication