DEMO.DESIGN FAQ


следующий фpагмент (2)- [56] Available echoes... (2:5030/84) ------------------------- RU.ALGORITHMS -
 Msg  : 19 of 22                                                                
 From : Oleg Grynchyshyn                    2:463/400.19    20 May 96  23:48:00 
 To   : Vadim Gaponov (Solў)                                                    
 Subj : Десятичные логаpифмы                                                    
--------------------------------------------------------------------------------
Хелло Вам!

Пятница Май 17 1996 22:05, Vadim Gaponov (Solў) писал(а/о) Roman Rusakov а я
подглядел:

Можешь попробовать мой алгоритм. Он взят с библиотеки действительных чисел
произвольной точности.

=== Cut ===
Real log2(rcReal yy)
{
 Real y(yy);
 if (y <= Real::zero) THROW_OBJ(xMath(xMath::ArgumentIsOutOfRange));
 Real ret(Real::zero, y.len);

 upart test = y.ptr[y.len - 1];
 for (short sh = 0; test != 1; sh ++) test >>= 1;
 _shiftRight(y.ptr, y.len, y.pow, sh);
 long ypow = y.pow; y.pow = 0;
 for (short i = ret.len - 1; i >= 0; i --)
  for (ushort j = 0; j < _bits_in_part; j ++)
   if ((y *= y) >= Real::two)
   {
    _shiftRight(y.ptr, y.len, y.pow, 1);
    ret.ptr[i] |= (_hi_bit >> j);
   }
 ret.pow = -1;
 return ret.norm() + Real(ypow * _bits_in_part + sh, 2);
}

Real log(rcReal x)
{
 return log2(x) / Real(Real::LOG2_E, x.len);
}
=== Cut ===

следующий фpагмент (3)|пpедыдущий фpагмент (1)- [38] Talks about assembler (2:5030/84) --------------------------- TALKS.ASM -
 Msg  : 8 of 13                                                                 
 From : Dmitry M. Golubovsky                2:5030/163.22   20 Sep 95  22:13:00 
 To   : Vadim Gurov                                                             
 Subj : ?                                                                       
--------------------------------------------------------------------------------
Hello Vadim!

19 Sep 95 18:46, Vadim Gurov wrote to All:


 VG>  Вот появилась следующая задача:
 VG>   al = 2 в степени al; и наоборот al = log al
 VG>                                           ¤
 VG>  То есть, если, например, AL=2, то нада получить AL=00000100b
 VG>                 или если  AL=00001000b, то нада AL=3

Первое решается обыкновенным сдвигом.

Второе - чуть сложнее:

log2al: movzx   eax,al                  ;необязательно но желательно
        bsf     eax,eax                 ;ищем бит с начиная с нулевого
        jz      short l1                ;Z - есть такой бит, иначе al=0
        mov     eax,-1                  ;или что-нибудь такое для
                                        ;идентификации -бесконечности
l10:    ret                             ;здесь имеется искомое число

Есть здесь конечно недостаток - будет найден только младший установленный бит
и не будут отловлены числа, не являющиеся степенями 2. Hо в исходном задании
ничего не сказано, как себя вести, если несколько бит установлено. Поэтому -
"Зависит от реализации"

Sincerely yours Dmitry M. Golubovsky

--- GoldED 2.42.G0214
 * Origin: ---> DMG - ITL <--- (2:5030/163.22)
следующий фpагмент (4)|пpедыдущий фpагмент (2)
- [38] Talks about assembler (2:5030/84) --------------------------- TALKS.ASM -
 Msg  : 13 of 13                                                                
 From : Nick Velitchko                      2:5020/463.27   22 Sep 95  20:37:00 
 To   : Vadim Gurov                                                             
 Subj : Re: ?                                                                   
--------------------------------------------------------------------------------
        Hello, Vadim!

Тут как-то 19 Sep 95 около 17:46, Vadim Gurov (2:5030/143.17) писал к All:

 VG>  Вот появилась следующая задача:
 VG>   al = 2 в степени al; и наоборот al = log al
 VG>                                           ¤
 VG>  То есть, если, например, AL=2, то нада получить AL=00000100b
 VG>                 или если  AL=00001000b, то нада AL=3

1)
        mov     cl,1
        xchg    al,cl
        shl     al,cl
2)
        mov     cl,8
@@loop: shl     al,1
        dec     cl
        jnbe    @@loop          ; log2(0)=0
        mov     al,cl

P.S. Hе проверял, так что если что не так, ногами не бить...

                                                Bye!
                                                     Nick.
---
 * Origin: The MKB BBS +7 (095) 926-4687 work time 21.00-08.00 (2:5020/463.27)

следующий фpагмент (5)|пpедыдущий фpагмент (3)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 135 of 185                                                              
 From : rgreen@ea.com                       2:5030/315      14 Nov 95  11:01:52 
 To   : All                                                 17 Nov 95  06:35:26 
 Subj : Re: Problem: Calcing log from simple math                               
--------------------------------------------------------------------------------
X-RealName: Robin Green

In article <488v20$12lk@stealth.mindspring.com>, sjledet@ledet.com. says...

