CareerCup

http://en.wikipedia.org/wiki/Karatsuba_algorithm

could anyone provide sample answers to this?

could anyone please share sample answer to this problem?

I guess the trick is that the number could be over 16 byte
so first find out how many bytes we need, then multiply different parts seperately

represent numbers using linked list ...having 16 bype per node and hten multiply it...answer would be again number in linked list..

basic math
karatsuba

Try Russian peasant algorithm

I guess linked list soln is a good one.

ans this some1

How about using the regular hand-written approach, like with pen and paper, eventually reducing it to a series of single digit additions and carry management.

How about this:

int main(){
int a = 9, b = 12;
int result = 0;
while (b&01){
if(b!=0) result += a;

a <<= 1;
b >>= 1;
}
}

An Algorithm for multiplication of long numbers is given in TH Cormen. It basically uses FFT to multiply long numbers. Resulting algorithm multiplies in nlogn multiplications instead of n^2

An Algorithm for multiplication of long numbers is given in TH Cormen. It basically uses FFT to multiply long numbers. Resulting algorithm multiplies in nlogn multiplications instead of n^2

a <<= 1

#include <stdio.h>
#define MAX 40                   
main()
{
    int Num[2][MAX];         
    int Result[MAX];         
    int Index[2]={0,0};      
    int i,j,k;
    int data;
    int tmp1,tmp2;         
    int Flag;

/**********************************************************/
    for(tmp1=0;tmp1<MAX;tmp1++)
    {
        Num[0][tmp1]=0;
        Num[1][tmp1]=0;
        Result[tmp1]=0;
    }

/*******************************************************/
    for(tmp1=0;tmp1<2;tmp1++)
    {
        printf("input number");
        scanf("%d",&data);
        while((data>=0)&&(data<10))
        {
            Num[tmp1][Index[tmp1]]=data;
            Index[tmp1]++;
            scanf("%d",&data);
        }
        printf("%d:",tmp1+1);
        for(tmp2=0;tmp2<Index[tmp1];tmp2++)
        {
            printf("%d",Num[tmp1][tmp2]);
        }
        printf("\n");
    }

/************************************************************/
    tmp1=MAX-1;
    for(i=(Index[1]-1);i>-1;i--)
    {   
        k=tmp1;                         
        for(j=(Index[0]-1);j>-1;j--)
        {    Flag=1;
            Result[k]+=Num[0][j]*Num[1][i];
            if(Result[k]>=10)       
            {
                Result[k-1]+=Result[k]/10;
                Result[k]=Result[k]%10;
                Flag=0;         
            }
            k--;
        }
        tmp1--;
    }

/**************************************************************/
     for(tmp1=(k+Flag);tmp1<MAX;tmp1++)
    {
        printf("%d",Result[tmp1]);
    }
    printf("\n");

}

This one works.

void multiply(char *str1, char *str2, char **result)
{
   int aLen = strlen(str1);
   int bLen = strlen(str2);
   int rLen = aLen + bLen;
   *result = (char *)malloc(rLen+1);
   int i,j;
   for (i = 0; i < rLen; i++)
      (*result)[i] = '0';
   (*result)[rLen] = '\0';
   
   char *a = (char *)malloc(aLen);
   for (i = 0; i < aLen; i++)
      a[i] = str1[aLen-i-1];
   char *b = (char *)malloc(bLen);
   for (i = 0; i < bLen; i++)
      b[i] = str2[bLen-i-1];
   
   for (i = 0; i < aLen; i++)
   {
      for (j = 0; j < bLen; j++)
      {
         (*result)[i+j] += (a[i]-'0')*(b[j]-'0');
         int k = 1;
         int temp = (*result)[i+j]-'0';
         if (temp >= 10)
         {
            (*result)[i+j] = temp % 10 +'0';
            (*result)[i+j+k] += temp / 10;
            temp = (*result)[i+j+k] -'0';
            k++;
         }
      }
   }
   i = rLen -1;
   while ((*result)[i] == '0')
      i--;
   rLen = i+1;
   (*result)[rLen] = '\0';
   for (i = 0; i < rLen/2; i++)
   {
      char c;
      c = (*result)[i];
      (*result)[i] = (*result)[rLen-i-1];
      (*result)[rLen-i-1] = c;
   }
   free(a);
   free(b);
}