[mastapro]

Hi guys, so I'm trying to implement addition, subtraction, modular, multiplication, and division using very big integers but without using any of java's functions. My question is simple, before I start, do you guys think it would be better to convert the large numbers into binary or keep them in decimal? Either way I go, I'm going to put 1 digit each into an array and pad the smaller number with 0's in the front.. Any suggestions would be appreciated. Thanks.

[pbl]

Does not really make difference.... if you have really but really big numbers like 10^500 then as the use of 0 and 1 will be 8 times slower it might make a difference especially for a complex operation like division

[mastapro]

Yea I figured both ways would prob be about the same... Do you have any direction to point me in, in terms of the algorithms for each arithmetic operation? I've been looking at Vazarani's algorithm book bu it doesn't help with addition/subtraction

[pbl]

If you hold your number in an array of int addidng two number is simply if you keep them has decimal values

   int carry = 0;
   for(int i = num1.length; --i >= 0; ) {
         num3[i] = num2[i] + num1[i] + carry;
         carry = num3[i] / 10;
         num3[i] %= 10;
   }

or if you keep them as bin

   int carry = 0;
   for(int i = num1.length; --i >= 0; ) {
         num3[i] = num2[i] + num1[i] + carry;
         carry = num3[i] / 2;
         num3[i] %= 2;
   }

[mastapro]

Thanks a lot pbl, I'm guessing it won't be as simple to add with binary?

[pbl]

What do you mean ?
I gave you the code to perform a add in both situation, if you keep it as decimal or if you keep it as binary. They are bot really easy

[mastapro]

oh sorry i didn't see the 2nd part of ur post... thanks. few last questions, for a shift right of 2, is it as easy as just moving the bits 2 over to the right in the array and then padding the left side with 0's? also, is there nay pseudo code for multiplication/division with binary? thanks for the help

[pbl]

Yes, the shift are probably the easiest one to implement... if you keep your data as binary
Wanting to implement the shift and rotate would by itseleft justify the ninary approach.

For the multiplication, the easiest way, you will have to do as we did when we where kids, (trick: declare an array for every row />)

       01011101    < num1
   *   11001100    < num2
   ------------
       00000000    < num3
      00000000     < num4
     01011101
    01011101
     ....
.--------------
   later on the sum of all the rows starting at num3

Fun project />

This post has been edited by pbl: 06 December 2012 - 12:20 PM
Reason for edit:: Fixed code tags

[mastapro]

haha thanks, doesn't seem to fun to implement but i guess i'll go for it. appreciate the help

[baavgai]

Small hint for this. It's much easier to store your array of digits backwards. That is, don't get hung up on keeping things so you can read them left to right.

You can also use a List<Integer> for this, which means you don't have to care how big it gets. For binary, you could even play with List<Boolean>.

[pbl]

If you store them backward.... make a class that extends ArrayList<Integer>
overload the get() method. If the index received as parameter is >= size() simply return 0

[mastapro]

also pbl, that adding code isn't working for me for some reason, i'm getting an arrayindexoutofbounds exception

[mastapro]

baavgai, on 06 December 2012 - 01:01 PM, said:

Small hint for this. It's much easier to store your array of digits backwards. That is, don't get hung up on keeping things so you can read them left to right.

You can also use a List<Integer> for this, which means you don't have to care how big it gets. For binary, you could even play with List<Boolean>.

just wondering, what is the benefit of this? Also does List<Integer> grow as u add more elements to it?

[mastapro]

ok now i understand the benefits of reversing the array lol. it makes it a bit easier. i don't think im gonna use an arraylist but i will reverse the bits before i do the necessary arithmetic to it and then reverse it back..

[baavgai]

mastapro, on 06 December 2012 - 04:51 PM, said:

does List<Integer> grow as u add more elements to it?

Yep. That is part of the benefit.

You mightn't entirely see the benefit of going backwards until you actually attack the problem.

Consider pbl's code, going a natural direction. Then, consider the reverse.

int carry = 0, pos = 0;
while(pos<num1.size() && num2.size()) {
	int value = num2[pos] + num1[pos] + carry;
	num3[pos++] = value % base;
	carry = value / base;
}
// a couple extra whiles
if (carry!=0) {
	num3[pos++] = carry;
}

That last bit of logic can be used to extend num3 if it's a list. Going the other direction, you'll need to shift some numbers around.

This post has been edited by baavgai: 06 December 2012 - 04:46 PM