_arjun's blog

Fast Multiplication
By _arjun, 16 years ago, In English
I had posted the same at topcoder and spoj but can't get the desired help, can somebody help me here for this problem. This code is taking 8 sec and I am taking 10^9 base, how can I reduce the time ?
  • Vote: I like it
  • +5
  • Vote: I do not like it

16 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it
That's the point of this problem. Naive algorithm won't do. You should use more involved methods like FFT or Karatsuba.

Here is a link to one of the TopCoder forum's posts regarding this problem.

Edit: Oh, I see you already know about that TC post. Then I don't understand what you're asking for. There is already enough information in that thread.
→ Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Thanks for the reply,
    I know that FFT or Karatsuba are better options, but some people have got accepted by just optimising the O(n^2)  approach like innocentboy's solution by using 10 ^ 5 base, thats why I tried this way and decided to take the base 10^9 but it is taking much time, so I just wanted to know that where am I going wrong?

    sorry for my bad english :)
    → Reply
16 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
Read this thread on spoj forum. Read the posts by the user "Robert Gerbicz".
See the example that he gave and try to use less modulus operator.
I did exactly what he told and got Ac in 1.06s.
→ Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it
    thanks a lot got AC, it was giving TLE because of too much MODULOUS and DIVIDE operations
    → Reply
16 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
I remember this was my first karatsuba implementation. Never got a chance to use it again... :p
→ Reply