2
\$\begingroup\$

This is vedic method multiplication. This code takes time on a very long numeric string, and I want to optimize it. I also apply recursion on multIndices (this function is multiplying two given indices values).

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char str1[10000],str2[10000],resultant[10000000];
int carry=0,n=0;
void mulIndices(int i, int j){
    int result=0;
    for(;i<=j;i++,j--){
    result = result + carry + (str1[i]-48)*(str2[j]-48);
        if(i!=j)
            result += (str2[i]-48)*(str1[j]-48);
    carry=0;
    }
    if(result > 9){
        carry = result/10;
        result %= 10;
    }
    resultant[n++] = result+48;
}
void reverseStr(char str[]){
    int tmp,i=0,j=0,length = strlen(str);
    for(i=0,j=length-1;i<length/2;i++,j--){
            tmp = str[i];
            str[i] = str[j];
            str[j] = tmp;
    }
}
int main()
{
    int value=-1, i=0,u,v,j=0,mulVal=0,length1 = 0,length2 = 0,diffOfLen=0,maxLength=0;
    printf("Enter the first numeric value: ");
    gets(str1);
    printf("Enter the second numeric value: ");
    gets(str2);

    length1 = strlen(str1);
    length2 = strlen(str2);

    if(length2<length1){
        diffOfLen= length1-length2;
        maxLength = length2;
    }else{
        diffOfLen= length2-length1;
        maxLength = length1;
    }

    i = diffOfLen;
/*
    if(length2<length1){
        i += length2;
    }else if(length2>length1){
        i += length1;
    }
*/
    reverseStr(str1);
    reverseStr(str2);

    while(diffOfLen--){
        //printf("%d\n",diffOfLen);
        if(length2<length1){
            str2[i++] = '0';
            str2[i] = '\0';
        }
        else if(length2>length1){
            str1[i++] = '0';
            str1[i] = '\0';
        }
    }
/*
    puts(str1);
    puts(str2);
*/



    for(i=0;i<maxLength;i++){
            mulIndices(0,i);
            //printf("0 %d\n",i);
    }
    for(i=1;i<maxLength;i++){
            mulIndices(i,maxLength-1);
            //printf("0 %d\n",i);
    }if(carry != 0){
        resultant[n++] = carry+48;
    }
    resultant[n] = '\0';
    reverseStr(resultant);
    puts(resultant);

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I want to apply recursion on multIndices function instead on this loop. \$\endgroup\$ – vaibhav May 29 '14 at 16:14
4
\$\begingroup\$
  • Code organization: main does too much. Actual calculations, that is everything between gets and puts shall be a standalone function (multiply). Zero-filling loop shall be factored out into a function (see below). main declares many unused variables (value, u, v, j, mulVal - do you need them?).

  • Globals: globals are bad. Try to get rid of them.

  • Input: Don't use gets. Also, input shall be validated.

  • Magic number: 48 is ASCII for zero. Subtracting '0' would be much more clear. BTW, you do a lot of extra work: it is enough to convert just once as soon as the string lengths are calculated.

Other notes:

Don't be shy on spaces. Things like for(i=0,j=length-1;i<length/2;i++,j--){ are very hard to read.

An if (i != j) condition in mulIndices may only happen upon loop termination. There's no need to test it at every iteration. Similarly, in the length fitting loop, the condition is tested at every iteration. Swapping ifs and while results in better code:

if (length2 < length1) {
    while (diffOfLen--)
        str2[i++] = '0';
    str2[i] = 0;
} else {
    while (diffOfLen--)
        str1[i++] = '0';
    str1[i] = 0;
}

BTW, now it is obvious that the loops are functions. I'd prefer just memset.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.