sub gcd {
    my ($u, $v) = @_;

    return $v if !$u || $u == $v;
    return $u if !$v;

    my $shift = 0;
    while (!(($u | $v) & 1)) {
        $u >>= 1;
        $v >>= 1;
        ++$shift;
    }

    $u >>= 1 while !(u & 1);

    do {
        $v >>= 1 while !(v & 1);

        ($u,$v)=($v,$u) if $u > $v;
        $v -= $u;
    } while $v;

    return $u << shift;
}