biginteger_sumBigInt.c

   1 /* Copyright (c) 2008 Jérémie Laval, Marine Jourdain
   2
   3  * Permission is hereby granted, free of charge, to any person obtaining a copy
   4  * of this software and associated documentation files (the "Software"), to deal
   5  * in the Software without restriction, including without limitation the rights
   6  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7  * copies of the Software, and to permit persons to whom the Software is
   8  * furnished to do so, subject to the following conditions:
   9
  10  * The above copyright notice and this permission notice shall be included in
  11  * all copies or substantial portions of the Software.
  12
  13  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  19  * THE SOFTWARE.
  20  *
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <math.h>
  26 #include <string.h>
  27
  28 #include "biginteger.h"
  29 #include "biginteger_utils.h"
  30
  31
  32 BigInteger sumBigInt(BigInteger b1, BigInteger b2)
  33 {
  34   //test if b2 is negative
  35   if(b1.Sign==Positive && b2.Sign==Negative){
  36     b2.Sign=Positive;
  37     return diffBigInt(b1,b2);
  38   }else{
  39     //test if b1 is negative
  40     if(b1.Sign==Negative && b2.Sign==Positive){
  41       b1.Sign=Positive;
  42       return diffBigInt(b2,b1);
  43     }
  44   }
  45   //variable which will be the result of the sum
  46   BigInteger Sum = CreateZeroBigInt();
  47   //temporary pointer  over b1
  48   BigUnsignedInteger* p1 = b1.AbsValStart;
  49   //temporary pointer over b2
  50   BigUnsignedInteger* p2 = b2.AbsValStart;
  51   //test if the two BigInteger are null
  52
  53   if (b1.Sign == Undefined && b2.Sign == Undefined){
  54     return Sum;
  55   }else{
  56     //test if one of the 2 BigInt is null
  57     if (b1.Sign == Undefined && b2.Sign != Undefined)
  58       Sum = b2;
  59     else if (b2.Sign == Undefined && b1.Sign != Undefined)
  60         Sum = b1;
  61
  62   }
  63
  64   //test if the 2 BigInt are both positive or both negative
  65   int carry=0;
  66   //do the addition until we reach the last node of one of the two numbers, or both
  67   while(p1 != NULL || p2 != NULL){
  68     unsigned int s=(p1==NULL ? 0 : p1->Value) + (p2==NULL ? 0 : p2->Value) + carry;
  69     PushEndNode(&Sum, s%10000);
  70     //compute the carry
  71     if(s >= 10000)
  72       //if the sum exceed 10000
  73       carry=1;
  74     else
  75       carry=0;
  76
  77     if (p1 == NULL) {//test if p2 is longer than p1
  78       p2=p2->Next;
  79     }else if (p2==NULL) { //test if p1 is longer than p2
  80       p1=p1->Next;
  81     }
  82   }
  83   //test if it remain a carry after all the additions
  84   if(carry==1){
  85     PushEndNode(&Sum,1);
  86   }
  87   //if the two numbers are both negative
  88   if(b1.Sign == Negative && b2.Sign == Negative)
  89       Sum.Sign=Negative;
  90
  91   return Sum;
  92
  93 }