3 times faster MT19937 in GCC

→ Pay attention

Before contest
Refact.ai Match 1 (Codeforces Round 985)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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)