MMIXmasters


Documentation, Sources, Binaries, Links, Examples, Contributions

Table of Content

Content

The MMIX Supplement

The results of the MMIXmasters did appear as a book:

The MMIX Supplement
to
The Art of Computer Programming
Volumes 1, 2, 3
by Donald E. Knuth
ISBN-13: 978-0133992311
ISBN-10: 0133992314

The book is available from Amazon or other bookstores.

There is a separate page devoted to this book.

The mission is, however, not yet completed! Please analyze, check, test, review, or improve the code you find there to help getting it in its final shape!

A big "Thank You!" goes to all that contributed so far.

Welcome to the MMIXmasters

MMIX, the CPU, and its associated assembly language was created by Donald Knuth to specify algorithms in the next edition of his series: The Art of Computer Programming (TAOCP). Currently volume 1, 2, 3, and 4A, as well as five fascicles have been published, with more in preparation. Knuth will use MMIX as the low-level programming language in the "ultimate" edition of his opus.

As Donald Knuth states in his "Call for Volunteers":

All of the MIX programs in Volumes 1--3 will need to be rewritten in MMIX, before I finish the ``ultimate'' edition of those volumes that I plan to write after Volume 5 is completed. The current target date for the ultimate volumes is the year 2020, so there is plenty of time to do the conversion. But I think it will be an instructive undertaking if different groups of students from around the world try to do the necessary translations first, perhaps in friendly competitions, long before I get into the act.
This part of the web site is for the volunteers---the MMIXmasters---who are converting all of the programs in TAOCP, Volumes 1 - 3, from the old language MIX to the new language MMIX.

The MMIXmasters had their home at www.mmixmasters.org, which was set up in December 1998 (see History) by Vladimir G. Ivanovic who headed the MMIXmasters since then. After a good start, the contributions became fewer and fewer. In May 2002, the MMIXmasters moved to mmixmasters.sourceforge.net but the activity level remained low. Therefore in July 2011, when the prospect of moving MMIX to a new home at mmix.cs.hm.edu materialized, Vladimir proposed to move the MMIXmasters to this new site as well.

The remainder of this page is taken from the existing MMIXmasters pages by Vladimir and were adapted to fit into the new context.

MIX

MIX is a hybrid binary-decimal computer. When it is programmed in binary, each byte has six bits. In decimal, each byte has two decimal digits. Bytes are arranged into words of five bytes plus a sign. The majority of programs written for MIX will work in either binary or decimal, as long as they do not attempt to store a value greater than 63 in a single byte.

Each machine instruction in memory occupies one word, and consists of four parts: the address in memory to read or write, an index specification to add to the address, a modification that specifies which parts of the register or memory location will be read or altered, and the code of operation. All operation codes have a related mnemonic.

MIX programs often use self-modifying code, in particular to return from a subroutine, as MIX lacks an automatic subroutine return pile. Self-modifying code is enabled by the modification byte, letting the program store information to, for instance, the address part of the target instruction, leaving the rest of the instruction without modification.

How to Volunteer

Note: These instructions are open to revision. I am open to comments, suggestions and discussion.

  1. Download and read the documentation (see sidebar). We especially recommend:
  2. Download and build the latest sources for the simple simulator, assembler, test programs, and documentation files mentioned above, and the meta-simulator. Alternatively, download a set of ready to run executables (see sidebar).
  3. Become familiar with the process of compiling and debugging MMIX programs. For example look at the Hello World example in the examples section.
  4. Choose a MIX program that has not already been converted to MMIX. See below for the list of available programs and their current status.
  5. Send us an email with your contribution. Currently there is no formal submission procedure and no format requirements. Just be reasonable. Of course, it will help us to publish your contribution, if you describe what you did in an index.html file, supply the source code, and complement it with appropriate test cases.

