Created
December 11, 2013 09:41
-
-
Save pratikone/7907626 to your computer and use it in GitHub Desktop.
C code to multiply 2 million-digit numbers
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
// | |
// main.c | |
// MultiplyX | |
// | |
// Created by Pratik Anand on 02/12/13. | |
// Copyright (c) 2013 Pratik Anand. All rights reserved. | |
// | |
#include <stdio.h> | |
#include <stdlib.h> | |
#define SIZE 100000000 | |
int main(int argc, const char * argv[]) | |
{ | |
struct timeval tv_start,tv_end; | |
// insert code here... | |
printf("Hello, World!\n"); | |
int lookup[10][10]; | |
//lookup table | |
for(int l1=0;l1<=9;l1++) | |
for (int l2=0; l2<=9; l2++) { | |
lookup[l1][l2]=l1*l2; | |
} | |
char *dSum=(char*)malloc(SIZE*sizeof(char)); | |
for (int dd=0; dd<SIZE; dd++) { | |
dSum[dd]='0'; | |
} | |
const int nsize=1000000; | |
printf("\nnumber:\n"); | |
char number[nsize+1]; | |
for (int k=0; k<nsize; k++) { | |
number[k]=rand()%10+'0'; | |
printf("%c",number[k]); | |
} | |
printf("\nmultiplier:\n"); | |
const int msize=1000000; | |
char multiplier[msize+1]; | |
for (int k=0; k<msize; k++) { | |
multiplier[k]=rand()%10+'0'; | |
printf("%c",multiplier[k]); | |
} | |
printf("\n"); | |
char *result=(char*)malloc(SIZE*sizeof(char)); | |
int ctrResJ=0; | |
int carry=0; | |
int res=0; | |
int d1=0,d2=0; | |
int dCarry=0; | |
int digit=0; | |
int dTemp=0; | |
int dRes=0; | |
int realCtr=0; | |
gettimeofday(&tv_start,NULL); | |
//tv_start.tv_sec ;// seconds | |
//tv_start.tv_usec; // microseconds | |
for (int ctr=msize-1; ctr>=0; ctr--,realCtr++) { | |
for (int ctrNum=nsize-1;ctrNum>=0 ; ctrNum--) { | |
res=(number[ctrNum]-'0')*(multiplier[ctr]-'0'); | |
//res=lookup[number[ctrNum]-'0'][multiplier[ctr]-'0']; | |
//adding the carry | |
res=res+carry; | |
carry=res/10; | |
res=res%10; | |
//printf("RESULT %c * %c = %d CARRY=%d\n",number[ctrNum],multiplier[ctr],res,carry ); | |
result[ctrResJ++]=res+'0'; | |
res=0; | |
} | |
if(carry>0){ | |
result[ctrResJ++]=carry+'0'; //last carry | |
carry=0; | |
} | |
result[ctrResJ++]='\0'; | |
ctrResJ=0; | |
//add | |
d2=0; | |
while (result[d2]!='\0') { | |
digit=result[d2]-'0'; | |
dTemp=dSum[d2+realCtr]-'0'; | |
dRes=(dTemp+digit+dCarry); | |
dSum[d2+realCtr]=(dRes%10)+'0'; | |
dCarry=dRes/10; | |
d2++; | |
} | |
if(dCarry>0){ | |
dSum[d2+realCtr]=dCarry+'0'; //last carry | |
dCarry=0; | |
d2++; | |
} | |
//copying for knowing the final end | |
d1=d2+realCtr; | |
d2=0; | |
//printf("Result is %s\n",dSum); | |
printf("\nMultiplier digit pos: %d\n",ctr); | |
} | |
dSum[d1]='\0'; | |
gettimeofday(&tv_end,NULL); | |
printf("\nTime taken :%ld sec\n",tv_end.tv_sec-tv_start.tv_sec); | |
printf("\nTime taken :%d us\n",tv_end.tv_usec-tv_start.tv_usec); | |
int i=d1-1; | |
char printDigit=0; | |
while (i>=0) { | |
printDigit=dSum[i]; | |
printf("%c",printDigit); | |
i--; | |
} | |
printf("\n"); | |
free(dSum); | |
free(result); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment