Board index » delphi » Need fast replacement for cos()

Need fast replacement for cos()

Hi all,

I'm in need for a fast replacement for the cos-function in the
range from -pi/2 to pi/2. Accuracy is not so importrant, as long as
the error is less than 1% and the curve is smooth. I figured out
that a representation of the form
  1 - a * x**2 + b * x**4
is good.

Now I need a fast implementation for the above, usable with borland
pascal where x is single and no numeric coprocessor is required.

--
=============================================================================
Dipl. Phys. Hans L. Trautenberg                       Universitaet Regensburg
                           Institut fuer Experimentelle und Angewandte Physik
phone (49) 941 943 2466                                         Polymerphysik
fax   (49) 941 943 3196                                    D-93040 Regensburg
e-mail  hans.trautenb...@physik.uni-regensburg.de                     Germany

privat
phone (49) 941 949211                                             Flurstr. 14
fax   (49) 941 930792                                            D-92348 Berg
                                                                      Germany
=============================================================================

 

Re:Need fast replacement for cos()


Why not just use a table look-up?

Re:Need fast replacement for cos()


Quote
H?kan Bergzn (hakan.berg...@telub.se) wrote:

: Why not just use a table look-up?

The problem with the look-up table is that the resulting curve
is not smooth, and smoothness is very important.

--
=============================================================================
Dipl. Phys. Hans L. Trautenberg                       Universitaet Regensburg
e-mail  hans.trautenb...@physik.uni-regensburg.de                     Germany
=============================================================================

Re:Need fast replacement for cos()


In article <41rtq3$...@rrzs3.uni-regensburg.de>, c4140@rphs45 (Hans Trautenberg t2466) writes:

Quote

> I'm in need for a fast replacement for the cos-function in the
> range from -pi/2 to pi/2. Accuracy is not so importrant, as long as
> the error is less than 1% and the curve is smooth. I figured out
> that a representation of the form
>   1 - a * x**2 + b * x**4
> is good.

> Now I need a fast implementation for the above, usable with borland
> pascal where x is single and no numeric coprocessor is required.

  Like this: 1-a*sqr(X)+b*sqr(sqr(x)) ?
  --Lars M.

Re:Need fast replacement for cos()


c4140@rphs45 (Hans Trautenberg t2466) wrote:

Quote
>Hi all,

>I'm in need for a fast replacement for the cos-function in the
>range from -pi/2 to pi/2. Accuracy is not so importrant, as long as
>the error is less than 1% and the curve is smooth. I figured out
>that a representation of the form
>  1 - a * x**2 + b * x**4
>is good.

>Now I need a fast implementation for the above, usable with borland
>pascal where x is single and no numeric coprocessor is required.

Using your form one can obtain an accuracy of 0.0007 across the interval
[-pi/2, pi/2] with

cos (x) ~ 0.995 - 0.4995 x^2 + 0.0367 x^4

If you program that straightforward

function MyCos (x:real):real;
begin
   x:= sqr(x);
   MyCos := 0.995 + x*(-0.4995 + 0.0367 * x)
end;

