Martin Ruckert - The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth

ePUB is an open, industry-standard format for eBooks. However, support of ePUB and its many features varies across reading devices and applications. Use your device or app settings to customize the presentation to your liking. Settings that you can customize often include font, font size, single or double column, landscape or portrait mode, and figures that you can click or tap to enlarge. For additional information about the settings and features on your reading device or app, visit the device manufacturers Web site.

Many titles include programming code or configuration examples. To optimize the presentation of these elements, view the eBook in single-column, landscape mode and adjust the font size to the smallest setting. In addition to presenting code and configurations in the reflowable text format, we have included images of the code that mimic the presentation found in the print book; therefore, where the reflowable format may compromise the presentation of the code listing, you will see a Click here to view code image link. Click the link to view the print-fidelity code image. To return to the previous page viewed, click the Back button on your device or app.

In this eBook, the limitations of the ePUB format have caused us to render some equations as text and others as images, depending on the complexity of the equation. This can result in an odd juxtaposition in cases where the same variables appear as part of both a text presentation and an image presentation. However, the authors intent is clear and in both cases the equations are legible.

Supplement to

The Art of Computer Programming

Volumes 1, 2, 3

by Donald E. Knuth

MARTIN RUCKERT

Munich University of Applied Sciences

ADDISONWESLEY

Upper Saddle River, NJ Boston Indianapolis San Francisco New York Toronto Montral London Munich Paris Madrid Capetown Sydney Tokyo Singapore Mexico City

The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein.

For information about buying this title in bulk quantities, or for special sales opportunities (which may include electronic versions; custom cover designs; and content particular to your business, training goals, marketing focus, or branding interests), please contact our corporate sales department at corpsales@pearsoned.com or (800) 382-3419.

For government sales inquiries,
please contact governmentsales@pearsoned.com.

For questions about sales outside the United States,
please contact international@pearsoned.com.

Visit us on the Web: informit.com/aw

Library of Congress Cataloging-in-Publication Data

Ruckert, Martin.
The MMIX supplement : supplement to The art of computer programming,
volumes 1, 2, 3 by Donald E. Knuth / Martin Ruckert, Munich University
of Applied Sciences.
pages cm
Includes index.
ISBN 978-0-13-399231-1 (pbk. : alk. paper) -- ISBN 0-13-399231-4 (pbk.
: alk. paper)
1. MMIX (Computer architecture) 2. Assembly languages (Electronic
computers) 3. Microcomputers--Programming. I. Knuth, Donald Ervin,
1938-. Art of computer programming. II. Title.
QA76.6 .K64 2005 Suppl. 1
005.1--dc23 2014045485

Internet page http://mmix.cs.hm.edu/supplement.html contains current information about this book, downloadable software, and general news about MMIX. See also http://www-cs-faculty.stanford.edu/~knuth/taocp.html for information about The Art of Computer Programming by Donald E. Knuth.

Copyright 2015 by Pearson Education, Inc.

All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to (201) 236-3290.

ISBN-13: 978-0-13-399231-1
ISBN-10: 0-13-399231-4

Text printed in the United States on recycled paper at Courier in Kendallville, Indiana.

First printing, February 2015

WHY ARE SOME programmers so much better than others? What is the magical ingredient that makes it possible for some people to resonate with computers so well, and to reach new heights of performance? Many different skills are clearly involved. But after decades of observation Ive come to believe that one particular talent stands out among the world-class programmers Ive knownnamely, an ability to move effortlessly between different levels of abstraction.

That may sound like a scary and complex thing, inherently abstract in itself, but I think its not really too hard to explain. A programmer must deal with high-level concepts related to a problem area, with low-level concepts related to basic steps of computation, and with numerous levels in between. We represent reality by creating structures that are composed of progressively simpler and simpler parts. We dont only need to understand how those parts fit together; we also need to be able somehow to envision the whole showto see everything in the large while seeing it simultaneously in the small and in the middle. Without blinking an eye, we need to understand why a major goal can be accomplished if we begin by increasing the contents of a lowly computer register by 1.

The best way to enhance our level-jumping skills is to exercise them frequently. And I believe the most effective strategy for that is to repeatedly examine the details of what goes on at the hardware level when a sophisticated algorithm is being implemented at a conceptual level. In the preface to Volume 1 of The Art of Computer Programming, I listed six reasons for choosing to discuss machine-oriented details together with high-level abstractions, integrating both aspects as I was presenting fundamental paradigms and algorithms of computer science. I still like those six reasons. But in retrospect I see now that I was actually blind to the most important reasonthat is, the pedagogical reason: I know of no better way to teach a student to think like a top computer scientist than to ground everything in a firm knowledge of how a computing machine actually works. This bottom-up approach seems to be the best way to help nurture an ability to navigate fluently between levels. Indeed, Tony Hoare once told me that I should never even think of condensing these books by removing the machine-language parts, because of their educational value.

I am thrilled to see the present book by Martin Ruckert: It is jam-packed with goodies from which an extraordinary amount can be learned. Martin has not merely transcribed my early programs for MIX and recast them in a modern idiom. He has penetrated to their essence and rendered them anew with elegance and good taste. His carefully checked codes represent a significant contribution to the art of pedagogy as well as to the art of programming. Although I myself rarely write machine-level instructions nowadays, my experiences of doing so in the past have provided an indispensable boost to the quality of everything that I now am undertaking. So I encourage serious programmers everywhere to sharpen their skills by devouring this book.