Z-Machine - Revision history

Admin: /* Subtraction Pseudocode */

2017-04-25T03:21:12Z

Subtraction Pseudocode

← Older revision		Revision as of 03:21, 25 April 2017
Line 208:		Line 208:
	===Subtraction Pseudocode===		===Subtraction Pseudocode===

	The structure of the Z-Machine code above came to me in a stroke of inspiration on the subway. I needed a way to ONLY increment I2 the first time through, so that it can stay ahead of the neighbor cell by 1 (this is the subtraction mechanism). I did this by using a jump condition (instruction 005) that is ''always'' false the first time through. By forcing the jump condition to branch the first time through, it allows us to skip one instruction. By inserting a second jump statement, we can ensure that the instruction that was skipped the first time through is run every other time.		The structure of the Z-Machine code above came to me in a stroke of inspiration on the subway. I needed a way to ONLY increment ix2 the first time through, so that it can stay ahead of the neighbor cell by +1 (this is the subtraction mechanism, minus 1). I did this by using a jump condition (instruction 005) that is ''always'' false the first time through. By forcing the jump condition to branch the first time through, it allows us to skip one instruction. By inserting a second jump statement, we can ensure that the instruction that was skipped the first time through is run every other time.

	<pre>		<pre>
Line 220:		Line 220:
	}		}
	</pre>		</pre>



	=Implementing the Less Than Operator=		=Implementing the Less Than Operator=

Admin: /* Implementing Greater Than Comparison Operator */

2017-04-25T03:19:23Z

Implementing Greater Than Comparison Operator

← Older revision		Revision as of 03:19, 25 April 2017
Line 223:		Line 223:


	=Implementing ~~Greater~~ Than ~~Comparison~~ Operator=		=Implementing the Less Than Operator=

	Another challenging operation to implement with the Z-Machine is the comparison operator. Suppose that an operator places two numbers into the first two memory positions of the Z-Machine. That is, index 0 contains a number A, and index 1 contains a number B. Supposing these numbers are both natural numbers (either 0 or positive integers), a comparison operator will compare the two numbers, select the smaller (or larger) of the two numbers, and place it into the third position in memory (index 2).		Another challenging operation to implement with the Z-Machine is the comparison operator. Suppose that an operator places two numbers into the first two memory positions of the Z-Machine. That is, index 0 contains a number A, and index 1 contains a number B. Supposing these numbers are both natural numbers (either 0 or positive integers), a comparison operator will compare the two numbers, select the smaller (or larger) of the two numbers, and place it into the third position in memory (index 2).

			We'll cover how to select the smaller of the two numbers and put it into the third slot in memory.

	The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.		The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.
Line 231:		Line 233:
	==Z-Machine Code==		==Z-Machine Code==

	In order to increment the memory cell at index 2 to hold the smaller of the two numbers at index 0 and index 1, we can use the following Z-Machine code, which continually checks if the number at index 2 is equal to either the number at index 0 or the number at index 1, and stops when it reaches ~~one or the other (~~the smaller of the two).		In order to increment the memory cell at index 2 to hold the smaller of the two numbers at index 0 and index 1, we can use the following Z-Machine code, which continually checks if the number at index 2 is equal to either the number at index 0 or the number at index 1, increments if false, and stops when true (when it reaches the smaller of the two).

	<pre>		<pre>

Admin: /* Z-Machine Code */

2017-04-25T03:17:50Z

Z-Machine Code

← Older revision		Revision as of 03:17, 25 April 2017
Line 231:		Line 231:
	==Z-Machine Code==		==Z-Machine Code==

	~~This operation~~ can ~~be implemented in the Z-Machine using~~ the following Z-Machine code:		In order to increment the memory cell at index 2 to hold the smaller of the two numbers at index 0 and index 1, we can use the following Z-Machine code, which continually checks if the number at index 2 is equal to either the number at index 0 or the number at index 1, and stops when it reaches one or the other (the smaller of the two).

	<pre>		<pre>
Line 247:		Line 247:
	011 Z4		011 Z4
	</pre>		</pre>

			Note that this code can successfully handle the case of either number (or both) being 0 or any other positive integer.

	==Z-Machine Comparison Operator Pseudocode==		==Z-Machine Comparison Operator Pseudocode==

Admin: /* Implementing Greater Than Comparison Operator */

2017-04-25T03:15:59Z

Implementing Greater Than Comparison Operator

