Board index » delphi » How Does Turbo Pascal Find Sin?

How Does Turbo Pascal Find Sin?

In article <19950612.200505.860472.NETN...@VM.BIU.AC.IL>

Quote
bro...@popeye.cc.biu.ac.il (Brosh Ariel) writes:
>I do think all the compilers use Taylor series, though I would prefer Lagrange
>interpulations.

What's the basis of this claim?  If you trace through the calculation in Turbo
Pascal, you'll see that it bases its calculation on the hardware FPTAN
instruction when using the IEEE types.  I couldn't follow what was going on
when using the Real type, or what the hardware emulator did.

Duncan Murdoch

 

Re:How Does Turbo Pascal Find Sin?


In a previous article, dmurd...@mast.queensu.ca (Duncan Murdoch) wrote:

Quote
>In article <19950612.200505.860472.NETN...@VM.BIU.AC.IL>
>bro...@popeye.cc.biu.ac.il (Brosh Ariel) writes:

>>I do think all the compilers use Taylor series, though I would prefer Lagrange
>>interpulations.

>What's the basis of this claim?  If you trace through the calculation in Turbo
>Pascal, you'll see that it bases its calculation on the hardware FPTAN
>instruction when using the IEEE types.  I couldn't follow what was going on
>when using the Real type, or what the hardware emulator did.

Whatever the heck Borland Pascal does, its a heck of a lot faster than
a Taylor Series (and yes, you remember correctly - I did post something
saying that a former prof of mine said a lot of languages used a Taylor
Series expansion.).  

I tested a Taylor series expansion that I wrote against what BP 7.01 uses
(on a 386 with NO 387 present) - the best I could make it do was 4.5 times
slower than what BP uses.  

Re:How Does Turbo Pascal Find Sin?


Quote
s...@skyfox.usask.ca wrote:

(snip)

Quote

>Whatever the heck Borland Pascal does, its a heck of a lot faster than
>a Taylor Series (and yes, you remember correctly - I did post something
>saying that a former prof of mine said a lot of languages used a Taylor
>Series expansion.).  

>I tested a Taylor series expansion that I wrote against what BP 7.01 uses
>(on a 386 with NO 387 present) - the best I could make it do was 4.5 times
>slower than what BP uses.  

