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

• 10 Replies
• 213 Views

0 Members and 1 Guest are viewing this topic.

#### CFJH

• Fractal Furball
• Posts: 256

#### 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: 1640

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

• 3e
• Posts: 1065

#### 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: 1640

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

• 3e
• Posts: 1065

#### 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: 1640

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

• 3e
• Posts: 1065

#### 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: 1640

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

• 3e
• Posts: 1065

#### 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] ]

• 3e
• Posts: 1065

#### 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: 1640

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

### Similar Topics

###### "Time Span"

Started by cricke49 on Fractal Image Gallery

0 Replies
211 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
93 Views
March 13, 2018, 12:00:58 AM
by gannjondal
###### Newton-Raphson zooming

Started by gerrit on Fractal Mathematics And New Theories

57 Replies
2538 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
189 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
540 Views
January 08, 2018, 03:03:56 PM
by knighty