(Question) Newton Raphson - how long wilt it run ?

  • 13 Replies
  • 325 Views

0 Members and 1 Guest are viewing this topic.

Offline CFJH

  • *
  • Fractal Furball
  • ***
  • Posts: 286
« on: May 11, 2019, 01:38:20 PM »
Hallo

I', running a Newton-Raphson-Zoom on the following location (Attachment)
Until now, the computer is running 2 month. Current Display in kf is "Newton-Raphson 18 / 4%"
Is it possible, to approximate the still needed time to finish (I need to reboot the pc for installation) ?
Is it possible to set a "save point" ?
kf-version is 14.4 on opensuse linux via wine. CPU is a i7-2600.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1779
« Reply #1 on: May 11, 2019, 08:09:26 PM »
Hallo

I', running a Newton-Raphson-Zoom on the following location (Attachment)
Until now, the computer is running 2 month. Current Display in kf is "Newton-Raphson 18 / 4%"
Is it possible, to approximate the still needed time to finish (I need to reboot the pc for installation) ?
Is it possible to set a "save point" ?
kf-version is 14.4 on opensuse linux via wine. CPU is a i7-2600.
NR in KF takes about log2(log10(zoom)) iterations, which is fairly accurate in my experience.

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1214
    • mathr.co.uk
« Reply #2 on: May 14, 2019, 12:31:31 AM »
Is it possible to set a "save point" ?
only by running KF in a VM and snapshotting the whole VM.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1779
« Reply #3 on: May 14, 2019, 07:44:37 AM »
Is the cubic Halley's method worth considering for extremely deep NR zooms?
Usually  the extra cost of evaluating f'' is not worth it and most Newton iterations iterate just a few times.

But for deep KF zoom (say 1e30000) we need something like 15 iterations. With a cubic convergence that would be only 10 which would save about 3 weeks in the example of this thread.

And in this case the main cost of each iteration is the full-precision orbit (z) whereas the derivative(s) can be done in normal precision (with floatexp probably) so the usual downside of Halley doesn't apply.

Update is \( -1/(\frac{f'}{f} -\frac{f''}{2f'}) \).

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1214
    • mathr.co.uk
« Reply #4 on: May 14, 2019, 02:16:36 PM »
the derivative(s) can be done in normal precision
Really?  At least for Newton's method, doing the derivative in machine precision means at most 53 bits are added to the correct portion each time, instead of doubling the number of correct bits.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1779
« Reply #5 on: May 14, 2019, 04:15:55 PM »
Really?  At least for Newton's method, doing the derivative in machine precision means at most 53 bits are added to the correct portion each time, instead of doubling the number of correct bits.
That kills the idea. Can you explain why?

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1214
    • mathr.co.uk
« Reply #6 on: May 14, 2019, 04:39:25 PM »
I think I worked it out once before with help from IRC or M.SE or so, can't remember the details but I started from z → z - f / (f' (1+e)) where e = O(2-53)

If this is wrong, and the derivative really can be calculated in low precision, NR in KF could be made more efficient (CPU time, wall-clock time still limited by the Z orbit)

Even with high precision needed, higher order methods may be faster (wall-clock time reduced due to fewer root-finding steps) because of potential for concurrent evaluation of parts of the formula (total CPU time may be higher)

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1779
« Reply #7 on: May 14, 2019, 04:54:55 PM »
I was going to edit my post as it became obvious that you're right after breakfast, but you beat me to it.
Error in f/f' is determined by the most inaccurate one, of course.

So that was a bad idea but yours is good I think: If you can calculate f'' in full precision on another processor it could work.

Halley method works by locally approximating the function by an order (1,1) rational function (Pade approximant) which has 3 coefficients.

From experiments in Newton-Hines thread it seems Halley has smaller basins of attraction; I should try it on a "Mandelbrot polynomial".
« Last Edit: May 14, 2019, 05:08:16 PM by gerrit »

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1214
    • mathr.co.uk
« Reply #8 on: May 14, 2019, 05:07:00 PM »
Here is a table I just calculated.  First number is bits of accuracy in f', second number is number of steps required to converge, for the function z^2+c iterated 3 times starting from -2 (real only)

(1,33)
(2,24)
(3,18)
(4,15)
(5,12)
(6,11)
(7,10)
(8,9)
(10,8)
(13,7)
(24,6)

6 steps were requires with full accuracy.  Tested with Double.

Code: [Select]
-- Haskell
import Data.Function
import Data.List
fdf n c = if n == 0 then (0, 0) else let (z, dz) = fdf (n - 1) c in (z^2 + c, 2 * z * dz + 1)
newton bits gdg c = let (z, dz) = gdg c in c - z / (dz * (1 + 0.5 ^ bits))
converge (x:y:zs) = if x == y then [x] else x:converge (y:zs)
main = mapM_ print . map head . groupBy ((==) `on` snd) $ [ (b, length . converge . iterate (newton b (fdf 3)) . negate $ 2) | b <- [1..53] ]

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1214
    • mathr.co.uk
