biginteger.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
  30 // Private Function Impl
  31
  32 #define ATOUI(str) ((unsigned int)strtoul(buffer, NULL, 10))
  33 #define MIN(x, y) (x < y ? x : y)
  34 #define MAX(x, y) (x > y ? x : y)
  35
  36 BigInteger CreateZeroBigInt()
  37 {
  38   BigInteger temp;
  39   temp.Sign = Undefined;
  40   temp.AbsValStart = NULL;
  41   temp.AbsValEnd = NULL;
  42   temp.Count = 0;
  43
  44   return temp;
  45 }
  46
  47 BigUnsignedInteger* InitBUint(unsigned int value)
  48 {
  49   BigUnsignedInteger* bigUint = malloc(sizeof(BigUnsignedInteger));
  50   bigUint->Value = value;
  51
  52   return bigUint;
  53 }
  54
  55 BigUnsignedInteger* CopyBigInteger(BigInteger source, BigInteger* dest, BigUnsignedInteger* start, int count)
  56 {
  57   BigUnsignedInteger* node = (start == NULL) ? source.AbsValStart : start;
  58
  59   do {
  60         PushEndNode(dest, node->Value);
  61         if (--count == 0)
  62           break;
  63   } while ((node = node->Next) != NULL);
  64
  65   return node;
  66 }
  67
  68 // base = part1 * 10000^N  + part2
  69 void SplitBigInteger(int N, BigInteger base, BigInteger* part1, BigInteger* part2)
  70 {
  71   // In case N is odd part2 has a 1 more node than part1
  72   int count = (N % 2) == 0 ? N/2 : N/2 + 1;
  73
  74   if (base.Count <= count) {
  75         // Only set part2, part1 == 0
  76         /*part2->AbsValStart = base.AbsValStart;
  77         part2->AbsValEnd = base.AbsValEnd;
  78         part2->Count = base.Count;*/
  79         CopyBigInteger(base, part2, NULL, -1);
  80         part2->Sign = Positive;
  81         return;
  82   }
  83
  84   BigUnsignedInteger* node = CopyBigInteger(base, part2, NULL, count);
  85   part2->Sign = Positive;
  86
  87   CopyBigInteger(base, part1, node->Next, -1);
  88   part1->Sign = Positive;
  89
  90 }
  91
  92 void MultiplyByBase(BigInteger* b, int k)
  93 {
  94   int i = 0;
  95   for (; i < k; i++)
  96         PushFrontNode(b, 0);
  97 }
  98
  99 void PrependNode(BigUnsignedInteger* b1, BigUnsignedInteger* b2)
 100 {
 101   b1->Next = b2;
 102   b2->Previous = b1;
 103 }
 104
 105 // Used to push_front a value
 106 void PushFrontNode(BigInteger* bigInt, unsigned int value)
 107 {
 108   BigUnsignedInteger* bigUint = InitBUint(value);
 109
 110   // Do the magic swapping
 111   if (bigInt->AbsValStart != NULL)
 112         PrependNode(bigUint, bigInt->AbsValStart);
 113   // Update BigInt's head field
 114   bigInt->AbsValStart = bigUint;
 115
 116   // If it's the first node added, correctly set bigInt->AbsValEnd
 117   if (bigInt->AbsValEnd == NULL)
 118         bigInt->AbsValEnd = bigUint;
 119
 120   bigInt->Count++;
 121 }
 122
 123 void PushEndNode(BigInteger* bigInt, unsigned int value)
 124 {
 125   BigUnsignedInteger* buint = InitBUint(value);
 126
 127   // Do the magic swapping
 128   if (bigInt->AbsValEnd != NULL)
 129         PrependNode(bigInt->AbsValEnd, buint);
 130   // Update BigInt's head field
 131   bigInt->AbsValEnd = buint;
 132
 133   // If it's the first node added, correctly set bigInt->AbsValStart
 134   if (bigInt->AbsValStart == NULL)
 135         bigInt->AbsValStart = buint;
 136
 137   bigInt->Count++;
 138 }
 139
 140 // Used to insert a node in the *middle* of the BigInt.
 141 // It Do *not* check if we reproduce Push(Front|End)Node behavior
 142 // Use Push(Front|End)Node if you intend to do what these functions are meant for
 143 void InsertNode(BigInteger* bigInt, BigUnsignedInteger* next, unsigned int value)
 144 {
 145   BigUnsignedInteger* buint = InitBUint(value);
 146   BigUnsignedInteger* temp  = next->Previous;
 147
 148   PrependNode(buint, next);
 149   PrependNode(temp, buint);
 150
 151   bigInt->Count++;
 152 }
 153
 154 // End Private Function Impl
 155
 156
 157
 158 // Public Function Impl
 159
 160 BigInteger newBigInteger(char* desc)
 161 {
 162   int        sLength         = strlen(desc);
 163   BigInteger temp            = CreateZeroBigInt();
 164   int        startIndex = 0;
 165
 166   if (sLength == 0)
 167         return temp;
 168
 169   temp.Sign = Positive;
 170
 171   if (desc[0] == '-' || desc[0] == '+') {
 172         if (desc[0] == '-')
 173           temp.Sign = Negative;
 174         startIndex = 1;
 175   }
 176
 177   char buffer[5];
 178   memset(buffer, '\0', 5);
 179   int i;
 180
 181   for (i = sLength - 4;  i >= startIndex; i -= 4) {
 182         strncpy(buffer, desc + i, 4);
 183         PushEndNode(&temp, ATOUI(buffer));
 184         // Erase the buffer
 185         memset(buffer, '\0', 5);
 186   }
 187   // In case the MSB digits are not packable by four do the fiddling manually
 188   if (sLength % 4 != 0) {
 189         strncpy(buffer, desc + startIndex, i + 4 - startIndex);
 190         PushEndNode(&temp, ATOUI(buffer));
 191   }
 192
 193   return temp;
 194 }
 195
 196 void printBigInteger(BigInteger bint)
 197 {
 198   BigUnsignedInteger* node = bint.AbsValEnd;
 199   if (node == NULL) {
 200         puts("0");
 201         return;
 202   }
 203
 204   if (bint.Sign == Negative)
 205         printf("%c", '-');
 206
 207   do {
 208         if (node != bint.AbsValEnd)
 209           printf("%04u", node->Value);
 210         else
 211           printf("%u", node->Value);
 212   } while((node = node->Previous) != NULL);
 213
 214   printf("\n");
 215 }
 216
 217 Boolean isNull(BigInteger bint)
 218 {
 219   return bint.AbsValEnd == NULL ? true : false;
 220 }
 221
 222 int signBigInt(BigInteger bint)
 223 {
 224   return (int)bint.Sign;
 225 }
 226
 227 Boolean equalsBigInt(BigInteger b1, BigInteger b2)
 228 {
 229   return compareBigInt(b1, b2) == 0 ? true : false;
 230 }
 231
 232 /* b1 > b2 => 1
 233  * b1 < b2 => -1
 234  * b1 == b2 => 0
 235  */
 236 int compareBigInt(BigInteger b1, BigInteger b2)
 237 {
 238   // try to short-circuit
 239   if (b1.Count < b2.Count)
 240         return -1;
 241
 242   if (b1.Count > b2.Count)
 243         return 1;
 244
 245   // Normal processing
 246   BigUnsignedInteger* node1 = b1.AbsValEnd;
 247   BigUnsignedInteger* node2 = b2.AbsValEnd;
 248
 249   // Test for NULL special case
 250   if (node1 == NULL && node2 == NULL)
 251         return 0;
 252
 253   if (b1.Sign != b2.Sign) {
 254         return b1.Sign == Negative ? -1 : 1;
 255   }
 256
 257   do {
 258         if (node1->Value < node2->Value)
 259           return -1;
 260         if (node1->Value > node2->Value)
 261           return 1;
 262   } while ((node1 = node1->Previous) != NULL && (node2 = node2->Previous) != NULL);
 263
 264   return 0;
 265 }
 266
 267 BigInteger sumBigInt(BigInteger b1, BigInteger b2)
 268 {
 269   // Check some sign conditions
 270   // (-b1 + b2) <=> (b2 - (+b2))
 271   if (b1.Sign == Negative && b2.Sign == Positive) {
 272         b1.Sign = Positive;
 273         return diffBigInt(b2, b1);
 274   }
 275   // (b1 + (-b2)) <=> (b1 - (+b2))
 276   if (b1.Sign == Positive && b2.Sign == Negative) {
 277         b2.Sign = Positive;
 278         return diffBigInt(b1, b2);
 279   }
 280
 281   BigInteger result = CreateZeroBigInt();
 282
 283   if (b1.Sign == Negative && b2.Sign == Negative)
 284         result.Sign = Negative;
 285   else
 286         result.Sign = Positive;
 287
 288   BigUnsignedInteger* node1 = b1.AbsValStart;
 289   BigUnsignedInteger* node2 = b2.AbsValStart;
 290
 291   // NULL case
 292   if (node1 == NULL)
 293         return b2;
 294   if (node2 == NULL)
 295         return b1;
 296
 297   unsigned int carry = 0;
 298   Boolean cont = false;
 299
 300   do {
 301         cont = false;
 302
 303         unsigned int newValue = (node1 == NULL ? 0 : node1->Value) + (node2 == NULL ? 0 : node2->Value) + carry;
 304
 305         carry = newValue / BASE;
 306         newValue = newValue % BASE;
 307         PushEndNode(&result, newValue);
 308
 309         if (node1 != NULL) {
 310           cont = (node1 = node1->Next) != NULL;
 311         }
 312         if (node2 != NULL) {
 313           node2 = node2->Next;
 314           cont = node2 != NULL || cont;
 315         }
 316
 317         if (!cont && carry > 0)
 318           PushEndNode(&result, carry);
 319   } while(cont);
 320
 321   return result;
 322 }
 323
 324 BigInteger diffBigInt(BigInteger b1, BigInteger b2)
 325 {
 326   // Sign cases
 327   // -b1 - (+b2) <=> -(b1 + b2)
 328   if (b1.Sign == Negative && b2.Sign == Positive) {
 329         b2.Sign = Negative;
 330         return sumBigInt(b1, b2);
 331   }
 332
 333   // b1 - (-b2) <=> b1 + b2
 334   if (b1.Sign == Positive && b2.Sign == Negative) {
 335         b2.Sign = Positive;
 336         return sumBigInt(b1, b2);
 337   }
 338
 339   BigInteger result = CreateZeroBigInt();
 340
 341   BigUnsignedInteger* node1 = b1.AbsValStart;
 342   BigUnsignedInteger* node2 = b2.AbsValStart;
 343
 344   // NULL case
 345   if (node2 == NULL)
 346         return b1;
 347   if (node1 == NULL) {
 348         b2.Sign = b2.Sign == Positive ? Negative : Positive;
 349         return b2;
 350   }
 351
 352   int comp = compareBigInt(b1, b2);
 353   if (comp == 0) {
 354         return result;
 355   } else if (comp > 0) {
 356         result.Sign = Positive;
 357   } else {
 358         // Some magic swapping
 359         result.Sign = Negative;
 360         BigUnsignedInteger* temp = node1;
 361         node1 = node2;
 362         node2 = temp;
 363   }
 364
 365   // Takes back the pointer value as there might have been swapping
 366   // TODO : see if we can exchange directly these pointer in the if rather than b1/b2
 367   /*node1 = b1.AbsValStart;
 368   node2 = b2.AbsValStart;
 369   */
 370
 371   unsigned int carry = 0;
 372   Boolean cont = false;
 373
 374   do {
 375         cont = false;
 376
 377         unsigned int newValue = 0;
 378         if (node1 != NULL && node2 != NULL) {
 379           if (node2->Value > node1->Value) {
 380                 // Do a little trick to get positive coefficient
 381                 // and backport the changement on the upper coefficient with carry
 382                 newValue = (BASE + node1->Value) - node2->Value - carry;
 383                 carry = 1;
 384           } else {
 385                 newValue = node1->Value - node2->Value - carry;
 386                 carry = 0;
 387           }
 388         } else {
 389           // Due to our hypothethis at start of the function (test, swapping and all)
 390           // we know that it's node2 which is NULL, then proceed with node1
 391           newValue = node1->Value - carry;
 392           carry = 0;
 393           // No need for unnecessary 0 in the list
 394           if (newValue == 0)
 395                 break;
 396         }
 397
 398         PushEndNode(&result, newValue);
 399
 400         if (node1 != NULL) {
 401           cont = (node1 = node1->Next) != NULL;
 402         }
 403         if (node2 != NULL) {
 404           node2 = node2->Next;
 405           cont = node2 != NULL || cont;
 406         }
 407
 408   } while(cont);
 409
 410   return result;
 411 }
 412
 413 // Uses Karatsuba algorithm
 414 BigInteger mulBigInt(BigInteger x, BigInteger y)
 415 {
 416   if (x.Sign == 0 || y.Sign == 0)
 417         return CreateZeroBigInt();
 418
 419   if (MAX(x.Count, y.Count) == 1) {
 420         BigInteger temp = CreateZeroBigInt();
 421         temp.Sign = Positive;
 422
 423         unsigned int result = x.AbsValStart->Value * y.AbsValStart->Value;
 424         if (result / BASE != 0)
 425           PushFrontNode(&temp, result / BASE);
 426         PushFrontNode(&temp, result % BASE);
 427         return temp;
 428   }
 429
 430   BigInteger x0 = CreateZeroBigInt();
 431   BigInteger x1 = CreateZeroBigInt();
 432
 433   BigInteger y0 = CreateZeroBigInt();
 434   BigInteger y1 = CreateZeroBigInt();
 435
 436   int N = MAX(x.Count, y.Count);
 437   SplitBigInteger(N, x, &x1, &x0);
 438   SplitBigInteger(N, y, &y1, &y0);
 439
 440   /* a = x1*y1
 441    * b = x0*y0
 442    * c = (x1 - x0)(y1 - y0)
 443    */
 444   BigInteger a = mulBigInt(x1, y1);
 445   BigInteger b = mulBigInt(x0, y0);
 446   BigInteger c = mulBigInt(diffBigInt(x1, x0), diffBigInt(y1, y0));
 447   BigInteger abc = sumBigInt(a, b);
 448   abc = diffBigInt(abc, c);
 449
 450   int k = (N % 2) == 0 ? N/2 : N/2 + 1;
 451   MultiplyByBase(&a, 2*k);
 452   MultiplyByBase(&abc, k);
 453
 454   return sumBigInt(sumBigInt(a, abc), b);
 455 }
 456
 457 // Returns b^n
 458 BigInteger powBigInt(BigInteger b, int n)
 459 {
 460   BigInteger result = b;
 461
 462   while ((n & 0x1) == 0) {
 463         result = mulBigInt(result, result);
 464         n /= 2;
 465   }
 466   if (n != 1) {
 467         int i = n;
 468         for (; i >= 1; i--)
 469           result = mulBigInt(result, b);
 470   }
 471
 472   return result;
 473 }
 474
 475 // End Public Function Impl