Get best of the week

El programa decimal más corto

En 1984 , se lanzó el libro de culto de Steven Levy, Hackers: Heroes of the Computer Revolution . Hay una traducción rusa de aficionados, pero está lejos de ser ideal. Me comprometí a corregir las inexactitudes, poniendo el original en inglés al lado (por cierto, y no está exento de pecado), pero lo abandoné después del segundo capítulo. De una forma u otra, quiero llamar su atención sobre un fragmento (puede leerlo en un artículo separado ) dedicado a la subrutina para imprimir un número en el sistema decimal. ¿Cuánto se puede reducir tal programa? Cual es el limite?

En agosto de 2018, escribí un programa para medir el tiempo de ejecución exacto de las instrucciones del procesador soviético 1801BM1 (tiene un conjunto de instrucciones PDP-11 ). Saber el tiempo exacto (en ciclos de procesador) era necesario al trabajar en la demostración " Good Apple " para la computadora BK 0011M. Quería ver los resultados de la medición en decimal. Para hacer esto, tuve que escribir mi propia subrutina: las funciones del sistema no estaban disponibles debido a los detalles de la prueba.

Lo primero que hice fue crear una matriz TEN con potencias de 10. El procedimiento toma un número en el registro R0, la salida es una cadena de texto en NUMBER. Importante: ¡ no hay instrucciones de división en el procesador !

	MOV #NUMBER,R1	; pointer to output text string
	MOV #TEN,R5
1:	CMP (R5)+,R0 	; skip leading zeros
	BHI 1		; branch if higher, for 16-bit not signed
	MOV -(R5),R3
	BEQ 4		; if less then 10

2:	MOV #47.,R4	; 0 symbol in ASCII codepage - 1
3:	INC R4		; count digits
	SUB R3,R0
	BHIS 3		; branch if higher or same, for 16-bit not signed
	MOVB R4,(R1)+	; print R4

	ADD (R5)+,R0
	MOV (R5),R3
	BNE 2

4:	ADD #48.,R0	; 0 symbol in ASCII codepage
	MOVB R0,(R1)+	; print R0
	CLRB (R1) 	; end of text marker
	RET

TEN:	.WORD 10000.,1000.,100.,10.,0

Para comprender el ensamblador PDP-11, es suficiente recordar que los argumentos se escriben de izquierda a derecha (primero la fuente, luego el receptor), y los comandos de ramificación condicional comienzan con la letra B (de la ramificación de palabra - ramificación). No describiré el algoritmo, no tiene ningún interés y se proporciona aquí solo como punto de partida. El tamaño de esta rutina es de 22 palabras (sin incluir datos).

Después de que todo funcionó, de repente recordé la historia del libro de Stephen Levy: los hackers lucharon por reducir el tamaño de un programa similar, y también por la arquitectura PDP. Es cierto que tenían PDP-1, pero unos años después obtuvieron PDP-11.

imagen

Al abrir el libro, encontré una descripción extremadamente vaga. Los hackers del MIT comenzaronigual que yo de la lista de lugares decimales. Pero lo que sucedió después no está claro en el texto. Obviamente, esto tampoco fue claro para el autor del libro; simplemente escribió palabras comunes de los labios de los testigos de ese concurso de piratería.

Tuve que profundizar en el archivo de programas de Internet para PDP-1 . Hay muchas cosas interesantes: Minskytron, Munching squares y otros llamados "hacks de pantalla" (por cierto, es notable que ya entonces, a principios de los años 60, los hackers del MIT usaban el término " demo " en el mismo sentido en que lo usamos ahora) en el demoscene). Hay muchas rutinas del sistema en el archivo, pero, desafortunadamente, no hay un número decimal entre ellas.

Luego, armado con un depurador, decidí ver cómo se implementaba este procedimiento en el sistema operativo MKDOS, que utilizo en BK 0010 y BK 0011M. ¡Oh milagro! - Después de mirar de cerca, me di cuenta de que el subprograma encaja muy bien con la descripción nebulosa del libro "Hackers". Aquí está su código:

	MOV #10.,R4
	CLR R2
