• April 19, 2021, 06:17:55 PM

Login with username, password and session length

Author Topic:  Round-off errors in polynomial evaluation  (Read 883 times)

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • 3d
  • ****
  • Posts: 953
Re: Round-off errors in polynomial evaluation
« Reply #15 on: May 07, 2020, 09:37:29 PM »
It seems the outside of the M-set is recursively enumerable but not recursive, which means you can verify algorithmically that a point that is outside is in fact outside, but you can't do that for any point inside.
I don't understand - the period-2 bulb is known in area and position - and can be considered algorithmically verified. And all the true shape Msets laserblaster and I are computing right now via interval arithmetics and cell-mapping are verified as well as the seed intervals enter a cycle for the interior. Given enough time and computer power, in principle every small square can be verified whether it lies fully in the interior of a hyperbolic component or fully outside the Mset (not allowed to touch the boundary itself though).

Or is there a definition of computability that collides with what I naively assume computability means? Or maybe there is more "interior" than just the hyperbolic components, wherever that then lies.

Offline gerrit

  • 3f
  • ******
  • Posts: 2402
Re: Round-off errors in polynomial evaluation
« Reply #16 on: May 07, 2020, 11:04:38 PM »
I don't understand - the period-2 bulb is known in area and position - and can be considered algorithmically verified. And all the true shape Msets laserblaster and I are computing right now via interval arithmetics and cell-mapping are verified as well as the seed intervals enter a cycle for the interior. Given enough time and computer power, in principle every small square can be verified whether it lies fully in the interior of a hyperbolic component or fully outside the Mset (not allowed to touch the boundary itself though).

Or is there a definition of computability that collides with what I naively assume computability means? Or maybe there is more "interior" than just the hyperbolic components, wherever that then lies.
What about a square that's both in and out?

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 117
Re: Round-off errors in polynomial evaluation
« Reply #17 on: May 07, 2020, 11:29:21 PM »
It would make sense if Penrose meant points in the set, rather than interior points.

Offline gerrit

  • 3f
  • ******
  • Posts: 2402
Re: Round-off errors in polynomial evaluation
« Reply #18 on: May 08, 2020, 12:04:44 AM »
It would make sense if Penrose meant points in the set, rather than interior points.
Yes.

Offline marcm200

  • 3d
  • ****
  • Posts: 953
Re: Round-off errors in polynomial evaluation
« Reply #19 on: May 08, 2020, 08:31:27 AM »
@gerrit: What about the following: A whole square that straddles the Mset (so not just touching). Run a thread with the CM/IA algorithm for 5 sec for that square. Then divide the initial square in 4 identical small ones, and let now 5 threads run for another 5 seconds. Then divide every square again and go on. As the inital square straddles truely, at one finite point a (very small) square is fully inside the Mset and one is fully outside, so the algorithm knows the initial square had both interior and exterior and can stop. However that would leave the case where the initial square touches the Mset.

Some points on the x-axis are verified and so are all the boundary points of the period 1-4 as explicit formulas exist and can be symbolically solved.

But maybe the notion is "there's (not yet) an algorithm to judge a general point" - and that reminds me of the halting problem in computer science: No general agorithm exists, but there might very well be one that could prove e.g. that any C++ compiler with no more than 1000 lines of code halts on every input.

Offline gerrit

  • 3f
  • ******
  • Posts: 2402
