출처 삶 그리고 깨달음 | 프리맨
원문 http://blog.naver.com/lonekid/60008258279

알다시피 실수를 표현하는 방법에는 부동소수점과 고정소수점 두 가지가 있다.

부동소수점은 일반적으로 C에서 float 이나 double 형으로 표현되는 방식이다. 이에 비해 고정소수점은 정수부와 소수부에 고정 비트수를 할당하여 [n.0 ~ n+1.0) 의 범위를 표현하는 방식이다. 즉 지수승은 표현하지 못하며 소수부에 대해 [0 ~ 1) 의 범위를 표현하는 방식이다. 이런 연유로 인해 고정소수점은 일반적으로 정수와 동일한 비트 표현을 갖기 때문에 정수연산과 동일한 레벨에서 처리할 수 있다.


아무리 FPU가 탑재되어 있다하더라도 정수 연산에 비해 부동소수점 연산은 수십배 이상 느리다. 그렇기 때문에 지수승에 의한 넓은 범위의 수치를 다루는 경우가 아니라면 고정소수점을 사용하는 것이 충분한 가치를 갖는다. 일반적으로 학문적 수준에서의 알고리즘들은 실수 구간의 연속 데이타를 대상으로 하지만 컴퓨터는 기본적으로 양자화된 이산(정수) 데이타를 대상으로 한다. 즉, 컴퓨터에 있어 알고리즘의 최종 결과는 대부분 정수이다. 그렇기 때문에서 알고리즘을 컴퓨터로 구현함에 있어 실수가 아닌 정수를 대상으로 하는 고속화된 이산(정수) 알고리즘들이 고안되는 것이다.


일반적으로 실수 알고리즘들은 [0 ~ 1) 범위의 노말라이즈된 수치로 표현되는 것이 보통이다.

정수부와 소수부에 각각 16비트씩 할당하는 16:16 고정소수점을 생각해보자. 정수부는 -32768 ~ +32767의 범위를 표현할 수 있으며 소수부는 [0 ~ 1) 의 범위를 65536 단계의 해상도(소수점 이하 4~5자리의 정확도)로 표현하게 된다. 즉, 0.1은 6554(65536*0.1), 0.5는 32768(65536*0.5), 0.8은 52429(65536*0.8)로 표현된다. 이렇게 표현되는 고정소수점에 대한 가감승제 연산은 컴퓨터 입장에서 32비트 정수에 대한 가감승제 연산과 동일하다. 다만 16비트 소수부에 대한 자리수만 고려해 주면 된다.


이렇게 표현되는 고정소수점에 대한 수학 클래스를 예시한다.

이 클래스에서는 고정소수점 버전의 삼각함수(Sin, Cos, Tan)를 테이블 방식으로 구현하고 있는데 이해하는데 어려움은 없을 것이다.


김인대



// 16:16 fixed point constant

#define FIXED_PI2       102944      // (3.1415926535 / 2) * 65536

#define FIXED_2PI       411775      // (2 * 3.1415926535) * 65536

#define FIXED_PI        205887      // 3.1415926535 * 65536

#define FIXED_R2D       3754936     // (180 / 3.1415926535) * 65536

#define FIXED_D2R       1144        // (3.1415926535 / 180) * 65536

#define FX_R2D(fxR)     ::MulDiv((fxR), 180 * 65536, FIXED_PI)

#define FX_D2R(fxD)     ::MulDiv((fxD), FIXED_PI, 180 * 65536)

 

#ifndef _countof

#define _countof(a)     (sizeof(a)/sizeof(a[0]))

#endif

 

// 16:16 fixed point

typedef long CFixed;

 

// 16:16 fixed point math class.

class CFxMath

{

public:

    static int ToInt(CFixed fxDeg)      { return fxDeg >> 16; }

    static int Round(CFixed fxDeg)      { return (fxDeg + 32768) >> 16; }

    static double ToDbl(CFixed fxDeg)   { return fxDeg / 65536.0; }

    static CFixed ToFx(int n)           { return n << 16; }

    static CFixed ToFx(double d)        { return CFixed(d * 65536); }

   

    static CFixed FxSin(CFixed fxDeg);

    static CFixed FxCos(CFixed fxDeg)   { return FxSin(fxDeg + 90 * 65536); }   // sin(deg + pi/2)

    static CFixed FxTan(CFixed fxDeg);

 

private:

    enum

    {

        eSinTableResolution = 7     // The resolution(bits) of fraction part.

    };

    static USHORT m_awSinTable[90 * (1 << eSinTableResolution)];    // 0 ~ 89.n degree

    static bool m_bInitSinTable;

    static bool InitSinTable();

};

 

// static

CFixed CFxMath::FxSin(CFixed fxDeg)

{

    // Normalize to -360 ~ +360 degree.

    if (fxDeg <= -360 * 65536 || 360 * 65536 <= fxDeg)

    {

        fxDeg = fxDeg % (360 * 65536);

    }

   

    // Normalize to 0 ~ 360 degree.

    if (fxDeg < 0)

    {

        fxDeg = (360 * 65536) + fxDeg;  // sin(2*pi + n) == sin(n)

    }

   

    // Adjust angle for quadrant.

    int nQuad = fxDeg / (90 * 65536);

    switch (nQuad)

    {

    case 1:     // 90 ~ 180 degree

        fxDeg = (180 * 65536) - fxDeg;

        break;

    case 2:     // 180 ~ 270 degree

        fxDeg = fxDeg - (180 * 65536);  // -sin(fxDeg)

        break;

    case 3:     // 270 ~ 360 degree

        fxDeg = (360 * 65536) - fxDeg;  // -sin(fxDeg)

        break;

    case 0:     // 0 ~ 90 degree

    default:

        fxDeg;

        break;

    }

    ASSERT(0 <= fxDeg && fxDeg <= (90 * 65536));

   

    // Sin table lookup.

    long fxSinValue;

    if (fxDeg == (90 * 65536))

    {

        fxSinValue = 1 * 65536;             // For 90 degree

    }

    else

    {

        int nDegIdx = fxDeg >> (16 - eSinTableResolution);

        fxSinValue = m_awSinTable[nDegIdx]; // For 0 ~ 89.n degree

    }

    return (nQuad < 2) ? fxSinValue : -fxSinValue;  // 16:16 fixed point

}

 

// static

CFixed CFxMath::FxTan(CFixed fxDeg)

{

    CFixed fxCos = FxCos(fxDeg);

    return (fxCos == 0) ? MAXLONG : ::MulDiv(FxSin(fxDeg), 65536, fxCos);

}

 

USHORT CFxMath::m_awSinTable[90 * (1 << eSinTableResolution)];  // 0 ~ 89.n degree

bool CFxMath::m_bInitSinTable = InitSinTable();

 

bool CFxMath::InitSinTable()

{

    const double d2r = 3.1415926535 / 180;

    for (int nDegIdx = 0; nDegIdx < _countof(m_awSinTable); nDegIdx++)

    {

        double dDeg = (double)nDegIdx / (1 << eSinTableResolution);

        double dSin = ::sin(dDeg * d2r);

        m_awSinTable[nDegIdx] = USHORT(dSin * 65536 + 0.5);

    }

    return true;

}

'C/C++언어' 카테고리의 다른 글

고정 소수점 (C++언어 버젼)  (0) 2008.05.09
코드 최적화  (0) 2008.05.09
[알고리즘]고정소수점(fixed point) 연산  (0) 2008.05.09
음 고정소수점 만들기..  (0) 2008.05.09
고정 소수점  (0) 2008.05.09
각 언어별 3중 포인터  (0) 2008.05.06

+ Recent posts