Algorithum help

[problemkid]

Hi good day to all,

I am suppose to write a program using class that allows me to add or subtract numbers that are very long. Eg 100 digits.

I have come out with a few ideas to go about doing it but need to clarify some points before i go about implementing it.

First and foremost,
I intend to store the long number as strings and add them up together using the ASICS code. Is this the best way to go about doing it ? Is there some other better ways.

As for adding up each character in the string using ASICS code, do i have to use a for loop and go through each chracter and adding them up? I know the "+" symbol is for adding on to the string and not real numerical addition.

Secondly,
As the two long strings of numbers that are entered may not be the same in length. I intend to do a sizeof and compare the length of both strings. If either one of the string is shorter, i will add 0s in front of it. Which string function should i use ? push back or insert ? How does both work ?

Thank you all for the help :)

[vmanes]

Do you mean ASCII code?

Using strings will have advantages in input and output, compared to storing individual digits in array or vector elements. But you'll have to be sure you do the conversion from character code to numeric value and back again correctly.

Remember that to do addition you'll have to evaluate your strings starting at the far end, where the units digit will be stored, so you'll be looping backwards.

I don't think it's necessary to put 0s at the head of the shorter string - just make your loop stop processing when it gets to the highest order digit of the shorter string, and then copy the remaining digits from longer string to the result.

[adnan.siddique]

if you want to add 0's then u have to add 0's before the string if the length of the strings are not equal.
example 1:

234243429
000123127

secondly u have to convert ascii value to integer . well that can b done by subtracting 48 from its acsii value. e.g ascii of 4 is 52. when u subtract 48 from 52 answer will b 4.
thirdly u also have to take care about carry. in the above example 1 when u add 9 and 7 answer will b 16 now u have to put 6 in your answer string and 1 as carry. well that can b done by mod operator. 16 mod 10 = 6 and 1 mod 10 = 1.
so care about carries too.

*************** GOOD LUCK*****************

[problemkid]

Hi good day,

I have just found out that the question seems to be harder than i originally thought. The problem now is that the input number can be either negative or positive. Thus there is a total of 8 different cases.
For the additional cases
First
postive + positive
Second
Negative + positive
Third
Positive + Negative
Fourth
Negative + Negative
For the subtraction cases
First
Positive - Positive
Second
Postive - Negative = Positive + Positive
Third
Negative - Postive = Negative + Negative
Fourth
Negative - Negative = Negative + Positive

I am suppose to use class to solve this problem. I have a feeling that it will help me to reduce the amount of coding that I have to do. But i am having problem linking it up together into a code. Any suggestions how i can make it shorter and run faster instead of doing a switch of 8 different cases ? One section for marking is the efficiency of the program.

Thanks a million !

[adnan.siddique]

no you do not have 8 cases. look

5 - 3
and
-3 + 5
also
-3 - (-5) = -3 + 5
are all same cases.

similarly many others

[Agni]

Another approach could be:

1. Read in a number as a string
2. Take one character from the front, convert it into a number and push it in a stack - Stack-1
3. Keep doing step 2 till you've pushed the entire string on the stack with the least significant bit at the top of the stack
4. Then do the same for the 2nd string - Stack-2
5. Then pop first element from both the stacks and add them and keep the result in another stack, Stack-3 and store the carry in a temporary
6. Pop the second elements from the stacks add them, and the previous carry, push the result on the Stack-3 and so on
7. Once you've done with one stack push the elements of the next stack, check for carries and add them if you have to and push the result on to Stack-3
8. Pop out Stack-3 to show result.

I have not thought over this completely, you can do a quick analysis to see if it fits your requirement. You could use a class to encapsulate all this stack handling and provide the user with just an add function. And there is a predefined std::stack class available which you can use.

[adnan.siddique]

Another approach could be:
2. Take one character from the front

that is wrong. by start pushing from the front. because
if we do

345
+ 123

then we will add by starting 5 + 3 means from the end of two strings. and not by adding 3 + 1 from the start. if you push both the strings in a stack and then add by popping them then that will b wrong

2 solutions to this problem are

1) use a queue instead of a stack
2) start pushing in the stack from the start of the string

[Lerner]

You could do the arithmetic in "two" steps:

1) Determine the sign of the result:
   A) Addition
      a) if operands have same sign, then result has the same sign as the operands
      b) if operands have different signs, then result has sign of the operand with the largest absolute value
   B) Subtraction
      a) Flip the sign of the operand being subtracted (the one after the minus sign) and then use the same rules as addition

2) Do the addition or subtraction of the absolute values of the operands disregarding the sign of the operands.

The relative absolute values of two operands in this system can be determined by comparing the unsigned string representation of the operands and number of digits of the operands:

1) the operand with the largest number of digits has the highest absolute value
2) if the operands have the same number of digits:
    a) then the operand with the "largest string value" has the larger absolute value since the most commonly used char sets have the digits in sequential order from 0-9.  
    b) if the unsigned strings are equal then the absolute values are equal

I see nothing wrong with using arrays to do the problem. Padding the arrays with leading zeros when desired is perfectly valid as well. All the suggestions provided are just that, options you could use if you feel comfortable doing so.

[Agni]

>>that is wrong. by start pushing from the front
2) start pushing in the stack from the start of the string

What is the difference between the 2 statements?

[adnan.siddique]

from the start means from the index 0. and from the front means from the end of the string. sorry if i got you wrong. but thats what i understand.

[dusktreader]

