4 ms·

This is well know in competitive programming usually it's the second best alternative after karatsuba.

• giornogiovanna 8y ago
  Generally Fourier methods are asymptotically better than Karatsuba, but with much higher constants, which makes them kind-of impractical until you get very big numbers. Anyway, do competitive programmers tend to program everything from scratch, or is there another reason they don't just use GMP?
  • bcaa7f3a8bbc 8y ago
    > Anyway, do competitive programmers tend to program everything from scratch, or is there another reason they don't just use GMP? I think directly using algorithms and programs implemented by others would be considered cheating (and these libraries are not presented on the server which checks your answer anyway). In competitive programming, participants compete their own ability and knowledge to implement algorithms.
    • 6keZbCECT2uB 8y ago
      In ACM ICPC, we could bring printouts of library code and manually transcribe them into the computer. IIRC, FFT was apart of our team's library code, but you wouldn't use GMP since it would require too much typing.
    • Hernanpm 8y ago
      In C++ thanks to complex the implementation is short see https://ideone.com/tbHUN7 https://ideone.com/tbHUN7
      • bcaa7f3a8bbc 8y ago
        C99 has complex, too. I think most competitive programming contests are now using C99, finally.