Re: Round-off errors in polynomial evaluation
« Reply #20 on: May 08, 2020, 06:01:23 PM »
But maybe the notion is "there's (not yet) an algorithm to judge a general point" - and that reminds me of the halting problem in computer science: No general agorithm exists, but there might very well be one that could prove e.g. that any C++ compiler with no more than 1000 lines of code halts on every input.
Yes, the conjecture is "there is no halting algorithm that you input a single c and it tells you in M-set or not". c is assumed "computable" meaning there is an algorithm that computes digit after digit of c. For if c itself is uncomputable (like Chaitin's number) it's trivial. The discussion in Penrose's book is in context of Goedel theorem and Turing halting problem. So the idea is there is no better way than to iterate and hope it either converges or diverges but if neither it may stay bounded forever or not, no way to know.

Of course there is a better way, using human creativity. As trivial example if c is in main cardioid there is a better way than to iterate forever and give up: just prove it's inside the cardioid which has a simple computable shape. For pretty much any non-escaping orbit you compute you can figure out in which cardioid or pseudo-circle blob it is and then prove it's inside by solving a polynomial equation which is computable. So the non-computable points must be on the boundary. Penrose can't give an example of a non computable point. At least that's my summary of the book chapter, I hope I got it all right; the chapter is written as "computability for dummies" so I hope I'm not worse than dumb.

The paper Claude pointed at  defines "computability" in a more productive way AFAICU and seems to show M-set is computable in the sense you can make more and more accurate pictures of it and you can actually give guarantees on accuracy. But you already know that and are doing it.

Would be nice to come up with an algorithm (like an infinite series) that calculates a c such that no-one can figure out it it's in M or not. Proving uncomputability is an open problem so that would be too much to ask. Something like the first trancendental numbers that were proven; they were defined with an infinite series constructed explicitly so you can prove trancendentality.

Maybe pauldelbrot can come up with such a thing, at least I've never been able to ask a math question here that he could not answer :)

Offline hobold

  • Fractal Frogurt
  • ******
  • Posts: 419
Re: Round-off errors in polynomial evaluation
« Reply #21 on: May 08, 2020, 09:39:45 PM »
Random tidbit of useless information: the definition of "computability" is older than data processing machines. It used to mean a somewhat abstract thing. Then came computer science and overloaded the term with a more practical definition. It is possible to find a whole range of scientific papers with definitions inbetween these two ends (depending on what kind of abstract or concrete machine a paper is working with).

The meaning will shift again if and when quantum computers become relevant.

Offline gerrit

  • 3f
  • ******
  • Posts: 2402
Re: Round-off errors in polynomial evaluation
« Reply #22 on: May 08, 2020, 11:59:20 PM »
Random tidbit of useless information: the definition of "computability" is older than data processing machines. It used to mean a somewhat abstract thing. Then came computer science and overloaded the term with a more practical definition. It is possible to find a whole range of scientific papers with definitions inbetween these two ends (depending on what kind of abstract or concrete machine a paper is working with).

The meaning will shift again if and when quantum computers become relevant.
Good point, I thought computable alywas means Turing computable which includes quantum computers. Some more random reading in the Penrose book: if x is a computable real x==1? is uncomputable (undecidable) in general. For if your algorithm has computed 0.99..99 with a trilion 9's the trillionandoneth digit could be 8. So in this sense the unit circle is also not computable. Also in a foornote he writes someone told him non-computability of M-set was actually proven but no reference given.

I guess we're digressing far from rounding errors in polynomial evaluation...

Online Adam Majewski

  • Fractal Frogurt
  • ******
  • Posts: 467
Re: Round-off errors in polynomial evaluation
« Reply #23 on: July 04, 2020, 07:39:49 AM »
Would be nice to come up with an algorithm (like an infinite series) that calculates a c such that no-one can figure out it it's in M or not. Proving uncomputability is an open problem so that would be too much to ask. Something like the first trancendental numbers that were proven; they were defined with an infinite series constructed explicitly so you can prove trancendentality.

What about similar case :

https://en.wikibooks.org/wiki/Fractals/Mathematics/Numerical#Test

If one have a year to check one point it is practicaly uncomputable

Offline gerrit

  • 3f
  • ******
  • Posts: 2402
Re: Round-off errors in polynomial evaluation
« Reply #24 on: July 04, 2020, 10:06:33 PM »
If one have a year to check one point it is practicaly uncomputable
Get a faster machine and do it in 1 hr. There is no such thing as "practically uncomputable".

Offline 3DickUlus

  • Administrator
  • *******
  • Posts: 2193
    • Digilantism
Re: Round-off errors in polynomial evaluation
« Reply #25 on: July 04, 2020, 11:22:42 PM »
Impractical to compute, but not un-computable.

Offline marcm200

  • 3d
  • ****
  • Posts: 953
Re: Round-off errors in polynomial evaluation
« Reply #26 on: April 12, 2021, 11:06:17 AM »
Computing some Newton maps for polynomials for the period-5 (and divisor) hyperbolic centers of the  quadratiuc Mset (degree 16, evaluated in iterative form), it's interesting how qualitatively different the outcome is, given  a specific number type.

Left is double precision, there are hardly any (green) points Newton-converging to the hyperbolic center (red square in the image's center. The period-5 cardioid at -1.6254137262130523567 is overlayed onto the Newton map in blue). Those splattered points look like numerical artefacts`.

Middle is long double and it now looks like there might be circular structures having a more or less complicated boundary (spikes). The splattered green gets more dense, so might not be an artefact after all.

And _float128 suggests that almost the entire image will finally be inside an attraction basin for the hc (and probably is part of the immediate basin). The only remaining structure is the one on the far left. But maybe that will vanish too later.


clip
A Round Thing

Started by Bill Snowzell on Fractal Image Gallery

2 Replies
227 Views
Last post March 09, 2018, 09:55:20 AM
by Bill Snowzell
xx
CPU: order of evaluation of an arithmetic expression

Started by marcm200 on Programming

5 Replies
325 Views
Last post February 12, 2020, 09:35:38 AM
by hobold
xx
Several Problems / Errors

Started by PMH on Kalles Fraktaler

5 Replies
482 Views
Last post December 07, 2017, 04:43:37 PM
by PMH
xx
compile errors with release 2-2.13.

Started by piotrv on Mandelbulber

3 Replies
385 Views
Last post April 01, 2018, 07:42:03 AM
by buddhi
xx
Errors when trying to upload video

Started by LionHeart on Forum Help And Support

6 Replies
262 Views
Last post April 13, 2020, 02:36:08 AM
by LionHeart