1:	CLR R1
2:	SUB R4,R0 	;    10,    
	BLO 3
	INC R1 		;  -   
	BR 2
3:	ADD R4,R0
	ADD #48.,R0 	; ASCII-  0
	INC R2		;  -   
	MOVB R0,-(SP)
	MOV R1,R0 	;    -   
	BNE 1
	INC R2
	MOVB #32.,-(SP)	; ASCII- 
4:	MOVB (SP)+,R0
	CALL PRINT
	SOB R2,4	;     
	RET

El programa forma una cadena de texto en la pila, luego llama al procedimiento de impresión para cada carácter guardado. Aparentemente, esto es exactamente lo que se entiende en el libro de Stephen Levy bajo la frase "se convierte de manera opuesta, y con la ayuda de un ingenioso enfoque de software, imprime en el orden correcto". Otras características del algoritmo deben quedar claras a partir de los comentarios sobre el código.

El tamaño de la subrutina es de 23 palabras , pero no se puede comparar directamente con mi subrutina: las condiciones son muy diferentes. Decidí rehacer el programa de MKDOS a mis condiciones: la formación de una cadena de texto en la memoria.

Al final, me di cuenta de que es mejor dejar solo la idea de restar el número 10 y escribir el resto desde cero. Después de varias vueltas de optimización de Sansara , obtuve lo siguiente:

	MOV #NUMBER,R1	; pointer to output text string
	CLRB -(R1)	; end of text marker
	MOV #10.,R4
1:	MOV #-1.,R5
2:	INC R5		; counter of 10s
	SUB R4,R0
	BHIS 2		; branch if higher or same
	ADD #58.,R0	; #10. + '0' ASCII code
	MOVB R0,-(R1)	; store R0 to text string
	MOV R5,R0	; let's count next how many 10s in number of 10s
	BNE 1
	RET		; returns text string pointer in R1

16 palabras , se alcanzó el límite (pensé), aquí está: ¡Nirvana, sobre el cual Stephen Levy escribió tan emocionalmente!

Qué trucos se aplican aquí:

  1. El primer comando establece el puntero no al principio, sino al final de la línea de texto. El texto se rellena de derecha a izquierda; esto también es conveniente porque en la salida obtenemos la dirección del comienzo de la línea, lista para ser enviada al procedimiento de impresión de texto.
  2. , . (INC R5) 1. 0, , ?.. , 10 – , . , . . – . : 1 , , 1 ( ). , , . . -1.
  3. 10, , , . – ( ). , – . , , . ( 10 10 ) . : ASCII- 0, ! , , . ADD #58.,R0 (48+10).

Estaba tan satisfecho con el programa que decidí compartirlo en el foro zx-pk.ru (sin sospechar nada de las tradiciones locales para criticar sin argumentos). La reacción de la comunidad fue algo como esto: "solo había que ver cómo lo hicieron en DEC, es un clásico".

Bueno, aquí hay un programa de DEC , la compañía que creó PDP-11 e incorporó a algunos de los hackers del MIT en sus filas:

; RETURNS:
; R0 = 0
; R1 -> byte following last digit in converted number
CVBTOD:	MOV	R0,-(SP)	;SAVE THE NUMBER PASSED TO US
	CLR	R0		;SET FOR CRUDE DIVIDE BY 10.
10$:	INC	R0		;BUMP QUOTIENT
	SUB	#10.,(SP)	;REDUCE NUMBER BY 10.
	BHIS	10$		;IF SIGN DIDN'T CHANGE...
	ADD	#10.+48.,(SP)	;MAKE REMAINDER PRINTABLE
	DEC	R0		;REDUCE QUOTIENT
	BEQ	20$		;IF ZERO, TIME TO PRINT
	CALL	CVBTOD		;OTHERWISE, RECURSE !
