Schoenhage A., Grotefeld A.F.W., Vetter E. Fast algorithms: a multitape Turing machine implementation. With errata

Bibliographisches Institut & F.A. Brockhaus AG, 1994. — 311 p.
About ten years ago I have started my work on a voluminous book project with tentative title Computational Complexity and Fundamental Problems of Numerical Mathematics. One of the central goals with this project is a thorough development of my Splitting Circle Method for fast approximate factorization of complex polynomials, combined with an adequate presentation of the theoretical foundations in complexity theory, and aiming at an efficient practical implementation. Section 3 of [Sc86b] about the fundamental theorem of algebra in terms of computational complexity gives a brief outline of the main underlying ideas, and since 1982 there also exists a preliminary report describing many of the theoretical details of this method, but that is only half of the story, or even less.The full text of that "main book" shall also cover the more practical issues of a really fast implementation, including all the required subalgorithms with their innumerous technicalities.
The detour for developing these subalgorithms has taken a considerable amount of additional time. The division of complex numbers, to mention just one example, has absorbed me for more than a year. Meanwhile there exists quite a substantial collection of algorithms implemented on a surprisingly efficient model of a multitape Turing machine. Besides the classical routines for computing with integers and rational, real, and complex numbers, this collection includes many of the asymptotically fast algorithms for these domains, also several new algorithms never published before. So there is growing interest of other working groups in general availability of this software. Further research based on these routines requires a coordinating compilation of this material accumulated over the years anyway. Moreover, the guiding principles behind these routines appear to be well suited for educational purposes. All this has motivated us to write this "TP-book" as an inseparable mixture of textbook, research report, reference manual, and programmer's guide.
In order to get a brief impression of the development of this software, you may find it instructive to have a look at the first and the last page of Chapter 1, onthe Preamble of Chapter 5, and the last page of Chapter 9 . It has been a pretty long journey from the very beginning, starting with the first implementation on a small computer, to the present state of this project, supported by many people and institutions in many ways. Special acknowledgements go to R. Loos and the University at Karlsruhe for hardware and software support with the zero version,to G. Regenspurg for stimulating discussions about related hardware aspects, to M Luneburg for writing the routines for rational arithmetic, and to D.Reischert for his careful proofreading. Quite generally, I wish to express my thanks to all who have been patient enough to listen to my ideas, including those who have encouraged my efforts by their challenging scepticism about the practicability of Turing machines. And we have to thank the publisher and H. Engesser for not sharing this scepticism, and for the cooperation in bringing out this book. As it stands, this text could not have been written without the congenial contributions of my coauthors. A. Grotefeld as our expert for the Sun 3 version has developed tpl, tpx, and written Chapter 4, while all of tpc and Chapter 3 are E. Vetter's work. Of course, these chapters are just the tip of the iceberg. The efficient implementation software hidden under the surface is what provides all the convenient facilities of these advanced TP versions and what makes the fast algorithms really fast.
Bonn, January 1994 A. Schonhage