>
>This is a math exercise with some real world application. The new
>LiveScript programming language built into Netscape 2.0 has just the
>following arithmetic operators:

The book you need is:

  "Methods and Programs for Mathematical Functions", Stephen
  L. Moshier, (pub.) Ellis Horwood, 1989, ISBN 0-7458-0289-3

The algorithm is about two pages long but falls through very fast and
has a peak error of 1.1*10^-16 for IEEE doubles.

If you have a number 'x' which is seperable into exponant k and
significand f then given:

  x = f * 2^k  where 0.5 <= f < 1.0

  log(x) = log(2^k * f)
         = log(f) + k log(2)

given that |k|>2 then log() can be calculated by:

  log(x) = 2(x-1)/(x+1) +
           2/3((x-1)(x+1))^3 +
           2/5((x-1)(x+1))^5 + ...

Here's the algorithm:

You can gain more accuracy by transforming f from the interval [0.5,1.0)
to the interval [ 1/sqrt(2), sqrt(2) ) by:

  if(f < 1/sqrt(2))   /* 1/sqrt2 == 0.7071067812 */
     z = (f - 0.5) / (0.5 + 0.5 * (f - 0.5))
     k = k - 1        /* there was a *2 above, so re-jig the exp.)
  else
     z = (f-1)/(0.5 * f + 0.5)

next, approximate the log of f by:


  log(f) ~= z + z^3 * (R(z^2))/(S(z^2))

  where:

  R(t) = -0.789580278884799154124 * t^2 +
         +1.63866645699558079767  * t   +
         -6.41409952958715622951

  S(t) = +1.00000000000000000000 * t^3 +
         -3.56722798256324312549 * t^2 +
         +312.093766372244180303 * t   +
         -769.691943550460008604

and finally recombine it all using:

  log(x) ~= (log(f) - 0.0002121944400546905827679 * k) +
            0.693359375 * k

Phew! got there. I hope these values are right. Basically, get the
book, it's well worth it.

следующий фpагмент (6)|пpедыдущий фpагмент (4)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 136 of 185                                                              
 From : randraka@ids.net                    2:5030/315      15 Nov 95  01:14:08 
 To   : All                                                 17 Nov 95  06:35:26 
 Subj : Re: Problem: Calcing log from simple math                               
--------------------------------------------------------------------------------
X-RealName: Ray Andraka

sjledet@ledet.com (Sterling Ledet) wrote:

>

Logs can be computed using shifts and adds plus a few constants
(one per iteration).  The algorithm is a CORDIC style algorithm,
which is simply an iterative approach.  The equations needed to
compute a log in any base are:

  F[i+1] = F[i] + d[i]*F[i]*2^(-i)

and   X[i+1] = X[i] + d[i]*Log(1+2^(-i))

where   d[i] = 1 if F[i+1]<C  or 0 otherwise,
  Log(1+2^(-i)) is read from a table
  C is the input value (a)
  X[0] = 0
  F[0] = 1
  X[n] = Log(C/F[0])

The result is valid for input ratios between 1 and the sum of
the entries in the table.

This algorithm is derived from the incremental expression of the
exponential, b^(x+dx) = b^x * b^(dx), which can be restated as
b^(x+dx)=b^x + b^x * 2^(-i) if b^(dx)=1+2^(-i).  The base of the
Log is determined by the base of the entries in the table.

This algorithm can be reversed to obtain exponentials as well!

I've designed hardware to accomplish this algorithm as well as other CORDIC
algorithms including trig, inverse trig, hyperbolic trigs and their inverses,
square roots, vector rotations and magnitude.  All these use only
shifts, adds and small look-up tables (no more than 16 values each)

-Ray Andraka
Chairman, the Andraka Consulting Group
401/884-7930   FAX 401/884-7950
email randraka@ids.net

The Andraka Consulting Group is a digital hardware design firm specializing
in high performance FPGA designs.  Services include complete design,
development,
simulation, and integration of these devices and the surrounding circuits.  We
also evaluate,troubleshoot, and improve existing designs. Please call or write
for a free brochure.
следующий фpагмент (7)|пpедыдущий фpагмент (5)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS -
 Msg  : 144 of 185                                                              
 From : buller@bnr.ca                       2:5030/315      14 Nov 95  14:59:52 
 To   : All                                                 17 Nov 95  06:35:34 
 Subj : Re: Problem: Calcing log from simple math                               
--------------------------------------------------------------------------------
X-RealName: Jon Buller

>

If all you need is: floor (log2 ((int)x)) then I suggest something like:

int fl2 (int x) {
    int i = 0;

    if (x <= 0) return (-1);
    while (i = 0; x != 0; i++) x >>= 1;
    return (i);
} /* this is off the top of my head, so it most likely has big stupid bugs */


If you really need a full floating point logarithm, try a power series.  It's
what your C libraries use, since most (or more likely all) computers don't
have a log instruction.

Jon Buller
Всего 6 фpагмент(а/ов) |пpедыдущий фpагмент (6)

оглавление \| demo party в ex-СССР \| infused bytes e-mag \| новости от ib/news \| другие проекты \| письмо \|	win koi lat