Programming Style

  • Try to be faithful to Knuth's style. Look at the MMIX programs he has published in Fascicle 1 and in Volume 4A of TAOCP. His style is very flexible, there are no absolute rules (that I know of), but one goal: to optimize readability and efficiency.

    There is also a style guide that tries to give useful hints.

    Tools for Testing and Publishing

    The programs that are written by the MMIXmasters should not only compile but are intended ultimately for publication. For this end, program text in mms files needs to be converted to program text in tex files. To facilitate this translation, there is a simple tool, mmstotex, which is described on the mmstotex page, where you find also a link to its source code (a lex file).

    All programs should be tested. Especially those that are intended for publication. To facilitate writing and executing test cases, I wrote a simple tool to produce a series of programs from a test description. The tool testgen is described on the testgen page, again with a link to its source code.

    MIX to MMIX Conversion

    Here are the MIX programs that need to be converted to MMIX.

    Programs or algorithms that are related have been grouped together, but could be separated if that makes more sense. (For example, Program #1.10 could be split into programs 1.10.1, 1.10.2 and 1.10.3.)

    If there are any errors, please let us know, but make sure you are using the edition and printing indicated.

    Volume 1: Fundamental Algorithms, 3/e, First Printing, May 1997

    Section Page Program Solution
    1.3.2 519 Exercise 18 (Farey Series) #18 Analysis pdf
    1.3.2 521 Exercise 22 (Josephus Problem) #22 Analysis pdf
    1.3.3 168 Program A A Analysis pdf
    1.3.3 174 Program B B Analysis pdf
    1.3.3 177 Program I I Analysis pdf
    1.3.3 178 Program J J Analysis pdf
    2.1 236 Algorithm A A
    2.2.3 258-259 stack insert & delete insert & delete
    2.2.3 266-268 Program T (Topological Sort) T
    2.2.4 277-278, 552-553 Program A (Addition of Polynomials), #11, #13, #14, #15, A #11 #13 #14 #15
    2.2.5 289-295, 554-555, 568 The Elevator Simulation, #8 & #9 S 8 9 or S 8 9
    2.3.1 325, 567 Programs S & T, #20 S T #20
    2.3.2 342-345, 572-573 Program D (Differentiation), #13 D #13
    2.1 535 #8 #8
    2.1 535 #9 #9
    2.2.3 545 #2, #3, #4 #2 #3
    2.2.3 546 #8 #8
    2.2.3 548-549 #24 #24
    2.2.3 550 #27 #27
    2.2.5 556 #9 S 8 9 or S 8 9
    2.2.6 557-559 #15 #15
    2.3.2 573 #15 #15
    2.3.2 574 #16 #16
    2.3.5 601-602 #4 #4
    2.5 607 #4 #4
    2.5 609-610 #13, #16 #13 #16
    2.5 611-613 #27, #28 #27, #28
    2.5 614 #34 #34

    Volume 2: Seminumerical Algorithms, 3/e, First Printing, September 1997

    Section Page Program Proposal
    3.2.2 28, 556 Program A (Additive number generator), #25 A1 or A2
    4.2.1 218-219, 220-221, 612, 612-13, 615 Program A (Addition, subtraction, and normalization), Program M (Floating point multiplication and division), #14, #15 A M #14 #15
    4.2.3 247-249, 249-250, 251-252, 618 Program A (Double-precision addition), Program M (Double-precision multiplication), Program D (Double-precision division), #6 A P D #6
    4.3.1 266-267, 267-268, 269-270, 273-275, 623, 624, 625, 626 Program A (Addition of nonnegative integers), Program S (Subtraction of nonnegative integers), Program M (Multiplication of nonnegative integers), Program D (Division of nonnegative integers), #3, #8, #13, #25, #26 A S M D #3 #8 #13 #25 #26
    4.4 320, 321, 637-638 Single-precision conversion (Methods 1a and 2a),#8, #13, #19 M1a M1b M2a M2a #8 #13 #19
    4.5.2 337,339 Euclid's algorithm A, Binary gcd algorithm B A B
    3.2.1.1, 3.6 543, 544, 599 #2, #8, #1 #2 #5 #5 #8 #1
    4.6.3 691 #2 #2 #2S

    Volume 3: Sorting and Searching,2/e, First Printing, March 1998

    Section Page Program Proposal
    5.2 79, 615-616 Program C (Comparison counting), #4, #5, #9 C #4 #5 #9
    5.2.1 81, 597 Program S (Straight insertion sort) S
    5.2.1 85 Program D (Shellsort) D
    5.2.1 97, 603 Program L (List insertion), #33 L #33
    5.2.1 100, 625-626 Program M (Multiple list insertion), #35 M #35
    5.2.2 107 Program B (Bubble sort) B
    5.2.2 117-119, 614 Program Q (Quicksort), #55 Q #55
    5.2.2 126-127 Program R (Radix exchange) R
    5.2.3 140, 616 Program S (Straight selection sort), #8 S
    5.2.3 148 Program H (Heapsort) H
    5.2.4 167-168 Program N, L (List merge sort) N L
    5.2.5 174-176 Program R (Radix list sort) R
    6.1 394, 665 Program S (Sequential search), #3 S #3
    6.1 395 Program Q (Quick sequential search) Q
    6.1 395 Program Q' (Quicker sequential search) Q'
    6.2.1 411 Program B (Binary search) B
    6.2.1 413, 668-669 Program C (Uniform binary search), #11 C
    6.2.1 416 Program F (Fibbonaccian search) F
    6.2.2 425 Program T (Tree search & insertion) C
    6.2.3 457-458 Program A (Balanced tree search & insertion) A
    6.3 482-483 Program T (Trie search) T
    6.4 516, 729 Program C (Chained hash table search & insertion), #12 C #12
    6.4 519 Program L (Open scatter table search & insertion) L
    6.4 523 Program D (Open addressing with double hashing) D
    5 571-573 #8 #8
    5.2 617 #11 #11
    5.2.1 597 #3 #3
    5.2.1 624 #31 #31
    5.2.2 629-630 #12 #12
    6.3 722 #9 #9

    • Please help to keep this site up to date! If you want to point out important material or projects that are not listed here, if you find errors or want to suggest improvements, please send email to email