Skip to content

Instantly share code, notes, and snippets.

@DanBUK
Created October 29, 2012 08:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save DanBUK/3972281 to your computer and use it in GitHub Desktop.
Save DanBUK/3972281 to your computer and use it in GitHub Desktop.
Program does "big multiplication" - Should be able to handle numbers of _ANY_ length
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* Program does "big multiplication"
Should be able to handle numbers of _ANY_ length
Input via stdin:-
N
X1 Y1
X2 Y2
Where N == number of lines to follow
Xn Yn == Pair of number to multiply up to 10,000 decimal digits per number
Example input:
1
101 6667
Example output:
673367
*/
typedef struct {
int size;
short *digits;
} IntArray;
void atoIntArray (char *input, IntArray *rtv) {
int c;
rtv->size = strlen(input);
rtv->digits = (short *) malloc(rtv->size * sizeof(short));
for(c = 0; c < rtv->size; c++) {
rtv->digits[c] = input[c] - 48;
}
}
void print_IntArray (IntArray *rtv) {
int c;
int print = 0;
for(c = 0; c < rtv->size; c++) {
if (print > 0 || rtv->digits[c] > 0) {
print++;
printf("%d", rtv->digits[c]);
}
}
if (print == 0) {
printf("0");
}
printf("\n");
}
void do_add(IntArray *rtv, short amount, int pos) {
int tmpres = rtv->digits[pos] + amount;
if (tmpres > 9) {
do_add(rtv, floor(tmpres / 10), (pos - 1));
rtv->digits[pos] = tmpres % 10;
} else {
rtv->digits[pos] = tmpres;
}
}
void do_multi(char *inputline) {
char *pch;
IntArray left, right, output;
int r, l;
pch = strtok (inputline, " ");
atoIntArray(pch, &left);
pch = strtok (NULL, "\n");
atoIntArray(pch, &right);
output.size = right.size + left.size;
output.digits = (short *) malloc((output.size) * sizeof(short));
for(r = 0; r < output.size; r++) {
output.digits[r] = 0;
}
for(r = right.size - 1; r >= 0; r--) {
for(l = left.size - 1; l >= 0; l--) {
do_add(&output, (right.digits[r] * left.digits[l]), (l + r + 1));
}
}
free(right.digits);
free(left.digits);
print_IntArray(&output);
free(output.digits);
}
int main() {
int bytes_read;
int max_line = 102400;
int num_lines;
int curr_line = 0;
char *stringline;
stringline = (char *) malloc(max_line + 1);
bytes_read = getline (&stringline, &max_line, stdin);
if (bytes_read == -1) {
puts ("ERROR!");
} else {
num_lines = atoi(stringline);
while (curr_line < num_lines) {
bytes_read = getline (&stringline, &max_line, stdin);
do_multi(stringline);
curr_line++;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment