string arithmetic

[Tubs]

Any suggestions on how I could take two extremely long strings and perform addition, multiplication or subtraction on them and result another long string (in C)? Long int / double won't work, the digits can be up to 1000 characters long.

[wtd]

Well, let's look at the problem, without writing any code.

Let's say we have two very simple decimal numbers (as opposed to hex, binary, octal, etc) as character array string. "341" and "781".

How do we add these, without converting them to an integral type like "long"?

Well, we go back to elementary school math.

code:

341 + 781 -----

1 + 1 is 2. Ok. Simple enough.

4 + 8 is 12. Now, this is bigger than 9, which is the max value for a single digit. So, we subtract ten, and we're left with two. We'll use the two, and carry the one.

1 + 3 + 7 is 11, and we're finished, so the result is "1122".

Now, if you know how to iterate over strings backwards, and you know how to convert an ASCII digit into its corresponding integer value, then you have all of the tools you need to solve this.

[MysticVegeta]

Yes, This was a DWITE Contest question. It was quite easy to program really. All I had to do was take the numbers in string format.

say num1 length = 200
num2 length = 190

So you cant really do it "normal" way, where you take the last two, because it will give an error since num2(200) = no value. So what can you do to make the length same? Add 10 zeros in front of num2
Now the normal method works!!

[Tubs]

Ok, I will chop away at it for a couple hours. Thanks for the help

[Tubs]

Ok, I got addition and subtraction to work. Still confused on how multiplication would work though

[MysticVegeta]

If the strings are around 200 characters each, their product will be unimaginably high. I think it will exceed what a double can hold.

[wtd]

Tubs wrote:

Ok, I got addition and subtraction to work. Still confused on how multiplication would work though

Again, you have to think about the problem like a child.

[Andy]

try a long long, that might work

[Tubs]

wtd wrote:

Again, you have to think about the problem like a child.

Math sucks and I hate it and I hate it!!!!!!!!

[Geminias]

hey what exactly are we talking about here? i'd love to figure it out but your saying you add, subtract, multiply an extremely long string and return a another long string?

My guess is, that we are talking about iterating through a string and adding each ascii value for each character together and then returning the sum of that ascii value as a string? but that sounds a little funny to me. maybe someone can give me an example of whats really going on?

[wtd]

Basically, he has a really long string that represents some truly enormous number for which 32 bit or 64-bit integers aren't sufficient. He then has to perform math on these, with the result being a new string.

[MysticVegeta]

Result should be breaken down into strings because again 255 char string X 255 char string with not return a 255 char string in most of the cases unless of course there are no decimals involved/other conditions.

[Andy]

or you can just learn java and use BigDecimal :p

[md]

Why use Java when you can use something good?

Besides this is actually a good exercise for figuring out the algorythms behind something, instead of just using a peice of lirabry code. Understanding how something works is a good thing, much better then just taking for granted then it does.

[Andy]

nono im not suggesting that he shouldnt learn it himself, but for a contest, i think its much easier to use BigDecimal, im all for learning algorthims for yourself