Modern Computer Algebra
Joachim von zur Gathen and Jürgen Gerhard.
Textbook, 3rd edition, Cambridge University Press 2013 (publisher site).
ISBN 978-1107039032.
808 pages, 55 b/w illustrations, 53 colour illustrations, 40 tables, 560 exercises.
(Second edition 2003: ISBN 978-0521826464.)
(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