Slight GCD optimization

Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

→ Pay attention

Before contest
Codeforces Round 1133 (Div. 1)
20:16:38
Register now »

*has extra registration

Before contest
Codeforces Round 1133 (Div. 2)
20:16:37
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

View all →

→ Find user

→ Recent actions

Detailed →

yoshi_avx's blog

Slight GCD optimization

By yoshi_avx, history, 7 months ago, In English

Preparing a lookup table in binary GCD can be somewhat effective if the inputs are small. I've seen a 30% time reduction with a 512x512 table (which consumes almost no memory and time) for inputs less than $$$2\times10^9$$$. It scales quite linearly with the log.

Code

int lut[512][512];
uint32_t faster_binary_gcd(uint32_t u, uint32_t v)
{
    auto zu = std::countr_zero(u);
    auto zv = std::countr_zero(v);
    auto shift = std::min(zu, zv);
    u >>= zu;
    v >>= zv;
    do
    {
        if (u < 512)
            return lut[u][v % u] << shift;
        uint32_t u_minus_v = u - v;
        if (u > v)
        {
            u = v, v = u_minus_v;
        }
        else
        {
            v = v - u;
        }
        v >>= std::countr_zero(u_minus_v);
    } while (v != 0);
    return u << shift;
}