public
Created

bigmult.c

  • Download Gist
gistfile1.c
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
/* 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;
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.