Int64 gcd computation is too slow in Haskell

Правка en8, от codefforces, 2020-12-25 10:19:23

Problem: https://mirror.codeforces.com/contest/1459/problem/C

The algorithm is all about computing gcd of large integers, $$$4⋅10^5$$$ times. Haskell it seems is too slow for even this!

C++ code passes in ~ 1.3 sec.

But Haskell code exceeds TL (2 sec).

Switching from Integer to Int64 does not help a bit. Disappointing.

Any ideas on optimizing it?

Теги 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)