3 times faster MT19937 in GCC

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
38:15:04
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	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)