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

• 13 Replies
• 325 Views

0 Members and 1 Guest are viewing this topic.

#### CFJH

• Fractal Furball
• Posts: 286

#### Newton Raphson - how long wilt it run ?

« 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.

• 3f
• Posts: 1779

#### Re: Newton Raphson - how long wilt it run ?

« 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.

• 3f
• Posts: 1214

#### Re: Newton Raphson - how long wilt it run ?

« 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.

• 3f
• Posts: 1779

#### Re: Newton Raphson - how long wilt it run ?

« 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'})$$.

• 3f
• Posts: 1214

#### Re: Newton Raphson - how long wilt it run ?

« 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.

• 3f
• Posts: 1779

#### Re: Newton Raphson - how long wilt it run ?

« 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?

• 3f
• Posts: 1214

#### Re: Newton Raphson - how long wilt it run ?

« 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)

• 3f
• Posts: 1779

#### Re: Newton Raphson - how long wilt it run ?

« 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 »

• 3f
• Posts: 1214

#### Re: Newton Raphson - how long wilt it run ?

« 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]
-- Haskellimport Data.Functionimport Data.Listfdf 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] ]

• 3f
• Posts: 1214

#### Re: Newton Raphson - how long wilt it run ?

« 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

• 3f
• Posts: 1779

#### Re: Newton Raphson - how long wilt it run ?

« 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.

• 3f
• Posts: 1214

#### Re: Newton Raphson - how long wilt it run ?

« 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).

• 3f
• Posts: 1779

#### Re: Newton Raphson - how long wilt it run ?

« 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.

• 3f
• Posts: 1214

#### Re: Newton Raphson - how long wilt it run ?

« 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.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685885846106942996831372450141018482702171355702188916260002811470118183975036597634042438076629626Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506540504624835609449244671780073796650190254590385328478149775893292211423358784875397496987177782Zoom: 5.8914350992679410E86Period: 12034415example-1.newton-0002.kfr:Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926251346076181887831147249839867090271839319926561470443244190662028765822024428558414206Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551456856360416499080847299032874673266853772073122963910745370711366942791750373032486700899Zoom: 9.7412444385920960E89Period: 12034415example-1.newton-0003.kfr:Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926328543491105991186759632904947545033117956112216951238904390308291977580173531339912479Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551457596532963885235282149242046970874973847371769171520252796192507821244812241956809678674Zoom: 2.6874952226231059E96Period: 12034415example-1.newton-0004.kfr:Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926328543491106070050880057556774019598174936106042928916403188637817276471184795427121795Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551457596532963885293072706080495830020385198996738323889588386189318456096126173357563945377Zoom: 2.0455824855910900E109Period: 12034415example-1.newton-0005.kfr:Re: -1.739721642113471628609456705960498302576327101300430213476579368175514612504239785796685886478926328543491106070050880057556774019598175795397386823211262478484787844326385434394573519Im: -0.000001209880477685190918325374688573270997847464698731475166296166811128428426707116506538551457596532963885293072706080495830020385197544265847226618455676448876365985075956714415651Zoom: 1.1851016094152342E135Period: 12034415

### Similar Topics

###### "Time Span"

Started by cricke49 on Fractal Image Gallery

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

Started by gannjondal on Fractal Image Gallery

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

Started by gerrit on Fractal Mathematics And New Theories

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

Started by Know That Fractal! on Fractal Image Gallery

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

Started by claude on Fractal Mathematics And New Theories

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