The MMIX Supplement · Supplement to the Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth by Ruckert, Martin -- Read -- Imperial Library of Trantor

Index

About This eBook Title Page Copyright Page Foreword Preface Style Guide

1. Names 2. Temporaries 3. Index Variables 4. Register Numbers 5. Local Name Spaces 6. Instruction Counts

Programming Techniques

1. Index Variables 2. Fields 3. Relative Addresses 4. Using the Low Order Bits of Pointers (“Bit Stuffing”) 5. Loop Unrolling 6. Subroutines 7. Reporting Errors

Contents Chapter One. Basic Concepts

1.3.3. Applications to Permutations 1.4.4. Input and Output

Chapter Two. Information Structures

2.1. Introduction 2.2.2. Sequential Allocation 2.2.3. Linked Allocation 2.2.4. Circular Lists 2.2.5. Doubly Linked Lists 2.2.6. Arrays and Orthogonal Lists 2.3.1. Traversing Binary Trees 2.3.2. Binary Tree Representation of Trees 2.3.3. Other Representations of Trees 2.3.5. Lists and Garbage Collection 2.5. Dynamic Storage Allocation

Chapter Three. Random Numbers

3.2.1.1. Choice of modulus 3.2.1.3. Potency 3.2.2. Other Methods 3.4.1. Numerical Distributions 3.6. Summary

Chapter Four. Arithmetic

4.1. Positional Number Systems 4.2.1. Single-Precision Calculations 4.2.2. Accuracy of Floating Point Arithmetic 4.2.3. Double-Precision Calculations 4.3.1. The Classical Algorithms 4.4. Radix Conversion 4.5.2. The Greatest Common Divisor 4.5.3. Analysis of Euclid’s Algorithm 4.5.4. Factoring into Primes 4.6.3. Evaluation of Powers 4.6.4. Evaluation of Polynomials

Chapter Five. Sorting

5.2. Internal Sorting 5.2.1. Sorting by Insertion 5.2.2. Sorting by Exchanging 5.2.3. Sorting by Selection 5.2.4. Sorting by Merging 5.2.5. Sorting by Distribution 5.3.1. Minimum-Comparison Sorting 5.5. Summary, History, and Bibliography

Chapter Six. Searching

6.1. Sequential Searching 6.2.1. Searching an Ordered Table 6.2.2. Binary Tree Searching 6.2.3. Balanced Trees 6.3. Digital Searching 6.4. Hashing

Answers to Exercises

1.3.2. The MMIX Assembly Language 1.3.3. Applications to Permutations 1.4.4. Input and Output 2.1. Introduction 2.2.2. Sequential Allocation 2.2.3. Linked Allocation 2.2.4. Circular Lists 2.2.5. Doubly Linked Lists 2.2.6. Arrays and Orthogonal Lists 2.3.1. Traversing Binary Trees 2.3.2. Binary Tree Representation of Trees 2.3.5. Lists and Garbage Collection 2.5. Dynamic Storage Allocation 3.2.1.1. Choice of modulus 3.2.1.3. Potency 3.2.2. Other Methods 3.4.1. Numerical Distributions 3.6. Summary 4.1. Positional Number Systems 4.2.1. Single-Precision Calculations 4.2.2. Accuracy of Floating Point Arithmetic 4.2.3. Double-Precision Calculations 4.3.1. The Classical Algorithms 4.4. Radix Conversion 4.5.2. The Greatest Common Divisor 4.5.3. Analysis of Euclid’s Algorithm 4.6.3. Evaluation of Powers 4.6.4. Evaluation of Polynomials 5. Sorting

5.2. Internal Sorting 5.2.1. Sorting by Insertion 5.2.2. Sorting by Exchanging 5.2.3. Sorting by Selection 5.2.4. Sorting by Merging 5.2.5. Sorting by Distribution 5.3.1. Minimum-Comparison Sorting

5.5. Summary, History, and Bibliography 6.1. Sequential Searching 6.2.1. Searching an Ordered Table 6.2.2. Binary Tree Searching 6.2.3. Balanced Trees 6.3. Digital Searching 6.4. Hashing

Acknowledgments Index