big integer calculator! addition/subtraction algorithm

hello! I have tried to do a big integer calculator. as you can see from my code, I'm not an expert... (this is made to unix).
I've made so far addition algorithm and it works fine for positive integers BUT how to implement subtraction algorithm?

I take the numbers from console as strings and handle them as strings as well until the calculations are done with integer values and stored to integer type array.

I didn't want to put the whole source code here, but here is the function which makes addition. Before this function is called, the strings (numbers) are reversed vice versa. Is this algorithm insane? How can I handle negative numbers as well and how to make subtraction algorithm.

insert

Code:

void add(int argc,char *argv[]){


int c1=0,c2=0,c3=0,i=0,ii=0,k=0,carry=0;
unsigned int result[1000],luku1[1000],luku2[1000];

c1=strlen(argv[1]);
c2=strlen(argv[2]);

//check which number is longer
if(c1<c2){
          c3=c2;
          }
else if(c1>c2){
     c3=c1;
     }
else{
     c3=c1;
     }

//store strings to int tables as ints
for(i=0;i<c1;i++){
                  luku1[i]=argv[1][i]-48;
                  }

for(ii=0;ii<c2;ii++){
                     luku2[ii]=argv[2][ii]-48;
                     }


//addition algorithm
for(k=0;k<=c3;k++){
                   result[k]=luku1[k]+luku2[k]+carry;
                        
                   if(result[k]>=10){
                                     result[k]=result[k]-10;
                                     carry=1;
                                     }//if
                   else{
                   result[k]=result[k];
                   carry=0;
                   }//else

}//for


//if the last addition result was <10, don't print 0
if(result[c3]==0){
                  c3=c3-1;
                  }

//result
for(k=c3;k>=0;k--){
                   printf("%d",result[k]);
                   }
printf("\n");


}//add

Code:

void add(int argc,char *argv[]){

"interesting" argument passing convention.

Code:

if(c1<c2){
          c3=c2;
          }
else if(c1>c2){
     c3=c1;
     }
else{
     c3=c1;
     }

Surely you only need one check?

Code:

c3 = c1;
if (c2 > c1) c3 = c2;

or

Code:

c3 = (c2 > c1)?c2:c1;

You need to make sure that luku1 and luku2 are zero-filed all the way to c3 - otherwise they contain "random" stuff. And you add all the way to c3.

You probably also should check in this function that c3+1 is less or equal to 1000 - since that's the size of your variables, and if you go beyond that, bad things will happen.

--
Mats

> BUT how to implement subtraction algorithm?
When you do 'add', and overflow, you generate a carry.
So when you do 'sub' and underflow, you generate a borrow.

> Before this function is called, the strings (numbers) are reversed vice versa. Is this algorithm insane?
There's always going to be a certain amount of it (unless you complicate the code) since the numbers are displayed from most significant to least significant order (tens first, then units), whereas the calculations usually run units first, then tens.

why don't you use the standard functions for converting a string to an int?

Sorry if this is totally wrong.

Thanks for replies. As I told you, I'm not expert that's why there are several not-so-nice stuff in the code. As for my original question, I solved the subtraction algorithm the way Salem said. Snippet of a code is under...

BUT, of course I want to calculate multiplication and division too... Is it much more complicated? I should I proceed? Thank you for your replies!

And to Abda92: It's not possible, because the numbers used are bigger than you can convert...


insert

Code:

for(k=0;k<=c3;k++){
                   result[k]=luku1[k]-luku2[k]-borrow;
                        
                   if(luku1[k]<luku2[k]){
                                     result[k]=result[k]+10;
                                     borrow=1;
                                     }//if
                   else{
                   result[k]=result[k];
                   borrow=0;
                   }//else

}//for

Code:

                   result[k]=result[k];

Does absolutely nothing!

--
Mats

Multiplication and division aren't too hard if your big integer library works in binary.
However, since you're using base 10, you may want to write multiplication first though. Also, in this case you can implement it exactly the same as you do long multiplication or long division on paper.

I suggest changing the magic number of 48 to '0' instead which is a little more readable.

Note that the technique you are using is very fast when it comes to printing the value out (reverse the string), but very slow and very memory hungry when it comes to everything else. If you want to see how to implement the whole thing in binary exactly as if it were an __int1024 for example, then you can find such code on my website.

Yes yes. At first let's assume that I want to use 10-base as I've been using earlier. How I implement this multiplication+addition of carries?? Sorry, but I'm a bit lost with this...

Just the same way you'd do it "by hand", multiplying and "shifting" the digits as needed.

--
Mats

Hi! I came up with a solution like this... But I then I noticed that my addition doesn't handle negative numbers at all! How this can be done? 10:s complement or what?

insert

Code:

for(k=0;k<2*c3;k++){
for(kk=0;kk<2*c3;kk++){
                       result[k+kk]=result[k+kk]+luku1[k]*luku2[kk];
                       }
}

for(i=0;i<2*c3;i++){
                    result[i]=result[i]+carry;
                    
                    if(result[i]<0){
                                    carry=-(-(result[i]+1)/10+1);
                                    }
                    else{
                         carry=result[i]/10;
                         }
                    result[i]=result[i]-carry*10;
                    }

Negative numbers, you can deal with by taking the sign of each component, multiply the two signs together, and set the sign to that at the end. Remeber -5 * 7 == -(5 * 7) == -35.

Of course, negative add/subtract will require some checking of sign and if the sign is different, you need to call the opposite subtract/add with the opposite sign [and perhaps also swapping the arguments around].

--
Mats

Yeah, Thanks. Now I have succeeded with addition/subtraction and multiplication. Division I can do with subtraction, right? And like you guys pointed out before, it's not very nice to have constant size tables reserved for numbers/answer. So what should I do to reserve space only that much, what is needed for calculations? malloc? How to use it? Thanks in advance...

Divide can be done with subtraction, but dividing 212138348921312389127489123891279 by 3 would take quite some subtrctions... [particularly considering your subtractions are pretty slow - not saying you can easily speed them up, just that they take a whole lot more than one CPU clockcycle each]. Perhaps you can "shuffle" your divisor until it's almost the size of the number, and then start from there.

--
Mats