# very large integer arithmetic implementation

• (2 Pages)
• 1
• 2

## 20 Replies - 899 Views - Last Post: 06 December 2012 - 10:07 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=302988&amp;s=b0c7df9c52deadf6a22353c65f1e897c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 mastapro

Reputation: 0
• 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

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

Reputation: 8362
• Posts: 31,955
• 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

### #3 mastapro

Reputation: 0
• 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

### #4 pbl

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

Reputation: 8362
• Posts: 31,955
• 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;
}

```

### #5 mastapro

Reputation: 0
• 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?

### #6 pbl

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

Reputation: 8362
• Posts: 31,955
• 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

### #7 mastapro

Reputation: 0
• 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

### #8 pbl

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

Reputation: 8362
• Posts: 31,955
• 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

### #9 mastapro

Reputation: 0
• 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

### #10 baavgai

• Dreaming Coder

Reputation: 6095
• Posts: 13,189
• 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>.

### #11 pbl

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

Reputation: 8362
• Posts: 31,955
• 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

### #12 mastapro

Reputation: 0
• 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

### #13 mastapro

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

## Re: very large integer arithmetic implementation

Posted 06 December 2012 - 02:51 PM

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?

### #14 mastapro

Reputation: 0
• 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..

### #15 baavgai

• Dreaming Coder

Reputation: 6095
• Posts: 13,189
• Joined: 16-October 07

## Re: very large integer arithmetic implementation

Posted 06 December 2012 - 04:46 PM

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