← Older revision		Revision as of 03:15, 25 April 2017
Line 229:		Line 229:
	The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.		The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.

	~~This operation is a bit tricky to implement using the three operations of the~~ Z-Machine~~, but it can be done.~~		==Z-Machine Code==

			This operation can be implemented in the Z-Machine using the following Z-Machine code:

			<pre>
			001 Z2 // smaller of the two numbers
			002 Z3 // zero
			003 Z4 // one
			004 I4

			005 J0,2 --> 007
			006 J3,4 --> 011
			007 J1,2 --> 009
			008 J3,4 --> 011
			009 I2
			010 J3,4 --> 005
			011 Z4
			</pre>

	==Z-Machine Comparison Operator Pseudocode==		==Z-Machine Comparison Operator Pseudocode==
Line 238:		Line 253:

	<pre>		<pre>
	// The operator ~~sets these two numbers as the initial Z-Machine state:~~		// The operator begins by setting ix0 and ix1 to the two numbers to be compared.
	ix0 ~~= (the first number, A)~~		// The smaller of the two numbers will be placed into ix2
	ix1 ~~= (~~the ~~second number, B)~~

	// ~~Zero out the cell that stores the~~ smaller of ~~A and B.~~
	ix2 = 0		ix2 = 0

	~~// These are used to create statements that are guaranteed to be true~~
	zero = 0		zero = 0
	~~zero2 = 0~~
	one = 0		one = 0
	one++		one++

	if( ix0 != ix2 ) {		// check if ix2 is the first number
	jump to ~~check~~ if ix1 == ix2		if neq(ix0, ix2) --> jump to if neq(ix1, ix2)
	}		if neq(zero,one) --> finished, ix0 is the smaller number, jump to cleanup
			if neq(ix1, ix2) --> jump to increment ix2
	if(~~always true~~) {		if neq(zero, one) --> finished, ix1 is the smaller number, jump to cleanup
	~~jump to end~~, ~~because~~ ix0 ~~== ix2 and we found~~ the smaller ~~of the two numbers~~		ix2++
	}		if neq(zero,one) --> jump to top, if neq(ix0, ix2)
			clean up
	if( ix1 != ix2 ) {
	jump to ~~incrementing~~
	}

	if( ~~always true~~) {
	~~jump to end~~, ~~because~~ ix1 ~~== ix2 and we found~~ the smaller ~~of the two numbers~~
	}

	// (~~here we increment variables~~)

	~~end: zero out any temporary variables~~
	</pre>		</pre>

Admin: /* Implementing Greater Than Comparison Operator */

2017-04-25T02:59:25Z

Implementing Greater Than Comparison Operator

← Older revision		Revision as of 02:59, 25 April 2017
Line 229:		Line 229:
	The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.		The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.

	This operation is a bit tricky to implement using the three operations of the Z-Machine, but it can be done. Here is the pseudocode:		This operation is a bit tricky to implement using the three operations of the Z-Machine, but it can be done.



			==Z-Machine Comparison Operator Pseudocode==

			Here is the pseudocode for the greater than operator:

	<pre>		<pre>

Admin: /* Solution 2: Dealing with Zeros */

2017-04-25T02:58:13Z

Solution 2: Dealing with Zeros

← Older revision		Revision as of 02:58, 25 April 2017
Line 100:		Line 100:
	// increment by amount in index 0		// increment by amount in index 0
	009 J0,8 --> 014		009 J0,8 --> 014
	010 I6		010 I6
	011 J4,6 --> 014		011 J4,6 --> 014
	012 I4		012 I4
	013 I3		013 I3
	014 J0,4 --> 009		014 J0,4 --> 009

	// increment by amount in index 1		// increment by amount in index 1
	015 J1,8 --> 020		015 J1,8 --> 020
	016 I7		016 I7
	017 J7,8 --> 020		017 J7,8 --> 020
	018 I5		018 I5
	019 I3		019 I3
	020 J1,5 --> 017		020 J1,5 --> 017

	021 Z4		021 Z4
	022 Z5		022 Z5
	023 Z6		023 Z6
	024 Z7		024 Z7
	</pre>		</pre>

Admin: /* Implementing Subtraction */

2017-04-25T02:39:26Z

Implementing Subtraction

