TAOCP/1

By Hal Canary, 2007-05-12 12:19:20 (link)
#computers-code

I bought a boxed set of Knuth's Art of Computer Programming last week. As you may or may not know, TAOCP demonstrates programs in assembly for a mythical computer known as the MIX 1009. MIX would not have been out of place in 1965, but is hopelessly outdated today. Nonetheless, I learned enough MIX to write the following program in the MIX Assembly Language.

* factorial.mixal
*
* calculate n factorial in MIXAL
*
* loops on rI1 from n down to 0
*
* n! must fit into a 30-byte word, or it overflows
* n must fit into a 12-byte index register,
* n must be positive.
*
* if n! overflows, it will throw an error.
*
* Tested with GNU MDK 1.2.3.
*
* assemble with:
*	mixasm factorial.mixal
* execute with:
*	mixvm --run factorial.mix
*
* This program is dedicated to the public domain.
*      ---Hal Canary, https://halcanary.org/
*
n	EQU	11	* Argument
pp	EQU	1000	* pointer to a memory address.
*			* We make use of pp and pp+1
term    EQU     19	* terminal
        ORIG    3000
start	ENTA	1
	ENTX	0
	ENT1	n
loop	ST1	pp
	MUL	pp	* pp! == pp * (pp-1)!
	CMPA	0	* Check for overflow
	JNE	ovrflw
	SLAX	5	* Shift rX back to rA.
	DEC1	1	* k <- k-1
	J1P	loop	* if (k > 0) loop back
	CHAR	0	* rAX <- sprintf("%i", rA)
	STX	pp+1
	STA	pp
	OUT	pp(term)	* output pp and pp+1
        HLT
ovrflw	OUT	error0(term)
	HLT
error0	ALF	OVERF
	ALF	LOW
        END     start

Notice how I had to write to memory in order to multiply two numbers together! Crazy.

(Factorial calculations are a common assignment in computer science 101, as they are a simple exercise in a language's looping constructs.)

Here's the same program, reimplemented for the Emmix 2009:

* factorial.mmo
*
* Calculate factorial(NUMBER) in MMIXAL.
* If it overflows, it exits with no output.
*
* Tested with Donald E. Knuth's MMIXware (v20060918).
*
* Assemble with:
*	mmixal factorial.mms
* Execute with:
*	mmix factorial.mmo
*
* This program is dedicated to the public domain.
*	---Hal Canary, https://halcanary.org/

NUMBER	IS	12

	LOC	Data_Segment
buf	BYTE	0		this buffer will be 21
	LOC	buf+21			   bytes long
pbuf	GREG	@		pointer to the end of
num	OCTA	NUMBER			   the buffer
pnum	GREG	num
n	IS	pnum		the number
r	GREG	0		the remainder
k	IS	r		counter
ov	GREG	0

	LOC	#100
Main	LDO	n,pnum,0	load number from memory
	SUB	k,n,1
1H	MULU	n,n,k
	GET	ov,rH		check for overflow
	BP	ov,overflow
	SUB	k,k,1
	PBP	k,1B

* Print out n, followed by a newline.
	SET	r,0		'\0' character
	STBU	r,pbuf
	SUB	pbuf,pbuf,1
	SET	r,10		'\n' char
	STBU	r,pbuf
2H	SUB	pbuf,pbuf,1
	DIVU	n,n,10
	GET	r,rR		final digit is the remainder
	INCL	r,'0'		convert digit to ASCII char
	STBU	r,pbuf		store digit char in buffer
	PBP	n,2B		if there is more chars, loop
	SET	$255,pbuf	set $255 to point to the
	TRAP	0,Fputs,StdOut		most signif. digit.
	TRAP	0,Halt,0

overflow TRAP	0,Halt,0

This processor required me to (gasp) rewrite 'printf("%u",n);', which was the hardest part of the program.

(back)