20$:	MOVB	(SP)+,(R1)+	;STORE A CONVERTED DIGIT
	RETURN			;UNWIND THE RECURSION

14 palabras , genial! ¿O no? Fui derrotado, pero echemos un vistazo más de cerca:

  1. Agregar el código ASCII del carácter 0 y el número 10 se realiza en una operación. Resulta que tal truco se usó en los años 70. Frio.
  2. El programa se llama a sí mismo de forma recursiva: ¡una solución hermosa!
  3. – , . – .
  4. R1 . , , .
  5. , ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !

Total, el tamaño real es de 16 palabras . Exactamente como el mío. Ambos programas constan de 12 instrucciones. Entonces, ¿cuál es mejor?

Incluso si reemplaza las llamadas de pila con llamadas de registro, el programa DEC será más lento debido a las instrucciones DEC R0 y CALL dentro del bucle.

Pero eso no es todo. Cuando comencé a escribir este artículo, noté que en mi programa había una instrucción MOV # 10 rudimentaria (de MKDOS), R4: no tiene otro sentido que acelerar el ciclo interno. Es hora de deshacerse de ella.

	MOV #NUMBER,R1	; pointer to output text string
	CLRB -(R1)	; end of text marker
1:	MOV #-1.,R5
2:	INC R5		; counter of 10s
	SUB #10.,R0
	BHIS 2		; branch if higher or same
	ADD #58.,R0	; #10. + '0' ASCII code
	MOVB R0,-(R1)	; store R0 to text string
	MOV R5,R0	; let's count next how many 10s in number of 10s
	BNE 1 		; loop if R0 is not zero
	RET		; returns text string pointer in R1

15 palabras . 11 instrucciones Ahora, parece, eso es todo.

Bueno, mis ideas de optimización han terminado. Fue un desafío inspirador, incluso una apuesta. Es notable que la idea propuesta por un estudiante pirata informático a principios de los años 60 para PDP-1 fue utilizada por DEC diez e incluso veinte años después, y se aplicó en la computadora soviética BK 0011M hasta principios de la década de 2000. Sorprendentemente, en el año 2018, fue posible reinventar y optimizar parcialmente el algoritmo. Característicamente, muchos consideraron esto imposible.

Entonces, aquí está el Santo Grial (según Stephen Levy), que los piratas informáticos de los años 60 intentaron encontrar: el programa decimal más corto para PDP. O ... tal vez incluso más corto?

Actualizar: Sabía que llegaría este día, pero no pensé tan pronto :) ¡Resultó que el programa se puede reducir en una palabra más! La idea fue sugerida en los comentarios de Mr_Rm :

	MOV #NUMBER,R1	; pointer to output text string
	CLRB -(R1)	; end of text marker
1:	CLR R5
2:	INC R5		; counter of 10s +1
	SUB #10.,R0
	BHIS 2		; branch if higher or same
	ADD #58.,R0	; #10. + '0' ASCII code
	MOVB R0,-(R1)	; store R0 to text string
	MOV R5,R0	; let's count how many 10s in number of 10s
	SOB R0,1	; subtract 1 and loop if not zero
	RET		; returns text string pointer in R1

14 palabras . 11 instrucciones
El truco es este. Recuerde, escribí que con la organización "incorrecta" del ciclo R5, ¿se obtiene uno más de lo necesario? Bueno, deja! Lo reduciremos al final del programa. En la versión anterior, R5 se copió a R0, después de lo cual el comando BNE (Rama si no es igual a cero) verificó R0, y si no es igual a cero, se fue al comienzo del ciclo. Primero nos gustaría reducir R0 en uno, y luego (si no obtuvieron cero) ir al principio ... Espere un minuto, pero este es un comando de ciclo SOB (Restar uno y derivar) normal. Es cierto que aquí no se usó de manera canónica: se cumple una vez y luego el contador de ciclos se deshilacha. Esto parece desalentador, pero si observa la versión anterior de la subrutina, queda claro cómo se acorta una nueva.

Enlaces útiles:

More articles:


All Articles