lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Op Do. 4 Apr. 2019 om 23:25 het Egor Skriptunoff
<> geskryf:
> On Thu, Apr 4, 2019 at 2:14 AM Albert Chan wrote:
>> Comes across a fun math puzzle. :-)
>> Design a function cin(X), such that cin(cin(cin(X))) = sin(X)
> The most straightforward approach is
> to build Taylor series of cin(x) one term at a time.
[code snipped]
> This implementation works only if x is in the range from (-0.7) to (+0.7)
> That's because of floating point arithmetic is approximate.
> Exact arithmetic of fractions (with arbitrary long numerator and denominator) must be used instead.

No, the reason is that the convergence radius of the Maclaurin series
is only about 0.7. There are at least two ways around that:

1. Use a nonlinear transformation (epsilon algorithm, Levin's U etc)
to sum the series.
2. Apply analytic continuation. E.g. use this method to calculate cin
and enough derivatives at say pi/6, then calculate a Taylor series
round pi/6, etc.

I can't guarantee that either approach will work. Unfortunately I am
travelling and am typing this in an idle half-hour, so I can't try it
out now.

Problems of this kind are subtle and often have no unique solution.
Additional hypotheses are sometimes needed. The convergence
acceleration method in effect assumes that cin has no singularities
worse than poles near the region of interest. The analytic
continuation approach works if for example cin is analytic in an
ellipse with foci at (0,0) and (2.019,0). There is no reason to
suppose that the two answers will be the same. The very neat trick
which the designer of the puzzle certainly wanted solvers to see, does
not require that cin is analytic anywhere except at 0. This answer may
well be different from the other two.

Personally, I am very fond of the U transform because it produces an
asymptotic series, i.e. the answers initially seem to converge but
then diverge. The user is thus warned that there is some non-polar
singularity or excessive roundoff propagation, and the point where
this happens is merely a "best practical" answer for the given data.

Sorry, we are straying from Lua, but since for example discussions on
finite state machines have been conducted on the list recently, a
little computational complex analysis can't hurt :-)

-- Dirk