Outline of my Assembly Program to Set up and Run the Lehmer chains.
Last Up date:
2005 September 23
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
Eric's Assembler for more details.
I have not included the actual source listing, because:
- 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
- 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.
- I don't want to have to explain the idiosyncrasies of the assembler.
- If I make minor changes, it would become obsolete.
- It would be a significant task to keep updating this with each
Steps in Setting up the chains.
After all the squares table images are built we have to build tables
for the specific number we are to factor.
- Pick up the command line chain lengths one at a time.
For each one:
- Move the ASCII to the build table image area at the end of the program.
- While picking up and moving each byte also convert the
length to binary.
- 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
- PUSH the binary of the length on the hardware stack building a
length table for latter use.
- Following the TAB clear the chain to non-stop links. (? Fat Dashes.)
- Follow the table with a CR-LF
- Put a stop character (? Long vertical bar) in the table at locations:
0, 1 and all possible squares for that chain length.
- Generate the squares by successively adding odd integers to
- Loop back to 1 for each chain length, until chain images for each
length have been built.
- 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
Build a 2nd set of chain images. (The ones the user will see.)
- Read Std-In for the starting values for a and
- Convert a to binary, mod the chain length.
- I put this in register CH
- Convert a2-N to binary, mod the chain length.
- I put this in register CL
- PUSH CX which puts a and
a2-N values in another stack table.
- Loop back to 2 and do for all the chain lengths.
- PUSH a word of zero to flag the end of the a and
Move the ASCII a value read in to start overlaying the
previous initialization code.
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
- Pick up, but don't remove from the stack table a chain length.
- Transfer the ASCII length parameter through its following TAB to the
- Use the first table as a translate table. (It has positions for the
Squares, and non squares, for that number base.
- Get the a and
a2-N values from the second stack table.
(Don't remove them from the stack.)
- Generate 2a+1 the odd value to start adding to generate
a2-N. Of course do this all mod the chain length.
- For each position in the new table calculate sequential
a2-N and XLAT this against the first table.
- Loop back for each chain length, till all the new tables are
- This may well cover all, or more of, the above initialization
code that proceeds this step; depending on the number and size of the
The following is what I call the "Run Part" of the program.
That is all there is to the program. A couple of notes:
- Print out the generated chain images and cycle on each depression of
the space bar.
- The running part of the program cycles all of the chains and ANDs
all the first links.
- This takes 20 lines of assembly code.
- The bump a in ASCII decimal takes 11 lines of code.
- Test the "ANDed" first link bytes only takes a TEST and Jump
- The program then reads the keyboard to determine if it should go
through another print cycle or exit.
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.
- All the arithmetic is done in the 8-bit registers of the 8086
processor. No values are greater that the chain length.
- Pointers are 16-bit words, all are either on the hardware stack or
put into MOV instructions as immediate values.
- In only 2 places is a register PUSHed to temporarily free it up for
- In fact, there are only two POP one register instructions in the
entire program; and they are only executed once for each chain length
- There are only two CALL's they are to a subroutine to convert the
a and the a2-N values to a single byte.
Everything else is inline code, with loops of course.
- The "variable length data area" is at the end of, or over
top of, the initialization code.
- The variable length data tables are "underneath" the hardware
stack. No other data areas or tables are used.
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:
For comments call, or
My Home Page
of this page.