How to resolve the algorithm 100 doors step by step in the X86 Assembly programming language

Published on 12 May 2024 09:40 PM
#X86 assembly

How to resolve the algorithm 100 doors step by step in the X86 Assembly programming language

Table of Contents

Problem Statement

There are 100 doors in a row that are all initially closed. You make 100 passes by the doors. The first time through, visit every door and  toggle  the door  (if the door is closed,  open it;   if it is open,  close it). The second time, only visit every 2nd door   (door #2, #4, #6, ...),   and toggle it.
The third time, visit every 3rd door   (door #3, #6, #9, ...), etc,   until you only visit the 100th door.

Answer the question:   what state are the doors in after the last pass?   Which are open, which are closed?

Alternate:
As noted in this page's   discussion page,   the only doors that remain open are those whose numbers are perfect squares. Opening only those doors is an   optimization   that may also be expressed; however, as should be obvious, this defeats the intent of comparing implementations across programming languages.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm 100 doors step by step in the X86 Assembly programming language

Source code in the x86 programming language

		.NOLIST

; The task can be completed in 48 and "half" steps:
; On the first pass ALL doors are opened.
; On the second pass every EVEN door is closed.
; So, instead of all closed, the doors can initially be:
; Every odd door open, every even door closed and start at pass 3.
; On 51st and all the next passes, only one door is visited per pass:
; On 51st pass door 51, on 52nd pass door 52 etc.
; So, after pass 50, we can make "half a pass" starting with door 51
; and toggling every door up to and including 100.
; The code uses only volatile registers, so, no string (STOS etc) instructions.

		TITLE	100 Doors
		PAGE	, 132
		.686
		.MODEL	FLAT
		OPTION	CASEMAP:NONE

		.SFCOND
		.LIST

; =============================================================================

		.DATA?

Doors		BYTE	100 DUP ( ? )

; =============================================================================

		.CODE

Pass_Doors	PROC

		MOV	EDX, OFFSET Doors	; Initialize all doors.
		MOV	ECX, SIZEOF Doors / SIZEOF DWORD
		MOV	EAX, 01010101h		; This does first and second pass.

Close_Doors:	MOV	[ EDX ], EAX
		ADD	EDX, SIZEOF DWORD
		LOOP	Close_Doors

		MOV	ECX, 2			; Pass and step.

Pass_Loop:	MOV	EDX, OFFSET Doors

		ASSUME	EDX:PTR BYTE

Doors_Loop:	XOR	[ EDX ], 1		; Toggle this door.
		ADD	EDX, ECX                ; Advance.
		CMP	EDX, OFFSET Doors[ SIZEOF Doors ]

		JB	Doors_Loop

		INC	ECX
		CMP	ECX, SIZEOF Doors

		JB	Pass_Loop

		XOR	Doors[ SIZEOF Doors -1 ], 1 ; This is pass 100.
		RET

Pass_Doors	ENDP

; =============================================================================

		END

You may also check:How to resolve the algorithm Non-decimal radices/Input step by step in the C programming language
You may also check:How to resolve the algorithm Jacobsthal numbers step by step in the Maxima programming language
You may also check:How to resolve the algorithm Population count step by step in the Nim programming language
You may also check:How to resolve the algorithm Topological sort step by step in the Forth programming language
You may also check:How to resolve the algorithm Binary digits step by step in the Java programming language