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   // Check some sign conditions
  35   // (-b1 + b2) <=> (b2 - (+b2))
  36   if (b1.Sign == Negative && b2.Sign == Positive) {
  37         b1.Sign = Positive;
  38         return diffBigInt(b2, b1);
  39   }
  40   // (b1 + (-b2)) <=> (b1 - (+b2))
  41   if (b1.Sign == Positive && b2.Sign == Negative) {
  42         b2.Sign = Positive;
  43         return diffBigInt(b1, b2);
  44   }
  45
  46   BigInteger result = CreateZeroBigInt();
  47
  48   if (b1.Sign == Negative && b2.Sign == Negative)
  49         result.Sign = Negative;
  50   else
  51         result.Sign = Positive;
  52
  53   BigUnsignedInteger* node1 = b1.AbsValStart;
  54   BigUnsignedInteger* node2 = b2.AbsValStart;
  55
  56   // NULL case
  57   if (node1 == NULL)
  58         return b2;
  59   if (node2 == NULL)
  60         return b1;
  61
  62   unsigned int carry = 0;
  63   Boolean cont = false;
  64
  65   do {
  66         cont = false;
  67
  68         unsigned int newValue = (node1 == NULL ? 0 : node1->Value) + (node2 == NULL ? 0 : node2->Value) + carry;
  69
  70         carry = newValue / BASE;
  71         newValue = newValue % BASE;
  72         PushEndNode(&result, newValue);
  73
  74         if (node1 != NULL) {
  75           cont = (node1 = node1->Next) != NULL;
  76         }
  77         if (node2 != NULL) {
  78           node2 = node2->Next;
  79           cont = node2 != NULL || cont;
  80         }
  81
  82   } while(cont);
  83
  84   if (carry > 0)
  85         PushEndNode(&result, carry);
  86
  87   return result;
  88 }