wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Multiply two 100 digit integers.
        
(Message started by: Skandh on Sep 17^th, 2007, 12:50am)

Title: Multiply two 100 digit integers.
Post by Skandh on Sep 17^th, 2007, 12:50am

Hello all,
This question was asked in an Interview, they asked me to multiply two 100 digit numbers. I gave n^2 solution with n space complexity, but they were not happy.

I am not able to find any efficient method. Please help me.

Thanx

Title: Re: Multiply two 100 digit integers.
Post by Grimbal on Sep 17^th, 2007, 1:00am

There are faster methods, but they are not trivial, so if you don't know them it is unlikely you are going to find them during an interview.

I found this, for instance:
http://mathworld.wolfram.com/KaratsubaMultiplication.html

Title: Re: Multiply two 100 digit integers.
Post by towr on Sep 17^th, 2007, 2:55am

The (conceptually) simple way, take the fourier transform of both numbers (as vectors of single digits), pointwise multiply the spectra, and do the reverse fourier transform. You can do a fourier transform in O(n log(n)) time, and the pointwise multiplication is O(n), so the total is O(n log n).

Mind the rounding errors though, because you go from integers to real (or complex), and going back won't give integers precisely.

Title: Re: Multiply two 100 digit integers.
Post by SMQ on Sep 17^th, 2007, 5:46am

Although even with "gradeschool" multiplication, it should be fairly easy to see how to get the space complexity down to O(n) from O(n^2).

--SMQ

Title: Re: Multiply two 100 digit integers.
Post by goforit on Oct 3^rd, 2007, 9:34pm

Well, it may not be that difficult if you convert it into a typical C program...

say A[] and B[] are given arrays and we are keeping the result into C.

m and n are the sizes of A and B respectively.
int i, j, c, t;
for (i=0;i<m+n-1;i++)
C[i] = 0;

for(i=0;i<m;i++)
{
j=0; c = 0;

while(j <= n-1)
{
t = C[i+j] + a[i] * a[j] + c;
C[i+j] = t % 10;
c = C[i+j] / 10;
}

C[i+n] = c;
}

Cheers,
Nag

Title: Re: Multiply two 100 digit integers.
Post by Grimbal on Oct 4^th, 2007, 1:34am

I'm afraid it is O(n²) if m=n. The question was for ways to improve over that.

Title: Re: Multiply two 100 digit integers.
Post by goforit on Oct 26^th, 2007, 12:28am

ohh, i have writter for O(m+n) memory:)

then, i dont know the answer:) :D