목록이진 최대공약수 판정법 (1)
cyphen156
알고리듬#1+@ 이진 최대공약수(스테인의 알고리듬)
이번에 배울 내용은 유클리드 알고리듬과 유사한 스테인의 알고리듬이다. 전에 컴퓨터의 연산은 뺄셈이던지 곱셈이던지 혹은 나눗셈이던지 항상 이진 덧셈으로 이루어진다고 했다. 그런데 곱셈 연산과 나눗셈 연산의 경우 덧셈이 아닌 방식으로 동작시키는 것이 가능하다. 바로 비트시프트를 이용하는 것이다. 여기 1byte크기의 메모리에 데이터가 저장되어있다고 하자. 이 정수의 4배를 구하려면 같은 수를 덧셈 연산을 4번 해야 한다. 반면 비트시프트 연산의 경우 단순히 저장된 데이터중 일부 비트정보를 뒤집으면 되기에 이론적으로 횟수로는 2번의 횟수가 되어 덧셈 연산보다 더욱 빠를 수 있다. 나눗셈의 경우도 곱셈과 연산 방향만 바뀔 뿐 연산 수행 횟수는 동일하다. 이러한 비트시프트라는 것과 짝수에 반드시 2라는 약수가 있..
컴퓨터공학/알고리듬
2024. 2. 15. 15:36