Removing redundancy in high-precision Newton iteration

Papers

[fastnewton] 13pp, draft. (PDF) (PS) (DVI) D. J. Bernstein. Removing redundancy in high-precision Newton iteration. Document ID: def7f1e35fb654671c6f767b16b93d50. URL: https://cr.yp.to/papers.html#fastnewton. Date: 2004.03.09. Supersedes: (PDF) (PS) (DVI) 1998.06.27.

Relevant talks: 1999.10.13 (slides available), ``Solving equations to high precision.''

Proof-of-concept software

The constants labelled below as ``2000 Bernstein'' were found in 1999 and published here in 2000: reciprocal, square root, exponential. These algorithms are explained in Section 5 of the paper.

Summary of the results

High-precision division, square root, etc. can be accelerated. The best algorithms are nearly three times faster than the usual algorithms.

The following table shows the constants for various algorithms compared to multiplication. For example, 1.5 for 1/f means that there is a reciprocal algorithm taking 1.5+o(1) times as long as multiplication. ``Simple'' is the usual algorithm; ``best'' is the smallest published constant.

simple best order-2 best

1/f 4 1.5 (2000 Schoenhage) 1.5 (2000 Schoenhage, independently 2000 Bernstein); previously 1.8666... (1998 Bernstein); previously 2 (1994 Schoenhage Grotefeld Vetter, without details); previously 3 (1976 Brent)

g/f 5 2.0833... (2004 Hanrot Zimmermann); previously 2.3333... (2003 Bernstein) 2.0833... (2004 Hanrot Zimmermann); previously 2.1666... (2000 Bernstein); previously 2.625 (1998 Harley, without details); previously 2.7333... (1998 Bernstein); previously 3 (1994 Schoenhage Grotefeld Vetter, without details); previously 4 (1976 Brent)

f^{1/2} 5 1.8333... (2004 Bernstein) 1.8333... (2000 Bernstein); previously 2.1666... (1998 Bernstein); previously 4.5 (1976 Brent)

f^{1/2},f^{-1/2} 7 2.5 (2004 Bernstein) 2.5 (2000 Bernstein); previously 3 (1998 Bernstein); previously 5.5 (1976 Brent)

exp f for series 8 3.25 (2004 Hanrot Zimmermann); previously 3.3333... (2004 Bernstein) 2.8333... (2000 Bernstein); previously 3.4444... (1998 Bernstein); previously 7.3333... (1976 Brent)

	simple	best order-2	best
1/f	4	1.5 (2000 Schoenhage)	1.5 (2000 Schoenhage, independently 2000 Bernstein); previously 1.8666... (1998 Bernstein); previously 2 (1994 Schoenhage Grotefeld Vetter, without details); previously 3 (1976 Brent)
g/f	5	2.0833... (2004 Hanrot Zimmermann); previously 2.3333... (2003 Bernstein)	2.0833... (2004 Hanrot Zimmermann); previously 2.1666... (2000 Bernstein); previously 2.625 (1998 Harley, without details); previously 2.7333... (1998 Bernstein); previously 3 (1994 Schoenhage Grotefeld Vetter, without details); previously 4 (1976 Brent)
f^{1/2}	5	1.8333... (2004 Bernstein)	1.8333... (2000 Bernstein); previously 2.1666... (1998 Bernstein); previously 4.5 (1976 Brent)
f^{1/2},f^{-1/2}	7	2.5 (2004 Bernstein)	2.5 (2000 Bernstein); previously 3 (1998 Bernstein); previously 5.5 (1976 Brent)
exp f for series	8	3.25 (2004 Hanrot Zimmermann); previously 3.3333... (2004 Bernstein)	2.8333... (2000 Bernstein); previously 3.4444... (1998 Bernstein); previously 7.3333... (1976 Brent)