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

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

by Martin Ruckert
Released February 2015
Publisher(s): Addison-Wesley Professional
ISBN: 9780133992892

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

The MMIX Supplement: Supplement toThe Art of Computer ProgrammingVolumes 1, 2, 3 by Donald E. Knuth

“I encourage serious programmers everywhere to sharpen their skills by devouring this book.”

–Donald E. Knuth

In the first edition of Volume 1 of The Art of Computer Programming, Donald E. Knuth introduced the MIX computer and its machine language: a teaching tool that powerfully illuminated the inner workings of the algorithms he documents. Later, with the publication of his Fascicle 1, Knuth introduced MMIX: a modern, 64-bit RISC replacement to the now-obsolete MIX. Now, with Knuth’s guidance and approval, Martin Ruckert has rewritten all MIX example programs from Knuth’s Volumes 1-3 for MMIX, thus completing this MMIX update to the original classic.

Building on contributions from the international MMIXmasters volunteer group, Ruckert fully addresses MMIX basic concepts, information structures, random numbers, arithmetic, sorting, and searching. In the preparation of this supplement, about 15,000 lines of MMIX code were written and checked for correctness; over a thousand test cases were written and executed to ensure the code is of the highest possible quality.

The MMIX Supplement should be read side by side with The Art of Computer Programming, Volumes 1-3, and Knuth’s Fascicle 1, which introduces the MMIX computer, its design, and its machine language. Throughout, this supplement contains convenient page references to corresponding coverage in the original volumes. To further simplify the transition to MMIX, Ruckert stayed as close as possible to the original–preserving programming style, analysis techniques, and even wording, while highlighting differences where appropriate. The resulting text will serve as a bridge to the future, helping readers apply Knuth’s insights in modern environments, until his revised, “ultimate” edition of The Art of Computer Programming is available.

From Donald E. Knuth’s Foreword:

“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 code represents a significant contribution to the art of pedagogy as well as to the art of programming.”

Dr. Martin Ruckert maintains the MMIX home page at mmix.cs.hm.edu. He is professor of mathematics and computer science at Munich University of Applied Sciences in Munich, Germany.

Table of contents

  1. About This eBook
  2. Title Page
  3. Copyright Page
  4. Foreword
  5. Preface
  6. Style Guide
    1. 1. Names
    2. 2. Temporaries
    3. 3. Index Variables
    4. 4. Register Numbers
    5. 5. Local Name Spaces
    6. 6. Instruction Counts
  7. Programming Techniques
    1. 1. Index Variables
    2. 2. Fields
    3. 3. Relative Addresses
    4. 4. Using the Low Order Bits of Pointers (“Bit Stuffing”)
    5. 5. Loop Unrolling
    6. 6. Subroutines
    7. 7. Reporting Errors
  8. Contents
  9. Chapter One. Basic Concepts
    1. 1.3.3. Applications to Permutations
    2. 1.4.4. Input and Output
  10. Chapter Two. Information Structures
    1. 2.1. Introduction
    2. 2.2.2. Sequential Allocation
    3. 2.2.3. Linked Allocation
    4. 2.2.4. Circular Lists
    5. 2.2.5. Doubly Linked Lists
    6. 2.2.6. Arrays and Orthogonal Lists
    7. 2.3.1. Traversing Binary Trees
    8. 2.3.2. Binary Tree Representation of Trees
    9. 2.3.3. Other Representations of Trees
    10. 2.3.5. Lists and Garbage Collection
    11. 2.5. Dynamic Storage Allocation
  11. Chapter Three. Random Numbers
    1. 3.2.1.1. Choice of modulus
    2. 3.2.1.3. Potency
    3. 3.2.2. Other Methods
    4. 3.4.1. Numerical Distributions
    5. 3.6. Summary
  12. Chapter Four. Arithmetic
    1. 4.1. Positional Number Systems
    2. 4.2.1. Single-Precision Calculations
    3. 4.2.2. Accuracy of Floating Point Arithmetic
    4. 4.2.3. Double-Precision Calculations
    5. 4.3.1. The Classical Algorithms
    6. 4.4. Radix Conversion
    7. 4.5.2. The Greatest Common Divisor
    8. 4.5.3. Analysis of Euclid’s Algorithm
    9. 4.5.4. Factoring into Primes
    10. 4.6.3. Evaluation of Powers
    11. 4.6.4. Evaluation of Polynomials
  13. Chapter Five. Sorting
    1. 5.2. Internal Sorting
    2. 5.2.1. Sorting by Insertion
    3. 5.2.2. Sorting by Exchanging
    4. 5.2.3. Sorting by Selection
    5. 5.2.4. Sorting by Merging
    6. 5.2.5. Sorting by Distribution
    7. 5.3.1. Minimum-Comparison Sorting
    8. 5.5. Summary, History, and Bibliography
  14. Chapter Six. Searching
    1. 6.1. Sequential Searching
    2. 6.2.1. Searching an Ordered Table
    3. 6.2.2. Binary Tree Searching
    4. 6.2.3. Balanced Trees
    5. 6.3. Digital Searching
    6. 6.4. Hashing
  15. Answers to Exercises
    1. 1.3.2. The MMIX Assembly Language
    2. 1.3.3. Applications to Permutations
    3. 1.4.4. Input and Output
    4. 2.1. Introduction
    5. 2.2.2. Sequential Allocation
    6. 2.2.3. Linked Allocation
    7. 2.2.4. Circular Lists
    8. 2.2.5. Doubly Linked Lists
    9. 2.2.6. Arrays and Orthogonal Lists
    10. 2.3.1. Traversing Binary Trees
    11. 2.3.2. Binary Tree Representation of Trees
    12. 2.3.5. Lists and Garbage Collection
    13. 2.5. Dynamic Storage Allocation
    14. 3.2.1.1. Choice of modulus
    15. 3.2.1.3. Potency
    16. 3.2.2. Other Methods
    17. 3.4.1. Numerical Distributions
    18. 3.6. Summary
    19. 4.1. Positional Number Systems
    20. 4.2.1. Single-Precision Calculations
    21. 4.2.2. Accuracy of Floating Point Arithmetic
    22. 4.2.3. Double-Precision Calculations
    23. 4.3.1. The Classical Algorithms
    24. 4.4. Radix Conversion
    25. 4.5.2. The Greatest Common Divisor
    26. 4.5.3. Analysis of Euclid’s Algorithm
    27. 4.6.3. Evaluation of Powers
    28. 4.6.4. Evaluation of Polynomials
    29. 5. Sorting
      1. 5.2. Internal Sorting
      2. 5.2.1. Sorting by Insertion
      3. 5.2.2. Sorting by Exchanging
      4. 5.2.3. Sorting by Selection
      5. 5.2.4. Sorting by Merging
      6. 5.2.5. Sorting by Distribution
      7. 5.3.1. Minimum-Comparison Sorting
    30. 5.5. Summary, History, and Bibliography
    31. 6.1. Sequential Searching
    32. 6.2.1. Searching an Ordered Table
    33. 6.2.2. Binary Tree Searching
    34. 6.2.3. Balanced Trees
    35. 6.3. Digital Searching
    36. 6.4. Hashing
  16. Acknowledgments
  17. Index

Product information

  • Title: The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth
  • Author(s): Martin Ruckert
  • Release date: February 2015
  • Publisher(s): Addison-Wesley Professional
  • ISBN: 9780133992892