_arjun's blog

Fast Multiplication
By _arjun, 13 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

13 years ago, # |
← 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
  • 13 years ago, # ^ |
      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
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      By taking 10^9 base you are making yourself use 64-bit integer type. On 32-bit processor it might be not faster than using 32-bit types and making more operations.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I had tried with 10 ^4 and 10 ^ 5 bases also but that was still giving TLE
        → Reply
13 years ago, # |
  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
  • 13 years ago, # ^ |
      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
13 years ago, # |
  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