CODEWITHSUNDEEP
javaarrays
Daniel Munoz
Daniel Munoz

Reputation: 49

Multiplication through repeated addition

I'm trying to multiply two arrays of digits through repeated addition. So the number 324 = [4,2,3] times 24 = [4,2]. What im getting stuck on is iterating the addition of 324 and 324, Saving that into an array as [8,4,6] then reiterating the addition process to get [8,4,6]+[4,2,3] etc etc. This is what I have so far:

BigInt result = new BigInt();
BigInt temp = new BigInt();
int sum = 0;
int carry = 0;
int size = digitList.size();
int k = 0; //k is our multiplier 
for (int i = otherBigInt.digitList.size()-1; i >=0; i--) {
    k = 10 * k + otherBigInt.digitList.get(i);
}

This is where I perform the long addition, digit by digit. 

for (int i =0; i<size;i++) {
    sum = digitList.get(i) + digitList.get(i) + carry;
    if (sum > 9) {
        temp.digitList.add(sum%10);
        carry=1;
    } else {
        temp.digitList.add(sum);
        carry=0;
    }
    if (sum > 9 && i == size-1) {
        temp.digitList.add(sum/10);
    }
}

This is where I get stuck. What I'm trying to do here is to add 324 to the temporary array whereby it's answer then gets assigned to the result array. From here I assign the result to the temp array so that I can add to the stored result. eg: digitlist = 324, temp = 324. Result = 648 --> digitList=324, temp = 648. result = 972.

I clear the result array, so I can store a more recent result each iteration. At this point I get a nullpointerExeption where index = 0 and size =0.

for(int i=0;i<25;i++) {
    result.digitList.clear();
    for (int j=0; j<digitList.size();j++) {
        sum = digitList.get(j) + temp.digitList.get(j) + carry;
        if (sum > 9) {
            result.digitList.add(sum%10);
            carry=1;
        } else {
            result.digitList.add(sum);
            carry=0;
        }
        if (sum > 9 && j == size-1) {
            result.digitList.add(sum/10);
        }
    }
    temp.digitList = result.digitList;
    }
    return result;
}

This is a homework question, however I've been stuck on it for a while. The solution I'm coming to seems too complex for such a simple task, could someone steer me in the right direction?

Upvotes: 4

Views: 597

Answers (1)

Rainer Schwarze
Rainer Schwarze

Reputation: 4755

It might be easier, if you use other variable names to help you along:

BigInt input1 = new BigInt();
BigInt multiplier = new BigInt();

BigInt nextResult = new BigInt();
BigInt lastResult = null;

while ( ... notdone ... ) {
    nextResult.digitList.clear();
    if (lastResult==null) {
        lastResult = input1;
    } else {
        ... the addition logic: nextResult = lastResult + input1 ...
    }
    ... the logic to remember that one addition step was done ...

    lastResult = nextResult;
    nextResult = new BigInt();
}

lastResult is always your result from the previous iteration. You must be careful, that you never change digits in lastResult. The only change to lastResult must be, when you assign it from input1 or nextResult.

When you start with the addition, your lastResult has no data, because there was no "last iteration". In that case you can just initialize lastResult with input1.

nextResult is where you work in an addition iteration and store the new digits to. When that iteration is done, make it the lastResult and prepare a new nextResult on which to work. (In your code you sometimes use temp and sometimes result which adds confusion for you.)

The interesting part is, remembering how far you have calculated already. For instance with "5 x 3" after the first iteration you get a result and the "3" becomes "2" as there are two iterations left. Or with "123 x 15" the "15" decreases with each iteration first to "14", then "13", ... "10", "9", ... a.s.o.

This relates to the "... not done ..." part of the while condition.

There are a couple of optimizations possible here, of which I wouldn't want to tell much, because that is certainly part of your homework. Probably you should just go ahead and build some code until it works. Along the way you may already have ideas how to make things easier. It may also help, if you try to do the addition steps on paper. You may notice which parts could be done more easily. (If you don't find optimizations, don't worry - this needs practice and sometimes the brain is in such mood and sometimes not. Also your results must be correct, they should not be "cleverly optimized" and then be sometimes wrong.)

UPDATE: on variables and object instances

You need to make a difference between variables and the objects to which they refer.

nextResult = new BigInt();

This statement means two things: 1) You create an instance of BigInt() and 2) You reference that BigInt with lastResult.

Now this statement:

lastResult = nextResult;

THere is still the same BigInt, but now both lastResult and nextResult refer to that very same BigInt. If you change a digit in lastResult you actually change a digit in the BigInt instance. And since nextResult and lastResult refer to the same BigInt, both will deliver the identical values when fetching the digits.

This also means, that you do not need to copy the digits. They are already there.

Now this statement creates a new instance of BigInt:

nextResult = new BigInt();

Now after these three statements, nextResult refers to a new BigInt instance which is now different from the BigInt which is in lastResult.

Upvotes: 2

Related Questions