← Older revision		Revision as of 02:39, 25 April 2017
Line 221:		Line 221:
	</pre>		</pre>



			=Implementing Greater Than Comparison Operator=

			Another challenging operation to implement with the Z-Machine is the comparison operator. Suppose that an operator places two numbers into the first two memory positions of the Z-Machine. That is, index 0 contains a number A, and index 1 contains a number B. Supposing these numbers are both natural numbers (either 0 or positive integers), a comparison operator will compare the two numbers, select the smaller (or larger) of the two numbers, and place it into the third position in memory (index 2).

			The pseudocode approach to implement the comparison operator is to create a counter that start at zero, and check if it is equal to A or B (the numbers at index 0 and index 1). If we continue to increment our counter, and check if it is equal to A or B, and stop when it reaches either A or B, we can guarantee that we will stop when the counter reaches the smaller of the two numbers.

			This operation is a bit tricky to implement using the three operations of the Z-Machine, but it can be done. Here is the pseudocode:

			<pre>
			// The operator sets these two numbers as the initial Z-Machine state:
			ix0 = (the first number, A)
			ix1 = (the second number, B)

			// Zero out the cell that stores the smaller of A and B.
			ix2 = 0

			// These are used to create statements that are guaranteed to be true
			zero = 0
			zero2 = 0
			one = 0
			one++

			if( ix0 != ix2 ) {
			jump to check if ix1 == ix2
			}

			if(always true) {
			jump to end, because ix0 == ix2 and we found the smaller of the two numbers
			}

			if( ix1 != ix2 ) {
			jump to incrementing
			}

			if( always true) {
			jump to end, because ix1 == ix2 and we found the smaller of the two numbers
			}

			// (here we increment variables)

			end: zero out any temporary variables
			</pre>

Admin: /* Subtraction Pseudocode */

2017-04-21T07:56:07Z

Subtraction Pseudocode

← Older revision		Revision as of 07:56, 21 April 2017
Line 220:		Line 220:
	}		}
	</pre>		</pre>




			[[Category:CS]]
			[[Category:Puzzles]]
			[[Category:Circuits]]

Admin: /* Solution 2: Dealing with Zeros */

2017-04-21T07:55:15Z

Solution 2: Dealing with Zeros

← Older revision		Revision as of 07:55, 21 April 2017
Line 86:		Line 86:
	==Solution 2: Dealing with Zeros==		==Solution 2: Dealing with Zeros==

	A second solution that is a bit more challenging is dealing with the case of possible zeros in the first or second position. The algorithm above will increment the result and the temporary variable at least once (similar to a do-while loop structure), which will always cause the comparison operation <code>J2,0<code/> or <code>J3,1</code> to fail. Here is code that can deal more gracefully with a zero in either the first or second positions:		A second solution that is a bit more challenging is dealing with the case of possible zeros in the first or second position. The algorithm above will increment the result and the temporary variable at least once (similar to a do-while loop structure), which will always cause the comparison operation <code>J2,0</code> or <code>J3,1</code> to fail. Here is code that can deal more gracefully with a zero in either the first or second positions:

	<pre>		<pre>

Admin: /* Solution 2: Dealing with Zeros */

2017-04-21T07:54:43Z

Solution 2: Dealing with Zeros

← Older revision		Revision as of 07:54, 21 April 2017
Line 87:		Line 87:

	A second solution that is a bit more challenging is dealing with the case of possible zeros in the first or second position. The algorithm above will increment the result and the temporary variable at least once (similar to a do-while loop structure), which will always cause the comparison operation <code>J2,0<code/> or <code>J3,1</code> to fail. Here is code that can deal more gracefully with a zero in either the first or second positions:		A second solution that is a bit more challenging is dealing with the case of possible zeros in the first or second position. The algorithm above will increment the result and the temporary variable at least once (similar to a do-while loop structure), which will always cause the comparison operation <code>J2,0<code/> or <code>J3,1</code> to fail. Here is code that can deal more gracefully with a zero in either the first or second positions:

			<pre>
			001 Z3
			002 Z4 // temp 0
			003 Z5 // temp 1
			004 Z6 // is index 0 a zero?
			005 Z7 // is index 1 a zero?
			006 Z8 // zero
			007 Z9 // one
			008 I9

			// increment by amount in index 0
			009 J0,8 --> 014
			010 I6
			011 J4,6 --> 014
			012 I4
			013 I3
			014 J0,4 --> 009

			// increment by amount in index 1
			015 J1,8 --> 020
			016 I7
			017 J7,8 --> 020
			018 I5
			019 I3
			020 J1,5 --> 017

			021 Z4
			022 Z5
			023 Z6
			024 Z7
			</pre>

			Or, in pseudo Z-Machine code:

	<pre>		<pre>