한양과기고 에듀테크 수업도구 대시보드

CORDIC 알고리즘

계산기나 옛날 CPU는 sin, cos 값을 어떻게 구할까? 곱셈기조차 없던 시절엔 테일러 급수(곱셈·나눗셈 범벅)를 돌릴 수 없었다. CORDIC(COordinate Rotation DIgital Computer, 1959)의 답은 놀랍도록 단순하다 — 단위 벡터 (1, 0) 을 목표 각도만큼 회전시키되, 회전을 45°, 26.57°, 14.04°, 7.13°, … 처럼 점점 작아지는 고정 각도들의 덧셈/뺄셈으로 쪼갠다. 이 특별한 각도들은 arctan(2⁻ⁱ) 라서, 각 회전이 2⁻ⁱ 을 곱하는 것 = 비트 시프트와 덧셈만으로 끝난다. 곱셈기가 없는 FPGA·DSP, 인텔 8087 수치 보조프로세서, HP 공학용 계산기가 모두 이 방식을 쓴다.

x' = x − d·y·2⁻ⁱ | y' = y + d·x·2⁻ⁱ | z' = z − d·arctan(2⁻ⁱ)
d = +1 (아직 목표 각도에 못 미침) 또는 −1 (지나침) · ×2⁻ⁱ 는 오른쪽 시프트 i칸

회전 시뮬레이터 — 벡터를 목표 각도로 조금씩 튼다

목표 각도 θ 60.0°

반복 횟수 N 10

반복 i

이번 회전

±45.000°

남은 각도 z

60.000°

x (→ cos)

1.000000

y (→ sin)

0.000000

벡터 길이

1.000000

회전 한 번 을 눌러 보세요. 보라색 벡터가 매번 arctan(2⁻ⁱ) 만큼 목표(초록 점선) 쪽으로 꺾입니다. 벡터가 목표 방향에 거의 붙으면, 그동안 √(1+2⁻²ⁱ) 배씩 늘어난 길이를 상수 K 한 번으로 되돌립니다.

반복 기록 — 각 단계의 시프트·덧셈

i	arctan(2⁻ⁱ)	d	남은 z	x	y

CORDIC cos θ (보정 후)

—

진짜 cos θ

—

CORDIC sin θ (보정 후)

—

진짜 sin θ

—

각도 오차

—

≈ 유효 비트

—

반복 1번당 약 1비트씩 정밀도가 늘어난다(선형 수렴). float 정밀도(≈24비트)면 24회 정도면 충분. 뉴턴법 같은 2차 수렴은 아니지만, 회전 각도 테이블만 미리 저장해 두면 곱셈기 없이 루프만 돌리면 된다는 게 핵심이다.

왜 시프트만으로 회전이 될까 — "유사 회전"과 상수 K

각도 φ 만큼의 진짜 회전은 x' = x·cosφ − y·sinφ, y' = x·sinφ + y·cosφ 다. 여기서 cosφ 를 공통으로 묶어내면 x' = cosφ·(x − y·tanφ), y' = cosφ·(y + x·tanφ). 이제 φ = arctan(2⁻ⁱ) 로만 고르면 tanφ = 2⁻ⁱ 라서 괄호 안은 시프트 + 덧셈뿐이다. 앞의 cosφ 배율만 무시하고 회전하는 것을 유사 회전(pseudo-rotation)이라 부른다.

무시한 배율들은 방향과 무관하게 매번 1/cosφᵢ = √(1 + 2⁻²ⁱ) 씩 곱해지므로, N번 회전 뒤 벡터 길이는 항상 같은 상수배가 된다. 그 역수가 게인 K:

K = ∏_i=0..N−1 1 / √(1 + 2⁻²ⁱ) ⟶ 0.6072529350 (N = 10, N→∞ 이면 0.60725293…)

K는 목표 각도와 무관한 고정 상수 → 코드에 미리 계산해 박아 둔다. 마지막에 x, y 에 한 번만 곱하면 끝.
시작 벡터를 (K, 0) 으로 두면 마지막 곱셈조차 생략된다.
각 arctan(2⁻ⁱ) 값도 상수 테이블(보통 수십 개)로 저장 — 런타임엔 비교·시프트·덧셈만 남는다.

알고리즘 (회전 모드 — 각도 → sin·cos)

# 미리 계산해 두는 상수 테이블
ATAN = [atan(2.0**-i) for i in range(N)]   # arctan(2^-i) 라디안
K = 1.0
for i in range(N): K *= 1.0 / sqrt(1 + 2.0**(-2*i))   # ≈ 0.60725

def cordic(theta, N=24):
    x, y, z = K, 0.0, theta          # 시작 벡터에 K를 미리 반영
    for i in range(N):
        d = 1.0 if z >= 0 else -1.0   # 목표에 못 미치면 +, 지나쳤으면 -
        x, y = x - d*y*(2.0**-i), y + d*x*(2.0**-i)   # ← 하드웨어에선 시프트 i칸
        z = z - d*ATAN[i]                            # 남은 각도에서 이번 회전만큼 빼기
    return x, y                     # x ≈ cos(theta),  y ≈ sin(theta)

cordic(radians(30))   # → (0.86602..., 0.49999...)   ≈ (√3/2, 1/2)

벡터 모드로 부호를 d = -sign(y) 로 바꾸면, 벡터를 x축까지 되돌리며 z 에 arctan(y/x) 가 쌓이고 x 는 √(x²+y²) (벡터 크기)가 된다 → 직각→극좌표 변환.
회전식을 x' = x + d·y·2⁻ⁱ 로 (부호를 +로) 바꾸면 쌍곡선 모드 → sinh, cosh, exp, ln, √ 까지 같은 틀로 계산된다.
고정소수점(정수) 연산과 궁합이 좋아, 곱셈기가 비싼 FPGA/ASIC에서 특히 애용된다.

sin·cos 를 구하는 방법들

	테일러 급수	룩업 테이블 + 보간	CORDIC
필요한 연산	곱셈·나눗셈 다수	큰 메모리 + 곱셈 몇 번	시프트 + 덧셈 + 비교
곱셈기 필요?	필수	보간에 필요	불필요
수렴/정밀도	항 늘릴수록 (구간 끝에서 느림)	테이블 크기에 좌우	반복 1회 ≈ 1비트
한 번에 얻는 값	sin 또는 cos	보통 하나	sin·cos 동시에
대표 사용처	범용 CPU libm	게임·오디오 DSP	8087·HP 계산기·FPGA

CORDIC은 느리지만 하드웨어가 아주 작다 — 곱셈기 하나 넣을 자리에 CORDIC 루프 회로를 넣는 트레이드오프.
수렴 범위는 대략 |θ| < 99.7°(= Σ arctan(2⁻ⁱ)). 그 밖은 사분면을 먼저 접어서 범위 안으로 넣는다.