bigmult.c

gistfile1.c

/* Perform efficient multiplication of big numbers
 * Julien Vehent July 2012
 * gcc -DDEBUG -Wall -o bigmult0.2 bigmult0.2.c
 */

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>

int main(int argc, char **argv){

   if(argc != 3){
      fprintf(stdout,"\n./bigmult <number A> <number B>\n");
      return 1;
   }

   char *big_a,*big_b;
   // store the two numbers to multiplicate, big_b is always the longest (or equal)
   if(strlen(argv[1]) > strlen(argv[2])){
      big_b = argv[1];
      big_a = argv[2];
   }
   else{
      big_a = argv[1];
      big_b = argv[2];
   }

   char *null;
   int big_b_ptr_ref, big_b_ptr, big_a_ptr_ref, big_a_ptr, inter_result;

   int big_b_len = strlen(big_b);
   int big_a_len = strlen(big_a);

   int carry = 0;

   char *result;
   result = malloc((big_b_len + big_a_len) * sizeof(char));
   int result_ptr = 0;

   #ifdef DEBUG
   int i;
   for(i=strlen(big_a)-1; i >= 0; i--)
      fprintf(stdout, "%c", *(big_a+i));
   fprintf(stdout,"\nperforming %s (l=%d) x %s (l=%d)\n",
         big_a, (int)big_a_len, big_b, (int)big_b_len);
   #endif
   /* linear convolution
    * multiply digits one by one
    * starting from the rightmost ones
    * example:
    *               1   2   3
    *           ×   4   5   6
    *            -------------
    *              6   12  18
    *          5   10  15
    *      4   8   12
    *        -----------------
    *      4   13  28  27   18
    *    4+1 13+3 28+2 27+1  8
    *      5   6   0    8    8
    */

   // loop over big_b digits from the right to the left
   for( big_b_ptr_ref = big_b_len -1 ; big_b_ptr_ref >= 0 ; big_b_ptr_ref--){
      inter_result = 0;
      big_b_ptr = big_b_ptr_ref;
      for(  big_a_ptr = (big_a_len - 1);
            big_b_ptr < big_b_len && big_a_ptr >= 0;
            big_b_ptr++){
         /* strtol will convert everything in memory until it finds a \0
         * so we need to make sure the variable passed to strtol contains only
         * the char we want, followed with a \0
         */
         char c[2];
         c[1] = '\0';
         int a,b;
         c[0] = big_a[big_a_ptr];
         a = strtol(c, &null, 10);
         c[0] = big_b[big_b_ptr];
         b = strtol(c, &null, 10);
         inter_result += ( a * b );
         #ifdef DEBUG
         fprintf(stdout,"\t%d*%d=%d", a, b, (a * b));
         #endif
         big_a_ptr-- ;
      }

      // add previous carry
      #ifdef DEBUG
      fprintf(stdout," [sum = %d+%d=%d;",
              inter_result, carry, inter_result + carry);
      #endif
      inter_result += carry;
      carry = inter_result / 10;
      inter_result %= 10;
      #ifdef DEBUG
      fprintf(stdout," keep = %d; carry = %d];",
              inter_result,carry);
      #endif
      char c[5];
      c[4] = '\0';
      snprintf(c, sizeof(int), "%d", inter_result);
      result[result_ptr] = *c;
      result_ptr++;
      #ifdef DEBUG
      fprintf(stdout,"result= %s\n", result);
      #endif
   }

   #ifdef DEBUG
   fprintf(stdout,"leftmost reached, finished first loop\n");
   #endif

   // set the pointer to big_b to the leftmost position
   big_b_ptr_ref = 0;
   for( big_a_ptr_ref = big_a_len - 2 ; big_a_ptr_ref >= 0 ; big_a_ptr_ref--){
      inter_result = 0;
      big_b_ptr = big_b_ptr_ref;
      for(  big_a_ptr = big_a_ptr_ref;
            big_a_ptr >= 0 && big_b_ptr < big_b_len;
            big_b_ptr++){
         char c[2];
         c[1] = '\0';
         int a,b;
         c[0] = big_a[big_a_ptr];
         a = strtol(c, &null, 10);
         c[0] = big_b[big_b_ptr];
         b = strtol(c, &null, 10);
         inter_result += ( a * b );
         #ifdef DEBUG
         fprintf(stdout,"\t%d*%d=%d", a, b, (a * b));
         #endif
         big_a_ptr--;
      }

      // add previous carry
      #ifdef DEBUG
      fprintf(stdout," [sum = %d+%d=%d;",
              inter_result, carry, inter_result + carry);
      #endif
      inter_result += carry;
      carry = inter_result / 10;
      inter_result %= 10;
      #ifdef DEBUG
      fprintf(stdout," keep = %d; carry = %d];",
              inter_result,carry);
      #endif
      char c[5];
      c[4] = '\0';
      snprintf(c, sizeof(int), "%d", inter_result);
      result[result_ptr] = *c;
      result_ptr++;
      #ifdef DEBUG
      fprintf(stdout,"result= %s\n", result);
      #endif
   }

   #ifdef DEBUG
   fprintf(stdout,"carry = %d\n",carry);
   fprintf(stdout,"result= ");
   #endif
   if (carry > 0)
      fprintf(stdout, "%d",carry);
   for(result_ptr=(strlen(result)-1);result_ptr>=0;result_ptr--)
      fprintf(stdout,"%c",result[result_ptr]);

   fprintf(stdout,"\n");

   free(result);
   return 0;
}