Author |
Topic: Multiply two 100 digit integers. (Read 819 times) |
|
Skandh
Junior Member
Gender: 
Posts: 77
|
 |
Multiply two 100 digit integers.
« on: Sep 17th, 2007, 12:50am » |
 Quote  Modify
|
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
|
| « Last Edit: Sep 17th, 2007, 8:01am by Skandh » |
 IP Logged |
I wanna pull by legs!!!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Multiply two 100 digit integers.
« Reply #1 on: Sep 17th, 2007, 1:00am » |
Quote Modify
|
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
|
| « Last Edit: Sep 17th, 2007, 1:00am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Multiply two 100 digit integers.
« Reply #2 on: Sep 17th, 2007, 2:55am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Multiply two 100 digit integers.
« Reply #3 on: Sep 17th, 2007, 5:46am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
goforit
Newbie
Posts: 5
|
|
Re: Multiply two 100 digit integers.
« Reply #4 on: Oct 3rd, 2007, 9:34pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Multiply two 100 digit integers.
« Reply #5 on: Oct 4th, 2007, 1:34am » |
Quote Modify
|
I'm afraid it is O(n2) if m=n. The question was for ways to improve over that.
|
| « Last Edit: Oct 4th, 2007, 1:35am by Grimbal » |
IP Logged |
|
|
|
goforit
Newbie
Posts: 5
|
|
Re: Multiply two 100 digit integers.
« Reply #6 on: Oct 26th, 2007, 12:28am » |
Quote Modify
|
ohh, i have writter for O(m+n) memory
then, i dont know the answer 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print