Tuesday, 21 May 2013

Multiplication of two Integers

There are two methods for the multiplication of the two integers 
1) Divide and Conquer Method and  2) Karatsuba Method. Both methods are as follow.

1) Multiplication of two Integer using Divide and Conquer Method:

 The Program code for Divide and Conquer method is as below.


#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<math.h>
long double  dnc(char *,char *,int,int);
long double dnc1(int *,int *,int,int);
void main()
{
            int len1,len2,length,k1,i,j;
clock_t a,b;
            long double  ans=0;
            char mul1[100],mul2[100];
            clrscr();
            printf("enter two values\n");
            gets(mul1);
            gets(mul2);
            len1=strlen(mul1);
            len2=strlen(mul2);
            if(len1 % 2!= 0)
            {
                        for(i=len1;i>0;i--)
                                    mul1[i]=mul1[i-1];
                        mul1[0]='0';
                        len1++;
            }
            if(len2 % 2!= 0)
            {
                        for(i=len2;i>0;i--)
                                    mul2[i]=mul2[i-1];
                        mul2[0]='0';
                        len2++;
            }
            if(len1>len2)
            {
                        k1=len1-len2;
                        for(i=len2+k1-1;i>=len2;i--)
                                    mul2[i]=mul2[i-len2];
                        for(i=0;i<len2;i++)
                                    mul2[i]='0';
                        len2=len2+k1;
            }
            if(len2>len1)
            {
                        k1=len2-len1;
                        for(i=len1+k1-1;i>=len1;i--)
                                    mul1[i]=mul1[i-len1];
                        for(i=0;i<len1;i++)
                                    mul1[i]='0';
                        len1=len1+k1;
            }
            j=len1/2;
            if(j%2 !=0 && len1!=2)
            {
                        for(i=len1+1;i>1;i--)
                        {
                                    mul1[i]=mul1[i-2];
                                    mul2[i]=mul2[i-2];
                        }
                        for(i=0;i<2;i++)
                        {
                                    mul1[i]='0';
                                    mul2[i]='0';
                        }
                        len1=len1+2;
            }
            length=len1;
            a=clock();
            ans=dnc(mul1,mul2,len1,length);
            b=clock();
            printf("\n%Lf",ans);
            printf(“Time in milisecond is %ld”,(b-a)*1000/(CLK_TCK));
            getch();
}
long double dnc(char *mul1,char *mul2,int len1,int length)
{
            int i,j,mult1[100],mult2[100];
            long double  answer=0;
            for(i=0;i<len1;i++)
                        mult1[i]=mul1[i]-'0';
            for(j=0;j<len1;j++)
                        mult2[j]=mul2[j]-'0';
            answer=dnc1(mult1,mult2,len1,length);
            return answer;
}

long double  dnc1(int *mult1,int *mult2,int len1,int length)
{

            long double ans1=0,ans2=0,ans3=0,ans4=0,ans=0;
            int i;
            int a[100],b[100],c[100],d[100];
            len1=len1/2;
            for(i=0;i<len1;i++)
                        a[i]=mult1[i];
            for(i=len1;i<2*len1;i++)
                        b[i-len1]=mult1[i];
            for(i=0;i<len1;i++)
                        c[i]=mult2[i];
            for(i=len1;i<2*len1;i++)
                        d[i-len1]=mult2[i];
            if(len1==1)
            {
                        ans1=a[0]*c[0]*pow(10,2);
                        ans2=a[0]*d[0]*pow(10,1);
                        ans3=b[0]*c[0]*pow(10,1);
                        ans4=b[0]*d[0]*pow(10,0);
                        ans=ans1+ans2+ans3+ans4;
                        return ans;
            }
            else     if(len1==length/2)
            {
                        ans1=dnc1(a,c,len1,length) * pow(10,length);
                        ans2=dnc1(a,d,len1,length) * pow(10,length/2);
                        ans3=dnc1(b,c,len1,length) * pow(10,length/2);
                        ans4=dnc1(b,d,len1,length) * pow(10,0);
                        ans=ans1+ans2+ans3+ans4;
                        return ans;
            }
            else if(len1<1)
                        return 1;
            else
            {
                        ans1=dnc1(a,c,len1,length) * pow(10,len1);
                        ans2=dnc1(a,d,len1,length) * pow(10,len1/2);
                        ans3=dnc1(b,c,len1,length) * pow(10,len1/2);
                        ans4=dnc1(b,d,len1,length) * pow(10,0);
                        ans=ans1+ans2+ans3+ans4;
                        return ans;
            }
}


2) Multiplication of two Integer using Karatsuba Method :

 

The code for the karatsuba method is as  below


#include<stdio.h>
#include<conio.h>
long pow(long no,long n)
{
            long i,a=1;
            for(i=0;i<n;i++)
            {
            a=a*no;
            }
            return a;
}
long karatsuba(long a,long b,long n)
{
            long w,x,y,z;
            int p,q,r,s;
            if(n>1)
{          
           p=a/pow(10,n/2);
                        q=a%pow(10,n/2);
                        r=b/pow(10,n/2);
                        s=b%pow(10,n/2);
                        w=karatsuba(p,r,n/2)*pow(10,n);
                        x=karatsuba(p,s,n/2)*pow(10,n/2);
                        y=karatsuba(q,r,n/2)*pow(10,n/2);
                        z=karatsuba(q,s,n/2);
                        return w+x+y+z;
}
else
                        return a*b;
}
void main()
{
long p;
clrscr();
p=karatsuba(99999,99999,5);
printf("%ld",p);
getch();
}


This is two method for the multiplication the two integer.Both methods are used in the data structure subject and the design and analysis of the algorithm

0 comments:

Post a Comment