Hacker News Reader

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

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?

> 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.

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.

In C++ thanks to complex the implementation is short see https://ideone.com/tbHUN7

C99 has complex, too. I think most competitive programming contests are now using C99, finally.

Reply on news.ycombinator.com