Yes, they probably use something like the minimax polynomial approximation.
(That is the polynomial that minimizes the maximal error for a given degree
over a given interval.) The crux of the matter is, that you can do with a
polynomial of much lower degree than truncated Taylor series expansion, while
guaranteeing a certain accuracy OVER A WHOLE INTERVAL. In this respect Taylor
expansion is notoriously bad, being very accurate in a neighbourhood of the
expansion point, but losing accuracy fast when you move away.
To use the minimax approximation you'd have to calculate the polynomial
coefficients to acceptable precision, but this has been done in the 60's for
all
standard functions. (You'd have to look them up in old "Communications of the
ACM")

Jos.

Re:How Does Turbo Pascal Find Sin?


Quote
s...@skyfox.usask.ca wrote:

: In a previous article, dmurd...@mast.queensu.ca (Duncan Murdoch) wrote:
: >In article <19950612.200505.860472.NETN...@VM.BIU.AC.IL>
: >bro...@popeye.cc.biu.ac.il (Brosh Ariel) writes:
: >

: I tested a Taylor series expansion that I wrote against what BP 7.01 uses
: (on a 386 with NO 387 present) - the best I could make it do was 4.5 times
: slower than what BP uses.  

There are faster ways to calculate with series:  (I know this is
getting off the subject a little...)  There is an infinite product
representation for sin that makes it much quicker to calculate
successive terms.  I have found it to be faster sometimes.

Re:How Does Turbo Pascal Find Sin?


In a previous article, Jos van Kan <j.van...@math.tudelft.nl> wrote:

Quote
>Yes, they probably use something like the minimax polynomial approximation.
>(That is the polynomial that minimizes the maximal error for a given degree
>over a given interval.) The crux of the matter is, that you can do with a
>polynomial of much lower degree than truncated Taylor series expansion, while
>guaranteeing a certain accuracy OVER A WHOLE INTERVAL. In this respect Taylor
>expansion is notoriously bad, being very accurate in a neighbourhood of the
>expansion point, but losing accuracy fast when you move away.
>To use the minimax approximation you'd have to calculate the polynomial
>coefficients to acceptable precision, but this has been done in the 60's for
>all
>standard functions. (You'd have to look them up in old "Communications of the
>ACM")

If you hard-wire or hard-code the degree of the polynomial for a Taylor series
expansion to evaluate, the yes, it will generally lose accuracy as you move
further away from the expansion point.

However, if you have you algorithm go through the polynomial term-by-term until
the desired degree of accuracy is reached, then a Taylor series is probably
more accurate than a minimax polynomial approximation.

For example,  expansion of Sin(X) about Xo = 0 (from my memory -may be wrong)

Sin(X) = 1 - c2 * x^2  + c4 * x^4 - c6 * x^6 + c8 * x^8 - ....

where cN = 1 / N!

If you have evaluated sin(X) up to the term cN * x^N and find that the term
cM * x^M, where M = N+2, is less than or your desired degree of accuracy
then you evaluate no further terms, else add/subtract the order M term
to your result so far and check the order M+2 term.

I have found that doing this using nothing but BP/TP's six byte reals easily
gives accuracy up to 10 or 11 decimal digits - but it is slow.
If I enable 80x87 emulation and uses extendeds for intermediate results, I
put results into the reals that are as accurate as a real can possibly be -
which is 11 or 12 significant decimal digits.

In the post of mine that Jos is responding to, I claimed that the Taylor series
expansion for sin(x) that I tested was 4.5 times slower ON AVERAGE than
what BP/TP uses.  However, I wonder if mine is more accurate?  I'll test this.

Re:How Does Turbo Pascal Find Sin?


Quote
s...@skyfox.usask.ca wrote:

[deletions]

: However, if you have you algorithm go through the polynomial term-by-term until
: the desired degree of accuracy is reached, then a Taylor series is probably
: more accurate than a minimax polynomial approximation.

[more deletions]

No.  One of the things that goes into a minimax polynomial is the
maximum tolerated error ANYWHERE in the range.  You grind through
the procedure and out pops the polynomial.  One of the interesting
properties of such polynomials is that it is guaranteed that there
is no other polynomial with the same or fewer terms with the same
or less accuracy.  In other words, the minimax polynomial is just
that, the MINimum number of terms to give a certiain MAXimum error.

There are other ways to calculate transcendental functions as well.
Rational polynomials are often used for tan(), as they have certain
desireable properties.

Any decent algorithm used in any decent language will have a maximum
fixed error.

   ------ Paul J. Gans  [g...@scholar.chem.nyu.edu]

Re:How Does Turbo Pascal Find Sin?


James B. Millard (jmill...@nmsu.edu) wrote:
Quote
: s...@skyfox.usask.ca wrote:

: : In a previous article, dmurd...@mast.queensu.ca (Duncan Murdoch) wrote:
: : >In article <19950612.200505.860472.NETN...@VM.BIU.AC.IL>
: : >bro...@popeye.cc.biu.ac.il (Brosh Ariel) writes:
: : >

: : I tested a Taylor series expansion that I wrote against what BP 7.01 uses
: : (on a 386 with NO 387 present) - the best I could make it do was 4.5 times
: : slower than what BP uses.

: There are faster ways to calculate with series:  (I know this is
: getting off the subject a little...)  There is an infinite product
: representation for sin that makes it much quicker to calculate
: successive terms.  I have found it to be faster sometimes.

--
------------

"Bilbo Buggins Lives" (unknown)

   Sunny

Re:How Does Turbo Pascal Find Sin?


James B. Millard (jmill...@nmsu.edu) wrote:
Quote
: s...@skyfox.usask.ca wrote:

: : In a previous article, dmurd...@mast.queensu.ca (Duncan Murdoch) wrote:
: : >In article <19950612.200505.860472.NETN...@VM.BIU.AC.IL>
: : >bro...@popeye.cc.biu.ac.il (Brosh Ariel) writes:
: : >

: : I tested a Taylor series expansion that I wrote against what BP 7.01 uses
: : (on a 386 with NO 387 present) - the best I could make it do was 4.5 times
: : slower than what BP uses.

: There are faster ways to calculate with series:  (I know this is
: getting off the subject a little...)  There is an infinite product
: representation for sin that makes it much quicker to calculate
: successive terms.  I have found it to be faster sometimes.

You can use Horner's algorithm to evalute polynomials in minimum of muls/adds
It goes something like this:

--

p(x) = a(n)x^n + ... + a(0)

   y = a(n)
   z = a(n)

   for j = n-1 downto 1:
      y=x*y+a(j)
      z=x*z+y

    y=x*y+a(0)

  return y,z

where :
   P(x) = y
   P'(x) = z

this plus the fact that min-max algorithms require polynomials of much lesser degree will do the trick.

------------

"Bilbo Buggins Lives" (unknown)

   Sunny

Other Threads