Int64 gcd computation is too slow in Haskell

Revision en1, by codefforces, 2020-12-25 09:51:05

Problem: https://codeforces.net/contest/1459/problem/C Editorial: https://codeforces.net/blog/entry/85750

The solution is all about like 4*10^5 many gcd computations of large (Int64) numbers. It appears that Haskell is too slow do just this!

C++ solution passes in ~ 1.3 sec (https://codeforces.net/contest/1459/submission/102278594). Haskell on the other hand exceeds TL (2 sec) with both Int64 and Integer types.

Integer https://codeforces.net/contest/1459/submission/102279283

Int64 https://codeforces.net/contest/1459/submission/102279784

Disappointing. Your thoughts?

Tags haskell, int64, gcd, performance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English codefforces 2020-12-26 11:29:23 165 Tiny change: '\n**Update**\nIt tur' -> '\n**Update:**\nIt tur'
en9 English codefforces 2020-12-25 10:19:44 0 (published)
en8 English codefforces 2020-12-25 10:19:23 26 Tiny change: 'oblem/C)\nThe [alg' -> 'oblem/C)\n\nThe [alg'
en7 English codefforces 2020-12-25 10:15:34 51 Tiny change: 'erforming 4⋅1054⋅1054⋅10^5 gcd compu' -> 'erforming $$4⋅10^5$$ gcd compu'
en6 English codefforces 2020-12-25 10:09:59 10 Tiny change: 'erforming ``4⋅10^5`` gcd compu' -> 'erforming $$$4⋅10^5$$$ gcd compu'
en5 English codefforces 2020-12-25 10:08:36 12 Tiny change: 'erforming 400000 gcd compu' -> 'erforming ``4⋅10^5`` gcd compu'
en4 English codefforces 2020-12-25 10:07:30 54
en3 English codefforces 2020-12-25 10:02:40 50
en2 English codefforces 2020-12-25 09:59:28 410
en1 English codefforces 2020-12-25 09:51:05 846 Initial revision (saved to drafts)