3 times faster MT19937 in GCC

→ Pay attention

Before contest
Codeforces Round 995 (Div. 3)
00:15:25
Register now »

→ Streams

Codeforces Round 995 Solution Discussion

By aryanc403

Before stream 02:35:24

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

View all →

→ Find user

→ Recent actions

Detailed →

3 times faster MT19937 in GCC

Revision en1, by oToToT, 2022-10-28 22:11:56

TL; DR: #include <ext/random> and use __gnu_cxx::sfmt19937 just as std::mt19937.

Hi all,

I'm here to share a thing that seems not that well-known in the whole community.

I test the two codes below in the Codeforces' custom test with input 1000000000

sfmt19937

#include <bits/stdc++.h>
#include <ext/random>
using namespace std;

using RNG = __gnu_cxx::sfmt19937;
decltype(RNG()()) x;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    RNG rnd(1234);
    for (int i = 0; i < n; ++i)
        x = rnd();
    cout << rnd() << '\n';
    return 0;
}

mt19937

#include <bits/stdc++.h>
using namespace std;

using RNG = mt19937;
decltype(RNG()()) x;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    RNG rnd(1234);
    for (int i = 0; i < n; ++i)
        x = rnd();
    cout << rnd() << '\n';
    return 0;
}

History

Revisions

Rev.	By	When	Δ	Comment
en3	oToToT	2022-10-28 22:33:41	0	(published)
en2	oToToT	2022-10-28 22:33:02	724
en1	oToToT	2022-10-28 22:11:56	1050	Initial revision (saved to drafts)