Modern Computer Algebra
Joachim von zur Gathen and Jürgen Gerhard.
Textbook, 2nd edition, Cambridge University Press 2003 (US site).
ISBN 0521826462 Price £ 40 (US $ 65).
xiv+786 pages, 132 figures and tables (54 colored), 102 algorithms, 563 exercises.
(First edition 1999: ISBN 0521641764.)
MCA gallery: fast multiplication
An arithmetic circuit illustrating Karatsuba's algorithm for n=4. The shaded boxes are Karatsuba circuits for n=2. A subtraction node computes the difference of its left input minus its right input.
Cost (= black area) of Karatsuba's algorithm for increasing recursion depths. The image approaches a fractal of dimension log 3=1.59.
An arithmetic circuit computing the FFT for n=8.
Cost of the FFT for increasing recursion depths. The black area is proportional to the total work.
© Joachim von zur Gathen and Jürgen Gerhard, last change: 7 May 1999