Thread: big integer calculator! addition/subtraction algorithm

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    5

    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

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    230
    why don't you use the standard functions for converting a string to an int?

    Sorry if this is totally wrong.

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    5
    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

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
                       result[k]=result[k];
    Does absolutely nothing!

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Nov 2007
    Posts
    5
    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...

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Just the same way you'd do it "by hand", multiplying and "shifting" the digits as needed.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Nov 2007
    Posts
    5
    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;
                        }

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    Registered User
    Join Date
    Nov 2007
    Posts
    5
    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...

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Replies: 5
    Last Post: 04-12-2006, 06:30 PM
  4. Big and little endian
    By Cactus_Hugger in forum C Programming
    Replies: 4
    Last Post: 10-12-2005, 07:07 PM
  5. newbie programmer - needs help bad.
    By hortonheat in forum C Programming
    Replies: 17
    Last Post: 10-20-2004, 05:31 PM