Int64 gcd computation is too slow in Haskell

Правка en1, от codefforces, 2020-12-25 09:51:05

Problem: https://mirror.codeforces.com/contest/1459/problem/C Editorial: https://mirror.codeforces.com/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://mirror.codeforces.com/contest/1459/submission/102278594). Haskell on the other hand exceeds TL (2 sec) with both Int64 and Integer types.

Integer https://mirror.codeforces.com/contest/1459/submission/102279283

Int64 https://mirror.codeforces.com/contest/1459/submission/102279784

Disappointing. Your thoughts?

Теги haskell, int64, gcd, performance

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский codefforces 2020-12-26 11:29:23 165 Tiny change: '\n**Update**\nIt tur' -> '\n**Update:**\nIt tur'
en9 Английский codefforces 2020-12-25 10:19:44 0 (published)
en8 Английский codefforces 2020-12-25 10:19:23 26 Tiny change: 'oblem/C)\nThe [alg' -> 'oblem/C)\n\nThe [alg'
en7 Английский 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 Английский codefforces 2020-12-25 10:09:59 10 Tiny change: 'erforming ``4⋅10^5`` gcd compu' -> 'erforming $$$4⋅10^5$$$ gcd compu'
en5 Английский codefforces 2020-12-25 10:08:36 12 Tiny change: 'erforming 400000 gcd compu' -> 'erforming ``4⋅10^5`` gcd compu'
en4 Английский codefforces 2020-12-25 10:07:30 54
en3 Английский codefforces 2020-12-25 10:02:40 50
en2 Английский codefforces 2020-12-25 09:59:28 410
en1 Английский codefforces 2020-12-25 09:51:05 846 Initial revision (saved to drafts)