Created
October 29, 2012 08:15
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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