Outline of my Assembly Program to Set up and Run the Lehmer chains.

Last Up date: 2005 September 23
Recent changes: Coppied from old web site
where Iadded explanation that proceeds the first horizontal bar.

I created the following by going through the source in the order it would execute and explaining each major function of the program. In assembly code I usually put the initialization portion which is only used once in the data buffer and let it get overlaid. This gives more "horsepower" using less memory.

Most of what is done to set up the chains gets overlaid by the "running" tables. If you don't like that: Go write your own program!

I wrote the program using an assembler that is available on the internet. See Eric's Assembler for more details.

    I have not included the actual source listing, because:
  1. The logic of the program does not simply go from top to bottom of the listing. So it would be difficult for the uninitiated to follow.
  2. Many want to have a feel about how it is done, and maybe think about implementing this on other systems or in other languages. I felt giving them the steps would be more helpful if it did not involve the details of a specific processor. Yes, the code has comments; but as always they are short and would need this type explanation anyway.
  3. I don't want to have to explain the idiosyncrasies of the assembler.
  4. If I make minor changes, it would become obsolete.
  5. It would be a significant task to keep updating this with each modification.

Steps in Setting up the chains.
  1. Pick up the command line chain lengths one at a time.
      For each one:
    1. Move the ASCII to the build table image area at the end of the program.
      1. While picking up and moving each byte also convert the length to binary.
      2. When a non-ASCII character is found, denoting the end of the length parameter; put a TAB in the receiving area. The chain image follows this TAB.
      3. PUSH the binary of the length on the hardware stack building a length table for latter use.
    2. Following the TAB clear the chain to non-stop links. (? Fat Dashes.)
      1. Follow the table with a CR-LF
    3. Put a stop character (? Long vertical bar) in the table at locations: 0, 1 and all possible squares for that chain length.
      1. Generate the squares by successively adding odd integers to one
    4. Loop back to 1 for each chain length, until chain images for each length have been built.
    5. PUSH a word of zero on the stack to flag the end of the chain lengths table which has been built on the stack with the PUSH instruction.
  2. After all the squares table images are built we have to build tables for the specific number we are to factor.
    1. Read Std-In for the starting values for a and a2-N.
    2. Convert a to binary, mod the chain length.
      1. I put this in register CH
    3. Convert a2-N to binary, mod the chain length.
      1. I put this in register CL
    4. PUSH CX which puts a and a2-N values in another stack table.
    5. Loop back to 2 and do for all the chain lengths.
    6. PUSH a word of zero to flag the end of the a and a2-N values.
  3. Build a 2nd set of chain images. (The ones the user will see.)
    1. Pick up, but don't remove from the stack table a chain length.
    2. Transfer the ASCII length parameter through its following TAB to the new table.
    3. Use the first table as a translate table. (It has positions for the Squares, and non squares, for that number base.
    4. Get the a and a2-N values from the second stack table. (Don't remove them from the stack.)
    5. Generate 2a+1 the odd value to start adding to generate a2-N. Of course do this all mod the chain length.
    6. For each position in the new table calculate sequential a2-N and XLAT this against the first table.
    7. Loop back for each chain length, till all the new tables are built.
  4. Move the ASCII a value read in to start overlaying the previous initialization code.
  5. Jump to the beginning of the program which now moves the second set of chain tables to follow the ASCII a moved in the above step.
    The following is what I call the "Run Part" of the program.
  1. Print out the generated chain images and cycle on each depression of the space bar.
    1. The running part of the program cycles all of the chains and ANDs all the first links.
      • This takes 20 lines of assembly code.
    2. The bump a in ASCII decimal takes 11 lines of code.
    3. Test the "ANDed" first link bytes only takes a TEST and Jump Conditional instruction.
  2. The program then reads the keyboard to determine if it should go through another print cycle or exit.
That is all there is to the program. A couple of notes: Most compilers never generate code to dynamically modify instructions, or overwrite once used code. As an old compiler writer, I do it in virtually every program I write.

I used to claim I could write programs that took half as much memory and run twice as fast. Later I realized that I could make programs that only used a tenth as much memory, and ran about ten times as faster. With today's compilers I think I should jack that factor up to about a hundred in both cases.


Contact me at:
My phone #'s
For comments call, or e-mail me. Go to My Home Page or TOP of this page.