« Reply #9 on: May 14, 2019, 06:42:49 PM »
From experiments in Newton-Hines thread it seems Halley has smaller basins of attraction; I should try it on a "Mandelbrot polynomial".

modified polynomials (dividing by polynomials with lower periods that are factors of the target period) have larger Newton basins
maybe something similar can be done for Halley

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1779
« Reply #10 on: May 14, 2019, 09:01:12 PM »
From experiments in Newton-Hines thread it seems Halley has smaller basins of attraction; I should try it on a "Mandelbrot polynomial".
Checking again that seems to be true only for rational functions that are not polynomials. For polynomials Halley never blows up, like Newton.

The "divide by unwanted zeros" trick (https://mathr.co.uk/blog/2018-11-18_newtons_method_for_periodic_cycles.html) is neat; it works well for Misiurewicz points which I implemented a while ago.

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1214
    • mathr.co.uk
« Reply #11 on: September 11, 2019, 03:51:48 AM »
I noticed that the amount each step improves by is about twice the previous improvement (logarithmically speaking).  That led me to devise this formula for number of Newton iterations left to do:
\[ N = \log_2\left(\frac{\log(d_\infty^2) - \log(d_0^2)}{\log(d_1^2) - \log(d_0^2)}\right) \]
where
\( d_\infty \) is the stopping tolerance (also known as epsilon) and the other d values are how much the previous two steps changed the C value.

The next release of KF will have this feature.  The progress reporting is also fixed to show the current d and epsilon values (which I think were shown at some point but broke along the way).

I noticed in one test I did, where the NR detected a wrong period and never converged, the step count estimate went up to 8, then back down to 0.  So maybe this can be used as a proxy for "its gone wrong, give up now because it won't do what you expect even if it does complete".  I added a note to the documentation to recommend usage of Zoom Size 128 and Cross Hair Window when selecting where to zoom in, to reduce the chances of period mis-detection if you're zoomed too far out from the target.

This new feature is only for Power 2 Mandelbrot (so far).

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1779
« Reply #12 on: September 11, 2019, 04:28:23 AM »
niters = log_2(log_10(zoom)) what I've been going by seems quite close, this is of course better.

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1214
    • mathr.co.uk
« Reply #13 on: September 11, 2019, 08:38:32 AM »
I'm also working on adding the requested auto-save to the Newton-Raphson process.  Too complicated to save a full KFR, so I just save (Re, Im, Zoom, Period), which you can copy/paste into a full KFR if you need to load it in older versions.  I made the upcoming release able to load there more minimal KFR, but you'll want to load a full KFP palette (renamed KFR, or saved from the Color dialog) afterwards to set the other parameters.  Some example output files, corresponding images attached:

Code: [Select]
example-1.newton-0001.kfr:
Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685885846106942996831372450141018482702171355702188916260002811470118183975036597634042438076629626
Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506540504624835609449244671780073796650190254590385328478149775893292211423358784875397496987177782
Zoom: 5.8914350992679410E86
Period: 12034415

example-1.newton-0002.kfr:
Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926251346076181887831147249839867090271839319926561470443244190662028765822024428558414206
Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551456856360416499080847299032874673266853772073122963910745370711366942791750373032486700899
Zoom: 9.7412444385920960E89
Period: 12034415

example-1.newton-0003.kfr:
Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926328543491105991186759632904947545033117956112216951238904390308291977580173531339912479
Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551457596532963885235282149242046970874973847371769171520252796192507821244812241956809678674
Zoom: 2.6874952226231059E96
Period: 12034415

example-1.newton-0004.kfr:
Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926328543491106070050880057556774019598174936106042928916403188637817276471184795427121795
Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551457596532963885293072706080495830020385198996738323889588386189318456096126173357563945377
Zoom: 2.0455824855910900E109
Period: 12034415

example-1.newton-0005.kfr:
Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926328543491106070050880057556774019598175795397386823211262478484787844326385434394573519
Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551457596532963885293072706080495830020385197544265847226618455676448876365985075956714415651
Zoom: 1.1851016094152342E135
Period: 12034415


xx
"Time Span"

Started by cricke49 on Fractal Image Gallery

0 Replies
278 Views
Last post August 02, 2018, 07:05:21 AM
by cricke49
xx
The Newton Bulb - Some fruits need to ripe long

Started by gannjondal on Fractal Image Gallery

0 Replies
105 Views
Last post March 13, 2018, 12:00:58 AM
by gannjondal
xx
Newton-Raphson zooming

Started by gerrit on Fractal Mathematics And New Theories

57 Replies
2716 Views
Last post December 12, 2017, 05:42:52 AM
by gerrit
xx
Newton-Raphson Fractal attempt in Xaos

Started by Know That Fractal! on Fractal Image Gallery

0 Replies
209 Views
Last post December 22, 2017, 01:40:55 AM
by Know That Fractal!
xx
Newton-Raphson zooming for Burning Ship

Started by claude on Fractal Mathematics And New Theories

9 Replies
591 Views
Last post January 08, 2018, 03:03:56 PM
by knighty