CODEWITHSUNDEEP
javaalgorithmbigintegermultiplication
rainman
rainman

Reputation: 2659

implementing multiplication algorithm in java

I have the following multiplication algorithm, that i am trying to implement using Java:

Big Integer multiplication algorithm

m: is the a number of digits

n: is the b number of digits

β: is the base

this is my java function that implments this algorithm:

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;
    }

but i don't know why i am not getting the correct result, until now i am not able to detect where it fails.

Upvotes: 0

Views: 2198

Answers (3)

rainman
rainman

Reputation: 2659

I resolved the problem modifying my code in this way:

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;

    }

Upvotes: 0

Slava Vedenin
Slava Vedenin

Reputation: 60244

It look like that you should use set instead of add in listC, because 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;
    }

Upvotes: 0

user207421
user207421

Reputation: 311054

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

That should be

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

and your final transformation to BigInteger will overflow with sufficiently large numbers. I would get rid of the ArrayLists altogether and use arrays of int, and then convert that to byte[] at the end and feed that directly to a constructor for BigInteger.

Upvotes: 3

Related Questions