biginteger_quotientBigInt.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 // Uses a version of Knuth LongDivision algorithm found in the Art of Computer Programming vol2
  32 BigInteger quotientBigInt(BigInteger u, BigInteger v)
  33 {
  34   // Special cases due to comparison
  35   int comparison = compareBigInt(u, v);
  36
  37   // Since we are only interested in integer number if
  38   // b is greater than a the result is automatically rounded to 0
  39   if (comparison <= 0)
  40         return comparison < 0 ? CreateZeroBigInt() : newBigInteger("1");
  41
  42   BigInteger quotient = CreateZeroBigInt();
  43   quotient.Sign = (Sign)(u.Sign * v.Sign);
  44
  45   // Special case of u.Count == 1 and v.Count == 1
  46   if (u.Count == 1 && v.Count == 1) {
  47         unsigned int result =  u.AbsValStart->Value / v.AbsValStart->Value;
  48         PushFrontNode(&quotient, result);
  49         return quotient;
  50   }
  51
  52   // Special case of u.Count > 1 and v.Count == 1
  53   if (v.Count == 1) {
  54         unsigned int r = 0;
  55         BigUnsignedInteger* unode = u.AbsValEnd;
  56         int j = 1;
  57
  58         for (; j <= u.Count; j++) {
  59           PushFrontNode(&quotient, (r * BASE + unode->Value) / v.AbsValEnd->Value);
  60           r = (r * BASE + unode->Value) % v.AbsValEnd->Value;
  61           unode = unode->Previous;
  62         }
  63         Clean(&quotient);
  64
  65         return quotient;
  66   }
  67
  68   // Base case
  69
  70   unsigned int divisor = BASE / (v.AbsValEnd->Value + 1);
  71
  72   BigInteger uprime = mulBigIntByScalar(u.AbsValStart, divisor);
  73   BigInteger vprime = mulBigIntByScalar(v.AbsValStart, divisor);
  74
  75   // Normalize uprime
  76   if (uprime.Count == u.Count)
  77         //if (divisor == 1)
  78         PushEndNode(&uprime, 0);
  79   // Normalize vprime (unecessary due to how d is computed)
  80   if (vprime.Count > v.Count)
  81         // It's only a supplementary node
  82         PopEndNode(&vprime);
  83
  84
  85   unsigned int v1 = vprime.AbsValEnd->Value;
  86   unsigned int v2 = vprime.AbsValEnd->Previous->Value;
  87
  88   // Used to get sub-biginteger of uprime in the loop
  89   int j = 0;
  90   int m = u.Count - v.Count;
  91   int n = v.Count;
  92
  93   BigUnsignedInteger* ujNode = uprime.AbsValEnd;
  94
  95   for (; j <= m; j++) {
  96         unsigned int q = BASE - 1;
  97         unsigned int uj = ujNode->Value;
  98
  99         if (uj != v1)
 100           q = (uj * BASE + ujNode->Previous->Value) / v1;
 101
 102         // Overflow test
 103         while (v2 * q > (uj * BASE + ujNode->Previous->Value - q * v1) * BASE + ujNode->Previous->Previous->Value)
 104           q -= 1;
 105
 106         BigInteger slice = CreateZeroBigInt();
 107         slice.Sign = Positive;
 108         CopyBigIntegerFromEnd(uprime, &slice, ujNode, n + 1);
 109
 110         BigInteger qv = mulBigIntByScalar(vprime.AbsValStart, q);
 111         slice = diffBigInt(slice, qv);
 112
 113         ujNode = ReplaceFromEnd(&uprime, slice, ujNode->Next, n);
 114
 115         PushFrontNode(&quotient, q);
 116   }
 117
 118   Clean(&quotient);
 119
 120   return quotient;
 121 }