Instantly share code, notes, and snippets.

# jvehent/gist:3757123 Created Sep 20, 2012

bigmult.c
 /* Perform efficient multiplication of big numbers * Julien Vehent July 2012 * gcc -DDEBUG -Wall -o bigmult0.2 bigmult0.2.c */ #include #include #include #include int main(int argc, char **argv){ if(argc != 3){ fprintf(stdout,"\n./bigmult \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; }