I wrote a class that functions correctly. However, I assume this is homework, so I won't give you the solution code. I will describe a good solution to the problem for you, though.

First, I don't really see a reason to use strings for your storage. You might use chars, but you would only be saving a little space over using ints. I used an int array. The trick here is your implementation of the addition operation. Here's some pseudo code for the solution method I used.:

1.  initialize temporary variables a, b, i, s, r, and sign
2.  Determine which operand is greater, call this operand A, the other B
3.  Set sign = sign(A) * sign(B)   #By sign, I mean +1 or -1
      Set r = 0  #r will be used for the carry/borrow
4.  Set i = 0 to start at the right-most digit ( the one's place)
5.  Set a = A[i],  b = B[i] iff i > length(B)  else b = 0  # If B has run out of digits, set b to 0
6.  Set s = a + b + r
7.  If this is the last digit of A
          If s is negative, put positive s into the ith place of the result
          Else if s is larger than 9, put s - 10 into the ith place and 1 into  i+1 place of the result
          else, just put i into the ith place
          Go to 10
8.  Else
          If s is negative,  set r = -1, s = s + 10
          Else if s > 9,  set r = 1, s = s -10
          Else,  set r=0
          put s into the ith place of the result
9.  Increment i and go to 5
10.  Set the sign of the result to the sign of A, and you're done

This method nicely unifies addition and subraction and handles all of the different cases of signs of the operands.

Good luck!

[problemkid]

Yeah no problem. I understood the part.

Using stack to push and pop seems like a great idea, but i am suppose to write this using classes.

The major difficulty i am facing now is that the actual operation of the program.

Being string there is no negative number so how am i going to do the maths calculation.

for eg:
100 - 9000 = -8900.

Because if the first input is always bigger than the 2nd input it would be much simpler.

Any body have any idea on that?

[problemkid]

I wrote a class that functions correctly. However, I assume this is homework, so I won't give you the solution code. I will describe a good solution to the problem for you, though.

First, I don't really see a reason to use strings for your storage. You might use chars, but you would only be saving a little space over using ints. I used an int array. The trick here is your implementation of the addition operation. Here's some pseudo code for the solution method I used.:

Hi, the situation is that i intially thought i would be able to convert the string into a int array and that would make the maths calculate much easier. But my program must be able to add or subtract numbers up to 10^100. I cant use an array that size right?

one of the test case i must pass is
423422349999963634599999
-99999999999234997771231

[Lerner]

Containers can have as much memory as your computer has available. Each int requires four bytes of memory, minimum, whereas each char typically takes 1 byte of memory. Therefore, typically, it takes 4 times as much memory to store an int as it does to store a char. Each compiler is free to require more memory than the minimum established in the language standard, so the exact memory profile may be different with different compilers. In general, though, you can store more char than int in any given memory block.

Here's one class outline you could use, showing data members only:

inputString

and here's another:

inputString
sign
unsignedString
numDigits

Both class options above would have a variety of constructors, a destructor, a copy operator, an assignment operator, overloaded math operators (+, -, == and >), an overloaded << operator and probably some private helper functions. In the first option above the desired information can be gleaned from inputString as needed. In the second version the indicated data members can be done obtained from the input string within the constructor.

[dusktreader]

Containers can have as much memory as your computer has available. Each int requires four bytes of memory, minimum, whereas each char typically takes 1 byte of memory. Therefore, typically, it takes 4 times as much memory to store an int as it does to store a char. Each compiler is free to require more memory than the minimum established in the language standard, so the exact memory profile may be different with different compilers. In general, though, you can store more char than int in any given memory block.

This is true. If you think you might run out of memory, use chars instead. You should also note that chars can be signed just like an integer because they are actually an integer type with less bit depth! If you treat the chars exactly like you would an integer, all of the arithmetic will work the same so, for example:

char a = 7;
   char b = -9;
   char c = a + b;
   cout << c << endl;    // Weird output
   cout << (int)c << endl;   // Expected output

Try this out, and you'll see it works. When you printed c directly, it displayed some weird character, because printing a char uses the char's value to look up a symbol in the ascii table. We can be sure that looking up -2 in the ascii table is going to fetch a wierd symbol. However, since c instead holds an integer value, you simply cast it to an integer to print value it holds. The thing that you will need to be careful with is initializing your SuperLongInteger type with a string:

SuperLongInt( cosnt String& inputStr );

This constructor should extract the character numerical value out of each element of the string. A really easy way to do this is:

char input;
    char output;
    string inputStr = "2687431";
    char input = inputStr[3];  // Now input is a literal char that is '7'
    char output = input - '0';  // Now output should have the value 7
    cout << (int)output << endl;

This will work because the ascii table holds the values for the numbers in adjacent increasing slots. So, the ascii table would look something like this:

n   n+1  n+2  ...  n+9
-----------------------
'0'  '1'  '2'  ...  '9'

Where n is some unimportant lookup value. The important thing is that the lookup value for , say, '8' is always going to be 8 greater than the lookup value for '0'. So, we can convert any ascii number to an integer easily using the above method.

I ran your test case with my code, and my results were correct:

int main(int argc, char *argv[]){
    SuperLongInt l( "423422349999963634599999" );
    SuperLongInt m( "-99999999999234997771231" );

    cout << l << endl;
    cout << m << endl;
    cout << l+m << endl;
    return 0;
}

$> main
423422349999963634599999
-99999999999234997771231
323422350000728636828768