Построение логарифмической функции в C без использования типа float

Мне нужно переписать функцию журнала (базы 2 или база 10 не имеет значения, какой) без использования float введите, но мне нужно получить точность нескольких десятичных цифр после десятичной точки. (как float * 100 получить 2 десятичные дроби внутри целочисленного типа, например: если 1.4352 будет результат, моя функция должна вернуть что-то вроде 143 (int типа) и я знаю, что последние 2 цифры являются десятичными.

Я нашел через стека overoverflow некоторые методы, такие как:

но все они возвращаются int точность (избегая десятичных дробей).

Я понятия не имею, как подойти к этому, поэтому вопрос:

Как кодировать (и / или изменять) целое число log реализация для поддержки десятичного результата?

1 ответ

Решение

Для этого вам нужно использовать точность / арифметику / математику с фиксированной точкой. Это означает, что вы используете переменные целочисленного типа, но некоторые биты идут после десятичной точки.

например, давайте предположим, что 8 десятичных битов, поэтому операции выполняются так:

a = number1*256
b = number2*256
c=a+b // +
c=a-b // -
c=(a*b)>>8 // *
c=(a/b)<<8 // /

Здесь простая фиксированная точка log2 Пример с помощью бинарного поиска в C++:

//---------------------------------------------------------------------------
const DWORD _fx32_bits      =32;                            // all bits count
const DWORD _fx32_fract_bits= 8;                            // fractional bits count
const DWORD _fx32_integ_bits=_fx32_bits-_fx32_fract_bits;   // integer bits count
//---------------------------------------------------------------------------
const DWORD _fx32_one       =1<<_fx32_fract_bits;           // constant=1.0 (fixed point)
const DWORD _fx32_fract_mask=_fx32_one-1;                   // fractional bits mask
const DWORD _fx32_integ_mask=0xFFFFFFFF-_fx32_fract_mask;   // integer bits mask
const DWORD _fx32_MSB_mask=1<<(_fx32_bits-1);               // max unsigned bit mask
//---------------------------------------------------------------------------
DWORD bits(DWORD p)             // count how many bits is p
    {
    DWORD m=0x80000000; DWORD b=32;
    for (;m;m>>=1,b--)
     if (p>=m) break;
    return b;
    }
//---------------------------------------------------------------------------
DWORD fx32_mul(DWORD x,DWORD y)
    {
    // this should be done in asm with 64 bit result !!!
    DWORD a=x,b=y;              // asm has access only to local variables
    asm {                       // compute (a*b)>>_fx32_fract
        mov eax,a               // eax=a
        mov ebx,b               // ebx=b
        mul eax,ebx             // (edx,eax)=eax*ebx
        mov ebx,_fx32_one
        div ebx                 // eax=(edx,eax)>>_fx32_fract
        mov a,eax;
        }
    return a;
    // you can also do this instead but unless done on 64bit variable will overflow
    return (x*y)>>_fx32_fract_bits;
    }
//---------------------------------------------------------------------------
DWORD fx32_sqrt(const DWORD &x) // unsigned fixed point sqrt
    {
    DWORD m,a;
    if (!x) return 0;
    m=bits(x);                  // integer bits
    if (m>_fx32_fract_bits) m-=_fx32_fract_bits; else m=0;
    m>>=1;                      // sqrt integer result is half of x integer bits
    m=_fx32_one<<m;             // MSB of result mask
    for (a=0;m;m>>=1)           // test bits from MSB to 0
        {
        a|=m;                   // bit set
        if (fx32_mul(a,a)>x)    // if result is too big
         a^=m;                  // bit clear
        }
    return a;
    }
//---------------------------------------------------------------------------
DWORD fx32_exp2(DWORD y)       // 2^y
    {
    // handle special cases
    if (!y) return _fx32_one;                    // 2^0 = 1
    if (y==_fx32_one) return 2;                  // 2^1 = 2
    DWORD m,a,b,_y;
    // handle the signs
    _y=y&_fx32_fract_mask;      // _y fractional part of exponent
     y=y&_fx32_integ_mask;      //  y integer part of exponent
    a=_fx32_one;                // ini result
    // powering by squaring x^y
    if (y)
        {
        for (m=_fx32_MSB_mask;(m>_fx32_one)&&(m>y);m>>=1);     // find mask of highest bit of exponent
        for (;m>=_fx32_one;m>>=1)
            {
            a=fx32_mul(a,a);
            if (DWORD(y&m)) a<<=1;  // a*=2
            }
        }
    // powering by rooting x^_y
    if (_y)
        {
        for (b=2<<_fx32_fract_bits,m=_fx32_one>>1;m;m>>=1)      // use only fractional part
            {
            b=fx32_sqrt(b);
            if (DWORD(_y&m)) a=fx32_mul(a,b);
            }
        }
    return a;
    }
//---------------------------------------------------------------------------
DWORD fx32_log2(DWORD x)    // = log2(x)
    {
    DWORD y,m;
    // binary search from highest possible integer power of 2 to avoid overflows (log2(integer bits)-1)
    for (y=0,m=_fx32_one<<(bits(_fx32_integ_bits)-1);m;m>>=1)
        {
        y|=m;   // set bit
        if (fx32_exp2(y)>x) y^=m; // clear bit if result too big
        }
    return y;
    }
//---------------------------------------------------------------------------

Здесь простой тест (используя поплавки только для загрузки и печати, вы можете обрабатывать стенды и на целые числа, или с помощью констант, оцененных компилятором):

float(fx32_log2(float(125.67*float(_fx32_one)))) / float(_fx32_one)

Это оценивает: log2(125.67) = 6.98828125 мой счет выигрыша возвращается 6.97349648 что довольно близко Для более точного результата вам нужно использовать больше дробных битов. Int и пример с плавающей точкой оценки времени компиляции:

(100*fx32_log2(125.67*_fx32_one))>>_fx32_fract_bits

возвращается 698 что значит 6.98 как мы умножили на 100, Вы также можете написать свою собственную функцию загрузки и печати для прямого преобразования между фиксированной точкой и строкой.

Чтобы изменить точность, просто поиграйте с _fx32_fract_bits постоянная. Во всяком случае, если ваш C++ не знает DWORD это всего лишь 32 бита unsigned int, Если вы используете другой тип (например, 16 или же 64 немного) затем просто измените соответствующие константы.

Для получения дополнительной информации взгляните на:

[Edit2] fx32_mul на 32-битной арифметике без asm база 2^16 O(n^2)

DWORD fx32_mul(DWORD x,DWORD y)
    {
    const int _h=1; // this is MSW,LSW order platform dependent So swap 0,1 if your platform is different
    const int _l=0;
    union _u
        {
        DWORD u32;
        WORD u16[2];
        }u;
    DWORD al,ah,bl,bh;
    DWORD c0,c1,c2,c3;
    // separate 2^16 base digits
    u.u32=x; al=u.u16[_l]; ah=u.u16[_h];
    u.u32=y; bl=u.u16[_l]; bh=u.u16[_h];
    // multiplication (al+ah<<1)*(bl+bh<<1) = al*bl + al*bh<<1 + ah*bl<<1 + ah*bh<<2
    c0=(al*bl);
    c1=(al*bh)+(ah*bl);
    c2=(ah*bh);
    c3= 0;
    // propagate 2^16 overflows (backward to avoid overflow)
    c3+=c2>>16; c2&=0x0000FFFF;
    c2+=c1>>16; c1&=0x0000FFFF;
    c1+=c0>>16; c0&=0x0000FFFF;
    // propagate 2^16 overflows (normaly to recover from secondary overflow)
    c2+=c1>>16; c1&=0x0000FFFF;
    c3+=c2>>16; c2&=0x0000FFFF;
    // (c3,c2,c1,c0) >> _fx32_fract_bits
    u.u16[_l]=c0; u.u16[_h]=c1; c0=u.u32;
    u.u16[_l]=c2; u.u16[_h]=c3; c1=u.u32;
    c0 =(c0&_fx32_integ_mask)>>_fx32_fract_bits;
    c0|=(c1&_fx32_fract_mask)<<_fx32_integ_bits;
    return c0;
    }

Если у вас нет WORD,DWORD добавить это в начало кода

typedef unsigned __int32 DWORD;
typedef unsigned __int16 WORD;

или это:

typedef uint32_t DWORD;
typedef uint16_t WORD;

[Edit3] fx32_mul отладочная информация

позвольте call и trace/breakpoint this (15 дробных битов):

fx32_mul(0x00123400,0x00230056);

Который:

0x00123400/32768 * 0x00230056/32768 =
36 * 70.00262451171875 = 2520.094482421875

Так:

DWORD fx32_mul(DWORD x,DWORD y) // x=0x00123400 y=0x00230056
    {
    const int _h=1;
    const int _l=0;
    union _u
        {
        DWORD u32;
        WORD u16[2];
        }u;
    DWORD al,ah,bl,bh;
    DWORD c0,c1,c2,c3;
    // separate 2^16 base digits
    u.u32=x; al=u.u16[_l]; ah=u.u16[_h]; // al=0x3400 ah=0x0012
    u.u32=y; bl=u.u16[_l]; bh=u.u16[_h]; // bl=0x0056 bh=0x0023
    // multiplication (al+ah<<1)*(bl+bh<<1) = al*bl + al*bh<<1 + ah*bl<<1 + ah*bh<<2
    c0=(al*bl);        // c0=0x00117800
    c1=(al*bh)+(ah*bl);// c1=0x0007220C
    c2=(ah*bh);        // c2=0x00000276
    c3= 0;             // c3=0x00000000
    // propagate 2^16 overflows (backward to avoid overflow)
    c3+=c2>>16; c2&=0x0000FFFF; // c3=0x00000000 c2=0x00000276
    c2+=c1>>16; c1&=0x0000FFFF; // c2=0x0000027D c1=0x0000220C
    c1+=c0>>16; c0&=0x0000FFFF; // c1=0x0000221D c0=0x00007800
    // propagate 2^16 overflows (normaly to recover from secondary overflow)
    c2+=c1>>16; c1&=0x0000FFFF; // c2=0x0000027D c1=0x0000221D
    c3+=c2>>16; c2&=0x0000FFFF; // c3=0x00000000 c2=0x0000027D
    // (c3,c2,c1,c0) >> _fx32_fract_bits
    u.u16[_l]=c0; u.u16[_h]=c1; c0=u.u32; // c0=0x221D7800
    u.u16[_l]=c2; u.u16[_h]=c3; c1=u.u32; // c1=0x0000027D
    c0 =(c0&_fx32_integ_mask)>>_fx32_fract_bits; // c0=0x0000443A
    c0|=(c1&_fx32_fract_mask)<<_fx32_integ_bits; // c0=0x04FA443A
    return c0; // 0x04FA443A -> 83510330/32768 = 2548.53302001953125
    }
Другие вопросы по тегам