Fast arithmetic

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

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