Frank Heckenbach frank@g-n-u.de a dit :
da Silva, Joe wrote:
As for my comment about "tweaked" coefficients (for platforms which don't already provide the function), the general rule is that if you truncate an infinite series, you need to "tweak" the coefficient values to provide optimum accuracy for the number of terms you are using. Simply truncating a series may produce inaccurate results, regardless of how many terms you apply. That is the general rule, and I remember it was certainly true with trigonometric functions. However, perhaps this effect is not so prevalent with the "log1p" coefficients?
As I said, I'm no expert on numerics, and I haven't heard of this tweaking.
I suppose that what Joe has in mind is the replacement of a Taylor series by a Tchebychev polynomial. The drawback of a Taylor series is that to have a given accuracy you need only one term at the origin, but a number of terms which increases when you go farther away from the origin of the development. To have the accuracy you need at the farthest point of the development you need a polynomial of too high a degree, and you get in addition problems of roundoff errors when evaluating this polynomial. A Tchebycheff polynomial have a constant accuracy over the whole range of validity, and for a given accuracy over a given range it is of lower degree than any Taylor series based polynomial in the same range. Even better is the use of a rational function (ratio of two polynomials) as is used in the CEPHES library, for the log1p function in particular. However the degree and coefficients of this best polynomial depends both on the interval sought and on the accuracy needed. It is different e.g. for single, double, long double, and you cannot simply truncate a given series to different orders. The situation is even worse for a general purpose compiler like gpc which is aimed to work with different word sizes: 64 bits for real or double for most systems, but may be 128 bits for some. Checks would be needed to select the polynomial to use. It is probably better to let this done when possible by a libc library (or an other specialized library like CEPHES) which knows the particular system for which it is built and selects the order and coefficients of the polynomial accordingly. Gpc should give only a less optimized but the most generally valid solution.
Maurice
Maurice Lombardi wrote:
... snip ...
I suppose that what Joe has in mind is the replacement of a Taylor series by a Tchebychev polynomial. The drawback of a Taylor series is that to have a given accuracy you need only one term at the origin, but a number of terms which increases when you go farther away from the origin of the development. To have the accuracy you need at the farthest point of the development you need a polynomial of too high a degree, and you get in addition problems of roundoff errors when evaluating this polynomial. A Tchebycheff polynomial have a constant accuracy over the whole range of validity, and for a given accuracy over a given range it is of lower degree than any Taylor series based polynomial in the same range. Even better is the use of a rational function (ratio of two polynomials) as is used in the CEPHES library, for the log1p function in particular.
However the degree and coefficients of this best polynomial depends both on the interval sought and on the accuracy needed. It is different e.g. for single, double, long double, and you cannot simply truncate a given series to different orders. The situation is even worse for a general purpose compiler like gpc which is aimed to work with different word sizes: 64 bits for real or double for most systems, but may be 128 bits for some. Checks would be needed to select the polynomial to use. It is probably better to let this done when possible by a libc library (or an other specialized library like CEPHES) which knows the particular system for which it is built and selects the order and coefficients of the polynomial accordingly. Gpc should give only a less optimized but the most generally valid solution.
A good reference for this is Hastings "Approximations for Digital Computers", which I used to own until some #$%&*@ liberated my copy. You are referring to 'error leveled Tchebychev polynomials'. Try a good library.
Maurice Lombardi wrote:
Frank Heckenbach frank@g-n-u.de a dit :
da Silva, Joe wrote:
As for my comment about "tweaked" coefficients (for platforms which don't already provide the function), the general rule is that if you truncate an infinite series, you need to "tweak" the coefficient values to provide optimum accuracy for the number of terms you are using. Simply truncating a series may produce inaccurate results, regardless of how many terms you apply. That is the general rule, and I remember it was certainly true with trigonometric functions. However, perhaps this effect is not so prevalent with the "log1p" coefficients?
As I said, I'm no expert on numerics, and I haven't heard of this tweaking.
I suppose that what Joe has in mind is the replacement of a Taylor series by a Tchebychev polynomial. The drawback of a Taylor series is that to have a given accuracy you need only one term at the origin, but a number of terms which increases when you go farther away from the origin of the development. To have the accuracy you need at the farthest point of the development you need a polynomial of too high a degree, and you get in addition problems of roundoff errors when evaluating this polynomial. A Tchebycheff polynomial have a constant accuracy over the whole range of validity, and for a given accuracy over a given range it is of lower degree than any Taylor series based polynomial in the same range. Even better is the use of a rational function (ratio of two polynomials) as is used in the CEPHES library, for the log1p function in particular. However the degree and coefficients of this best polynomial depends both on the interval sought and on the accuracy needed. It is different e.g. for single, double, long double, and you cannot simply truncate a given series to different orders. The situation is even worse for a general purpose compiler like gpc which is aimed to work with different word sizes: 64 bits for real or double for most systems, but may be 128 bits for some. Checks would be needed to select the polynomial to use. It is probably better to let this done when possible by a libc library (or an other specialized library like CEPHES) which knows the particular system for which it is built and selects the order and coefficients of the polynomial accordingly. Gpc should give only a less optimized but the most generally valid solution.
Yes, that's what we do by using log1p() when available -- provided the libm provides a version for the particular target.
Besides, as I noted, Emil evaluates the series only in a certain interval (|u| < 1/3, i.e. z < 1/9), so the number of terms needed to get the required accuracy is bounded by a constant (the size of the coefficients array). When you say "too high", do you mean this constant is too big? Also, as I said, I can't see why there should be large rounding errors.
Frank
-
CBFalconer -
Frank Heckenbach -
Maurice Lombardi