Блог пользователя _arjun

Fast Multiplication
Автор _arjun, 14 лет назад, По-английски
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 ?
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
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.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      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.
      → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Actually this problem doesn't require FFT or Karatsuba, O(n^2) multiplication gets AC, but of course with some optimization.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
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.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    thanks a lot got AC, it was giving TLE because of too much MODULOUS and DIVIDE operations
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I remember this was my first karatsuba implementation. Never got a chance to use it again... :p
→ Ответить