I'd like to add (using the mathematical term) two Integer ArrayLists in Java, as well as divide them and multiply.

How would I go about this algorithmically? I can't for the life of me think of something, perhaps having to do with two's complements.

Okay, so let's say that I have large integers that are put into an ArrayLists, so to start off like 1233 and 1245. How would I divide those two with ArrayLists? a.get(i)? I could easily do it with an integer or a long, but if it had thousands of digits, that wouldn't work so well.

And yes, I'd like to add/divide the contents of the ArrayLists. If I used the get method and added them, I'd get something like [6,8,10,12] instead of that. But I guess I need to have single digits in each slot of the ArrayList. It's supposed to work similarly to BigInteger class in Java, but not use the BigInteger class.

ArrayList<Integer> a = [1,2,3,4,3,4,3,5,1,3]; 

ArrayList<Integer> b = [9,9,9,9,9,9,9,9,9,9,9];

ArrayList<Integer> c = [1,0,1,2,3,4,3,4,3,5,1,2]; //when adding

or look like c = [1,2,3,4,3,4,3,5,1,2,9,8,7,6,5,6,5,6,4,8,7]; //when multiplying

Thank you!

OK, you are implementing a Big int using array list... You may encounter the most difficult part of this assignment in implementation when you hit division. :P

Anyway, back to adding and multiplying. First you need the addition to work in order to go on multiplication. To add, you simply add from the last element of both array. You should also run a loop of the shorter number. Initial a carrier as 0. Each element index, add both of array element values. Then mod the result by 10 as the store value of the result, and divide the result by 10 as carrier. Go through all the shorter length number. Now, if the longer is longer, add the carrier to the index and keep moving up to the front until you are done. If there exists carrier value (not equal to 0) and you runs out of digit, add a new element with the value of carrier to the front of the array list.

To multiply, you do the same by going through the last element to the first element. Do it the same way you do multiplication in paper. You will see why addition is needed in order to complete the multiplication.

Edited 5 Years Ago by Taywin: n/a

Wow, thank you so much, Taywin! That was just what I needed! I now remember how I could use the mod and division operators. So, um, any suggestions of the division?

Well, for division is a bit tricky. You need to have your subtraction done first. Then, before going into division, the nominator must be greater than the denominator. If it is less than, return 0. If it is equal, return 1. Otherwise, do the division. In the division, you will start from the first index instead of last as in addition/multiplication. Then you could do the multiplication of the denominator and compare with a certain length of the denominator. Think of how you do the division in paper. It is the same way.

12345678901234567890123456789 / 9999999999

             ___________1__________________
  9999999999 )12345678901234567890123456789
               9999999999
              -----------
               2234567890
                      ...

PS: There are some other algorithms that could would optimize the division, but that would be too much to implement for you right now.

This question has already been answered. Start a new discussion instead.