최대공약수(GCD)를 구하는 가장 빠른 방법은?
학교 수학 시간에 안 가르치는 것 같은데, 최대공약수를 구하는 알고리즘이 유클리드 호제법이다. 인류 최초의 알고리즘이라고도 알려져있기도 하다. 개념은 단순하다. 서로를 나누어 나머지를 계속 구하는 것. 좀 더 원시적(?)으로 구현하려면 나머지(나누기) 대신 빼기로 구현해도 된다. 보통은 아래와 같은 코드를 사용한다. size_t GCD(size_t x, size_t y) { while (y) { x %= y; if (!x) { return y; } y %= x; } return x; } 그런데, 조금 뒤져보니 Binary GCD라는 알고리즘이 있다. 짝수인 경우 2로 계속 나누어 나눈 횟수를 미리 세어둔 뒤 유클리드 호제법을 사용하는 방식이다. 이 알고리즘은 CPU 명령을 활용하는 _BitScanForw..
