biginteger_mulBigInt.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 // Uses Karatsuba algorithm
  33 BigInteger mulBigInt(BigInteger x, BigInteger y)
  34 {
  35   if (x.Sign == 0 || y.Sign == 0)
  36         return CreateZeroBigInt();
  37
  38   // If we have a biginteger with one node no point in further splitting
  39   /* We do an operation like (in base 10) :
  40    *       abcd
  41    *       x  e
  42    *       ----
  43    * a*e*10^3 + b*e*10^2 + c*e*10 + d*e
  44    *
  45    */
  46   if (MIN(x.Count, y.Count) == 1) {
  47         BigUnsignedInteger* big = (x.Count == 1) ? y.AbsValStart : x.AbsValStart;
  48         unsigned int multiplier = (x.Count == 1) ? x.AbsValStart->Value : y.AbsValStart->Value;
  49
  50         BigInteger temp = mulBigIntByScalar(big, multiplier);
  51         temp.Sign = x.Sign * y.Sign;
  52
  53         return temp;
  54   }
  55
  56   BigInteger x0 = CreateZeroBigInt();
  57   BigInteger x1 = CreateZeroBigInt();
  58
  59   BigInteger y0 = CreateZeroBigInt();
  60   BigInteger y1 = CreateZeroBigInt();
  61
  62   int N = MAX(x.Count, y.Count);
  63   SplitBigInteger(N, x, &x1, &x0);
  64   SplitBigInteger(N, y, &y1, &y0);
  65
  66   /* a = x1*y1
  67    * b = x0*y0
  68    * c = (x1 - x0)(y1 - y0)
  69    */
  70   BigInteger a = mulBigInt(x1, y1);
  71   BigInteger b = mulBigInt(x0, y0);
  72   BigInteger c = mulBigInt(diffBigInt(x1, x0), diffBigInt(y1, y0));
  73   BigInteger abc = sumBigInt(a, b);
  74   abc = diffBigInt(abc, c);
  75
  76   int k = (N % 2) == 0 ? N/2 : N/2 + 1;
  77   MultiplyByBase(&a, 2*k);
  78   MultiplyByBase(&abc, k);
  79
  80   BigInteger result = sumBigInt(sumBigInt(a, abc), b);
  81   // Remove leading 0s if any
  82   Clean(&result);
  83   result.Sign = x.Sign * y.Sign;
  84
  85   return result;
  86 }