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

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

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