you achieve a speedup of a factor 3 with respect to the library cosine.
(if you DONT use the 80x87, otherwise its only a factor 2)
If you do not need that accuracy (you say 1%, but I suppose you mean +/- 0.01)
then you can do better than that by dividing the interval between
[0,1] and [1,\pi/2] (I'll assume x positive)

function MyFastCos (x:real) : real;
begin
   if (x>1) then
       MyFastCos := 0.955 * (pi/2 - x)
   else
       MyFastCos := 0.995 - 0.46 * x * x;
end;

This gets you another speedup factor of two. (Accuracy drops to 0.01 though)
Maybe there's somewhat more to be gained by using integer arithmetic.

Jos.

Re:Need fast replacement for cos()


In article <41rtq3$...@rrzs3.uni-regensburg.de>, c4140@rphs45 says...

Quote

>Hi all,

>I'm in need for a fast replacement for the cos-function in the
>range from -pi/2 to pi/2. Accuracy is not so importrant, as long as
>the error is less than 1% and the curve is smooth. I figured out
>that a representation of the form
>  1 - a * x**2 + b * x**4
>is good.

Why not use a lookup table? Can't get any faster than that.

Re:Need fast replacement for cos()


Jos van Kan (j.van...@math.tudelft.nl) wrote:

: Using your form one can obtain an accuracy of 0.0007 across the interval
: [-pi/2, pi/2] with

: cos (x) ~ 0.995 - 0.4995 x^2 + 0.0367 x^4

: If you program that straightforward

: function MyCos (x:real):real;
: begin
:    x:= sqr(x);
:    MyCos := 0.995 + x*(-0.4995 + 0.0367 * x)
: end;

: you achieve a speedup of a factor 3 with respect to the library cosine.
: (if you DONT use the 80x87, otherwise its only a factor 2)

: Maybe there's somewhat more to be gained by using integer arithmetic.

I store my arguments of the cosine as longints with
  2^32  =  pi,
     0  =  0,
-(2^32) = -pi

So what would be the best implementation of the function above with
this representation of the argument?

Thanks in advance for any help.

--
=============================================================================
Dipl. Phys. Hans L. Trautenberg                       Universitaet Regensburg
                           Institut fuer Experimentelle und Angewandte Physik
phone (49) 941 943 2466                                         Polymerphysik
fax   (49) 941 943 3196                                    D-93040 Regensburg
e-mail  hans.trautenb...@physik.uni-regensburg.de                     Germany

privat
phone (49) 941 949211                                             Flurstr. 14
fax   (49) 941 930792                                            D-92348 Berg
                                                                      Germany
=============================================================================

Re:Need fast replacement for cos()


In article <41v0fl$...@gyda.ifi.uio.no> lar...@ifi.uio.no (Lars Marius Garshol) writes:

Quote
>In article <41rtq3$...@rrzs3.uni-regensburg.de>, c4140@rphs45 (Hans
Trautenberg>t2466) writes:
>> I'm in need for a fast replacement for the cos-function in the
>> range from -pi/2 to pi/2. Accuracy is not so importrant, as long as
>> the error is less than 1% and the curve is smooth. I figured out
>> that a representation of the form
>>   1 - a * x**2 + b * x**4
>> is good.
>> Now I need a fast implementation for the above, usable with borland
>> pascal where x is single and no numeric coprocessor is required.
>  Like this: 1-a*sqr(X)+b*sqr(sqr(x)) ?

or Y := sqr(X) ; Fn := 1 - (p-q*Y)*Y ; ?

--
John Stockton : mailto:J...@dclf.npl.co.uk from off-site.  MIME.  WP.
 National Physical Laboratory, Teddington, Middlesex, TW11 0LW, UK
  Direct Phone +44 181-943 6087, Nearby Fax +44 181-943 7138  
   Postings out, Email in/out are fast.  Offshore news takes 0..10+
    days to arrive; please mail me a copy of non-UK followups!  
     Regret system puts unzoned (UK civil) time on messages.

Re:Need fast replacement for cos()


: The problem with the look-up table is that the resulting curve
: is not smooth, and smoothness is very important.

 A look up table is as smooth as you want, as long as you pre-calculate
enough values. Correct?

Re:Need fast replacement for cos()


Quote
>Jos van Kan (j.van...@math.tudelft.nl) wrote:

>: Using your form one can obtain an accuracy of 0.0007 across the interval
>: [-pi/2, pi/2] with

>: cos (x) ~ 0.995 - 0.4995 x^2 + 0.0367 x^4

Sorry, two typo's here:
   cos (x) ~ 0.9995 - 0.4955 x^2 + 0.0367 x^4

Quote

>: If you program that straightforward

>: function MyCos (x:real):real;
>: begin
>:    x:= sqr(x);
>:    MyCos := 0.995 + x*(-0.4995 + 0.0367 * x)

And here too   0.9995     -0.4955

Quote
>: end;

>: you achieve a speedup of a factor 3 with respect to the library cosine.
>: (if you DONT use the 80x87, otherwise its only a factor 2)

Jos.

Re:Need fast replacement for cos()


Quote
Dan Peori (pe...@news.isisnet.com) wrote:

: : The problem with the look-up table is that the resulting curve
: : is not smooth, and smoothness is very important.

:  A look up table is as smooth as you want, as long as you pre-calculate
: enough values. Correct?

If you pre-calculate enough values you need a lot of memmory, and memmory
is limited in real mode. And I have to use real mode.

--
=============================================================================
Dipl. Phys. Hans L. Trautenberg                       Universitaet Regensburg
e-mail  hans.trautenb...@physik.uni-regensburg.de                     Germany
=============================================================================

Re:Need fast replacement for cos()


See below: my first idea was also a lookup table, but what I found was:

The  Trunc() or Round() operations needed to index into the lookup table were
just as slow as computing the Cosine (under emulation).

Anyone know a QUICK method of generating an integer from a real ?

In article <41v6u7$...@sparky.midwest.net> rwp...@ldd.net (R W Pick) writes:

Quote
>>I'm in need for a fast replacement for the cos-function in the
>>range from -pi/2 to pi/2. Accuracy is not so importrant, as long as
>>the error is less than 1% and the curve is smooth. I figured out
>>that a representation of the form
>>  1 - a * x**2 + b * x**4
>>is good.
>Why not use a lookup table? Can't get any faster than that.

Re:Need fast replacement for cos()


c4140@rphs45 (Hans Trautenberg t2466) writes:

Quote
>Dan Peori (pe...@news.isisnet.com) wrote:
>: : The problem with the look-up table is that the resulting curve
>: : is not smooth, and smoothness is very important.
>:  A look up table is as smooth as you want, as long as you pre-calculate
>: enough values. Correct?
>If you pre-calculate enough values you need a lot of memmory, and memmory
>is limited in real mode. And I have to use real mode.

Try it like this: Use a pre-calculated table with more than 100 values. Keep
in mind that you only have to store the values from cos(0) up to cos (pi/2)
because all the other values can be gained by using the symmetrie-properties
of the cos function. Then calculate the value you need by spline-interpolation
and I think you will be confident!

If you need more hints, ask me!

Joerg.

------------------------------------------------------------------------------
Cand. phys. Joerg Kunze
Institute for Aplied Physics
Christian-Albrechts-University
Ohlshausenstr. 40-60
D-24098 Kiel
jo...@ang-physik.uni-kiel.de
------------------------------------------------------------------------------

Re:Need fast replacement for cos()


In article <DE2qsC....@dutiws.twi.tudelft.nl>, Jos van Kan <j.van...@math.tudelft.nl> says:

Quote

>c4140@rphs45 (Hans Trautenberg t2466) wrote:
>>Hi all,

>>I'm in need for a fast replacement for the cos-function in the
>>range from -pi/2 to pi/2. Accuracy is not so importrant, as long as
>>the error is less than 1% and the curve is smooth. I figured out
>>that a representation of the form
>>  1 - a * x**2 + b * x**4
>>is good.

>>Now I need a fast implementation for the above, usable with borland
>>pascal where x is single and no numeric coprocessor is required.

The absolute fastest way is creating a table, eg.
var
  arCos: array [-314..314] of Real;
function FastCos(Omega: Real): Real;
  begin
    FastCos := arCos[100 * Round(Omega)];
  end;

You'll need to init arCos, eg:
procedure InitFastCos;
  var
    cCos: Integer;
  begin
    for cCos := -314 to 314 do
      arCos[cCos] := Cos(cCos / 100);
    end;

arCos takes about 3K of your datasegment. Since you allow a 1% error,
you can consider creating an array of ShortInts, and dividing the result by
127:

var
  arCos: array [-314..314] of ShortInt;
function RealFastCos(Omega: Real): Real;
  begin
    FastCos := arCos[100 * Round(Omega)] / 127;
  end;

arCos will now take 629 bytes.
BTW you can win some extra clockcycles by changing the 100 to 128, and
changing the arraybounds accordingly. BP multiplies Integers faster when
the multiplier is a power of 2.

Bye,
Zweitze.

Re:Need fast replacement for cos()


Go to page: [1] [2]

Other Threads