biginteger_diffBigInt.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 diffBigInt(BigInteger b1, BigInteger b2)
  33 {
  34   // Sign cases
  35   // -b1 - (+b2) <=> -(b1 + b2)
  36   if (b1.Sign == Negative && b2.Sign == Positive) {
  37         b2.Sign = Negative;
  38         return sumBigInt(b1, b2);
  39   }
  40
  41   // b1 - (-b2) <=> b1 + b2
  42   if (b1.Sign == Positive && b2.Sign == Negative) {
  43         b2.Sign = Positive;
  44         return sumBigInt(b1, b2);
  45   }
  46
  47   BigInteger result = CreateZeroBigInt();
  48
  49   BigUnsignedInteger* node1 = b1.AbsValStart;
  50   BigUnsignedInteger* node2 = b2.AbsValStart;
  51
  52   // NULL case
  53   if (node2 == NULL)
  54         return b1;
  55   if (node1 == NULL) {
  56         b2.Sign = b2.Sign == Positive ? Negative : Positive;
  57         return b2;
  58   }
  59
  60   int comp = compareBigInt(b1, b2);
  61   if (comp == 0) {
  62         return result;
  63   } else if (comp > 0) {
  64         result.Sign = Positive;
  65   } else {
  66         // Some magic swapping
  67         result.Sign = Negative;
  68         BigUnsignedInteger* temp = node1;
  69         node1 = node2;
  70         node2 = temp;
  71   }
  72
  73   // Takes back the pointer value as there might have been swapping
  74   // TODO : see if we can exchange directly these pointer in the if rather than b1/b2
  75   /*node1 = b1.AbsValStart;
  76   node2 = b2.AbsValStart;
  77   */
  78
  79   unsigned int carry = 0;
  80   Boolean cont = false;
  81
  82   do {
  83         cont = false;
  84
  85         unsigned int newValue = 0;
  86         if (node1 != NULL && node2 != NULL) {
  87           if (node2->Value > node1->Value) {
  88                 // Do a little trick to get positive coefficient
  89                 // and backport the changement on the upper coefficient with carry
  90                 newValue = (BASE + node1->Value) - node2->Value - carry;
  91                 carry = 1;
  92           } else {
  93                 newValue = node1->Value - node2->Value - carry;
  94                 carry = 0;
  95           }
  96         } else {
  97           // Due to our hypothethis at start of the function (test, swapping and all)
  98           // we know that it's node2 which is NULL, then proceed with node1
  99           newValue = node1->Value - carry;
 100           carry = 0;
 101           // No need for unnecessary 0 in the list
 102           if (newValue == 0)
 103                 break;
 104         }
 105
 106         PushEndNode(&result, newValue);
 107
 108         if (node1 != NULL) {
 109           cont = (node1 = node1->Next) != NULL;
 110         }
 111         if (node2 != NULL) {
 112           node2 = node2->Next;
 113           cont = node2 != NULL || cont;
 114         }
 115
 116   } while(cont);
 117
 118   return result;
 119 }