Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
bigmult.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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.