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
  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   if (u.Count == 1 && v.Count == 1) {
  46         unsigned int result =  u.AbsValStart->Value / v.AbsValStart->Value;
  47         PushFrontNode(&quotient, result);
  48         return quotient;
  49   }
  50
  51   // Base case
  52   //BigInteger rest = CreateZeroBigInt();
  53
  54   unsigned int divisor = BASE / (v.AbsValEnd->Value + 1);
  55   BigInteger uprime = mulBigIntByScalar(u.AbsValStart, divisor);
  56   if (uprime.Count == u.Count)
  57         PushFrontNode(&uprime, 0);
  58   BigInteger vprime = mulBigIntByScalar(v.AbsValStart, divisor);
  59
  60   unsigned int v1 = vprime.AbsValEnd->Value;
  61   unsigned int v2 = vprime.AbsValEnd->Previous->Value;
  62
  63   // Used to get sub-biginteger of uprime in the loop
  64   int j = 0;
  65   int m = u.Count - v.Count;
  66   int n = u.Count;
  67
  68   printf("Num node %d\n", uprime.Count);
  69
  70   BigUnsignedInteger* ujNode = uprime.AbsValEnd;
  71
  72   for (; j <= m; j++) {
  73         unsigned int q = BASE - 1;
  74         unsigned int uj = ujNode->Value;
  75
  76         if (uj != v1)
  77           // TODO: Verify that ->Previous->Value can't segfault
  78           q = (uj * BASE + ujNode->Previous->Value) / v1;
  79         puts("Chou-fleur");
  80
  81         // Overflow test
  82         while (v2 * q > (uj * BASE + ujNode->Previous->Value - q * v1) * BASE + ujNode->Previous->Previous->Value)
  83           q -= 1;
  84
  85         printf("Lapin %d\n", j);
  86
  87         BigInteger slice = CreateZeroBigInt();
  88         CopyBigIntegerFromEnd(u, &slice, ujNode, n);
  89         slice = diffBigInt(slice, mulBigIntByScalar(v.AbsValStart, q));
  90
  91         ujNode = ReplaceFromEnd(&uprime, slice, ujNode->Next, n);
  92
  93         PushFrontNode(&quotient, q);
  94
  95         puts("Carotte");
  96   }
  97
  98   return quotient;
  99 }