Appendix B References
B.1 Books
- Jonathan M. Borwein and Peter B. Borwein, “Pi and the AGM: A Study in
Analytic Number Theory and Computational Complexity”, Wiley, 1998.
- Henri Cohen, “A Course in Computational Algebraic Number Theory”, Graduate
Texts in Mathematics number 138, Springer-Verlag, 1993.
http://www.math.u-bordeaux.fr/~cohen/
- Richard Crandall, Carl Pomerance, “Prime Numbers: A Computational Perspective” 2nd edition, Springer, 2005.
- Donald E. Knuth, “The Art of Computer Programming”, volume 2,
“Seminumerical Algorithms”, 3rd edition, Addison-Wesley, 1998.
http://www-cs-faculty.stanford.edu/~knuth/taocp.html
- John D. Lipson, “Elements of Algebra and Algebraic Computing”,
The Benjamin Cummings Publishing Company Inc, 1981.
- Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, “Handbook of
Applied Cryptography”, http://www.cacr.math.uwaterloo.ca/hac/
- Richard M. Stallman, “Using and Porting GCC”, Free Software Foundation, 1999,
available online http://gcc.gnu.org/onlinedocs/, and in
the GCC package ftp://ftp.gnu.org/gnu/gcc/
B.2 Papers
- Dan Bernstein, “Detecting perfect powers in essentially linear time”, Math. Comp. (67) pp. 1253-1283, 1998.
- Yves Bertot, Nicolas Magaud and Paul Zimmermann, “A Proof of GMP Square
Root”, Journal of Automated Reasoning, volume 29, 2002, pp. 225-252. Also
available online as INRIA Research Report 4475, June 2001,
http://www.inria.fr/rrrt/rr-4475.html
- Marco Bodrato, Alberto Zanoni, “Integer and Polynomial Multiplication: Towards optimal Toom-Cook Matrices”, ISAAC 2007 Proceedings, Ontario, Canada, July 29 - August 1, 2007, ACM Press. Available online at http://ln.bodrato.it/issac2007_pdf
- Marco Bodrato, “High degree Toom‘n’half for balanced and unbalanced multiplication”, E. Antelo, D. Hough and P. Ienne, editors, Proceedings of the 20th IEEE Symposium on Computer Arithmetic, IEEE, Tubingen, Germany, July 25-27, 2011, pp. 15–222. See http://bodrato.it/papers
- Richard Brent and Paul Zimmermann, “Modern Computer Arithmetic”,
version 0.4, November 2009, http://www.loria.fr/~zimmerma/mca/mca-0.4.pdf
- Christoph Burnikel and Joachim Ziegler, “Fast Recursive Division”,
Max-Planck-Institut fuer Informatik Research Report MPI-I-98-1-022,
http://data.mpi-sb.mpg.de/internet/reports.nsf/NumberView/1998-1-022
- Agner Fog, “Software optimization resources”, online at http://www.agner.org/optimize/
- Pierrick Gaudry, Alexander Kruppa, Paul Zimmermann, “A GMP-based implementation of Schoenhage-Strassen’s large integer multiplication algorithm”, ISAAC 2007 Proceedings, Ontario, Canada, July 29 - August 1, 2007, pp. 167-174, ACM Press. Full text available at http://hal.inria.fr/docs/00/14/86/20/PDF/fft.final.pdf
- Torbjorn Granlund and Peter L. Montgomery, “Division by Invariant Integers
using Multiplication”, in Proceedings of the SIGPLAN PLDI’94 Conference, June
1994. Also available ftp://ftp.cwi.nl/pub/pmontgom/divcnst.psa4.gz
(and .psl.gz).
- Niels Möller and Torbjörn Granlund, “Improved division by invariant
integers”, to appear.
- Torbjörn Granlund and Niels Möller, “Division of integers large and
small”, to appear.
- David Harvey, “The Karatsuba middle product for integers”, (preprint), 2009. Available at http://www.cims.nyu.edu/~harvey/mulmid/mulmid.pdf
- Tudor Jebelean,
“An algorithm for exact division”,
Journal of Symbolic Computation,
volume 15, 1993, pp. 169-180.
Research report version available
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-35.ps.gz
- Tudor Jebelean, “Exact Division with Karatsuba Complexity - Extended
Abstract”, RISC-Linz technical report 96-31,
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-31.ps.gz
- Tudor Jebelean, “Practical Integer Division with Karatsuba Complexity”,
ISSAC 97, pp. 339-341. Technical report available
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-29.ps.gz
- Tudor Jebelean, “A Generalization of the Binary GCD Algorithm”, ISSAC 93,
pp. 111-116. Technical report version available
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-01.ps.gz
- Tudor Jebelean, “A Double-Digit Lehmer-Euclid Algorithm for Finding the GCD
of Long Integers”, Journal of Symbolic Computation, volume 19, 1995,
pp. 145-157. Technical report version also available
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-69.ps.gz
- Werner Krandick, Jeremy R. Johnson, “Efficient Multiprecision Floating Point Multiplication with Exact Rounding”, Technical Report, RISC Linz, 1993, available at ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-76.ps.gz
- Werner Krandick and Tudor Jebelean, “Bidirectional Exact Integer Division”,
Journal of Symbolic Computation, volume 21, 1996, pp. 441-455. Early
technical report version also available
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1994/94-50.ps.gz
- Makoto Matsumoto and Takuji Nishimura, “Mersenne Twister: A 623-dimensionally
equidistributed uniform pseudorandom number generator”, ACM Transactions on
Modelling and Computer Simulation, volume 8, January 1998, pp. 3-30.
Available online
http://www.math.keio.ac.jp/~nisimura/random/doc/mt.ps.gz (or .pdf)
- R. Moenck and A. Borodin, “Fast Modular Transforms via Division”,
Proceedings of the 13th Annual IEEE Symposium on Switching and Automata
Theory, October 1972, pp. 90-96. Reprinted as “Fast Modular Transforms”,
Journal of Computer and System Sciences, volume 8, number 3, June 1974,
pp. 366-386.
- Niels Möller, “On Schoenhage’s algorithm and subquadratic integer GCD computation”, Math. Comp. 2007. Available online at http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf
- Peter L. Montgomery, “Modular Multiplication Without Trial Division”, in
Mathematics of Computation, volume 44, number 170, April 1985.
- Thom Mulders, “On short multiplications and divisions”, Appl. Algebra Engrg. Comm. Comput. 11 (2000), no. 1, pp. 69-88. Tech. report No. 276, Dept. of Comp. Sci., ETH Zurich, Nov 1997, available online at ftp://ftp.inf.ethz.ch/pub/publications/tech-reports/2xx/276.pdf
- Arnold Schönhage and Volker Strassen, “Schnelle Multiplikation grosser
Zahlen”, Computing 7, 1971, pp. 281-292.
- A. Schönhage, A. F. W. Grotefeld and E. Vetter, "Fast Algorithms, A Multitape Turing Machine Implementation" BI Wissenschafts-Verlag, Mannheim, 1994.
- Kenneth Weber, “The accelerated integer GCD algorithm”,
ACM Transactions on Mathematical Software,
volume 21, number 1, March 1995, pp. 111-122.
- Paul Zimmermann, “Karatsuba Square Root”, INRIA Research Report 3805,
November 1999, http://www.inria.fr/rrrt/rr-3805.html
- Paul Zimmermann, “A Proof of GMP Fast Division and Square Root
Implementations”,
http://www.loria.fr/~zimmerma/papers/proof-div-sqrt.ps.gz
- Dan Zuras, “On Squaring and Multiplying Large Integers”, ARITH-11: IEEE
Symposium on Computer Arithmetic, 1993, pp. 260 to 271. Reprinted as “More
on Multiplying and Squaring Large Integers”, IEEE Transactions on Computers,
volume 43, number 8, August 1994, pp. 899-908.