very large integer arithmetic implementation

  • (2 Pages)
  • +
  • 1
  • 2

20 Replies - 482 Views - Last Post: 06 December 2012 - 10:07 PM Rate Topic: -----

#1 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

very large integer arithmetic implementation

Posted 06 December 2012 - 09:44 AM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: very large integer arithmetic implementation

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 10:11 AM

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
Was This Post Helpful? 0
  • +
  • -

#3 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 10:20 AM

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
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 10:35 AM

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


Was This Post Helpful? 0
  • +
  • -

#5 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 10:43 AM

Thanks a lot pbl, I'm guessing it won't be as simple to add with binary?
Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 10:57 AM

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
Was This Post Helpful? 0
  • +
  • -

#7 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 11:13 AM

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
Was This Post Helpful? 0
  • +
  • -

#8 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 11:29 AM

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

Was This Post Helpful? 0
  • +
  • -

#9 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 12:17 PM

haha thanks, doesn't seem to fun to implement but i guess i'll go for it. appreciate the help
Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,594
  • Joined: 16-October 07

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 01:01 PM

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>.
Was This Post Helpful? 0
  • +
  • -

#11 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8324
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 01:14 PM

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
Was This Post Helpful? 1
  • +
  • -

#12 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 02:30 PM

also pbl, that adding code isn't working for me for some reason, i'm getting an arrayindexoutofbounds exception
Was This Post Helpful? 0
  • +
  • -

#13 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 02:51 PM

View Postbaavgai, 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?
Was This Post Helpful? 0
  • +
  • -

#14 mastapro  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 133
  • Joined: 19-September 11

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 04:35 PM

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..
Was This Post Helpful? 0
  • +
  • -

#15 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,594
  • Joined: 16-October 07

Re: very large integer arithmetic implementation

Posted 06 December 2012 - 04:46 PM

View Postmastapro, 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

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2