Skip to content

Instantly share code, notes, and snippets.

@pratikone
Created December 11, 2013 09:41
Show Gist options
  • Save pratikone/7907626 to your computer and use it in GitHub Desktop.
Save pratikone/7907626 to your computer and use it in GitHub Desktop.
C code to multiply 2 million-digit numbers
//
// 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