Machine-level Programming help

[beer]

We are doing machine-level programming in my intro to computing class. On our fictional computer, there are sixteen opcodes, of which seven are data storage/retrieval (load effective address, load/store direct, load/store indirect, load/store base+offset). Three instructions are operators (NOT, AND, and ADD), and the remaining six are various forms of branching, of which the only two we've used are conditional branching and trap vectors.

Our assignment is to create divide and modulus functions.

To multiply, we kept a pointer, and a running total, and added until the register that kept track of the number of times we had to add reached zero. But how would that work for divide?

 

[kherman]

Not sure if this helps, but inverse multiplication might work, AMD does this in thier processors.

Take the inverse of the denominator and multiply it to hte numerator. You now have divsion.

 

[beer]

To take the inverse requires a divide.

inverse of 2 is 1/2, 1/2 is physical a divide.

 

[michaelh20]

Given a number to divide something by, say divide 100 by 2, couldn't you
start with 2 and keep multiplying it by increasing numbers say

2*1
2*2
2*3
2*4

etc. and keep testing it to see if it is = to 100.. then you'd just need a couple of counters/registers to keep track. Not sure how this would work for non whole #s either.

Not very efficient huh?

I'm sure there must be some algorithm for this.

 

[beer]

Originally posted by: michaelh20
Given a number to divide something by, say divide 100 by 2, couldn't you
start with 2 and keep multiplying it by increasing numbers say

2*1
2*2
2*3
2*4

etc. and keep testing it to see if it is = to 100.. then you'd just need a couple of counters/registers to keep track. Not sure how this would work for non whole #s either.

Not very efficient huh?

I'm sure there must be some algorithm for this.

We don't have a bitwise comparison operator, either.

 

[notfred]

Originally posted by: Elemental007
To multiply, we kept a pointer, and a running total, and added until the register that kept track of the number of times we had to add reached zero. But how would that work for divide?

Do the opposite. Subtract instead of add.

10/2

10-2=8, 8-2=6, 6-2=4, 4-2=2, 2-2=0

5 subtractions. Therefore, 10/2 = 5.

 

[FeathersMcGraw]

Originally posted by: Elemental007
We are doing machine-level programming in my intro to computing class. On our fictional computer, there are sixteen opcodes, of which seven are data storage/retrieval (load effective address, load/store direct, load/store indirect, load/store base+offset). Three instructions are operators (NOT, AND, and ADD), and the remaining six are various forms of branching, of which the only two we've used are conditional branching and trap vectors.

Our assignment is to create divide and modulus functions.

To multiply, we kept a pointer, and a running total, and added until the register that kept track of the number of times we had to add reached zero. But how would that work for divide?

The naive way to do this: repeatedly subtract the divisor from the dividend until the result is smaller than the dividend. The number of times you do this is an integral quotient. The number remaining is the modulus.

 

[beer]

We don't have a bitwise comparison operator, but we have three one-bit registers, N, Z, and P, that mark the last value loaded into any of the eight general registers. if the last number loaded into a general register was negative, then the controller sets N=1, and Z=P=0. The same holds true for zero and positive values, respectively.

BTW, the computer only handles 2s-complement integers, so I can mark negative values.

 

[beer]

Originally posted by: notfred

Originally posted by: Elemental007
To multiply, we kept a pointer, and a running total, and added until the register that kept track of the number of times we had to add reached zero. But how would that work for divide?

Do the opposite. Subtract instead of add.

10/2

10-2=8, 8-2=6, 6-2=4, 4-2=2, 2-2=0

5 subtractions. Therefore, 10/2 = 5.

Simple....in theory.

However I can only see when we go to 0 or less after the operation has already taken place. In other words, once I subtract to 0 or to a negative number, only then do the registers indicate that I've gone too far.

I can't just do a while loop.

 

[michaelh20]

>>We don't have a bitwise comparison operator, either.

So if you want to see if (X == 100), how about

doing if (NOT (( NOT X ) AND 100))

which would give True.. I guess.. can you at least do Equals?

then (NOT X) AND 100 would be 0

 

[beer]

The conditional branch instruction allows me to inspect any number of the three one-bit registers and, if the register contains a 1, I can change the instruction pointer to point to a new instruction, as long as it is on the same page as the current instruction.

 

[beer]

There is no equality operator.

Just AND, NOT, and ADD

 

[notfred]

Originally posted by: Elemental007

Originally posted by: notfred

Originally posted by: Elemental007
To multiply, we kept a pointer, and a running total, and added until the register that kept track of the number of times we had to add reached zero. But how would that work for divide?

Do the opposite. Subtract instead of add.

10/2

10-2=8, 8-2=6, 6-2=4, 4-2=2, 2-2=0

5 subtractions. Therefore, 10/2 = 5.

Simple....in theory.

However I can only see when we go to 0 or less after the operation has already taken place. In other words, once I subtract to 0 or to a negative number, only then do the registers indicate that I've gone too far.

I can't just do a while loop.

If you have conditional branching why can't you do a while loop?

 

[beer]

Think of it this way:

I have an instruction that says, 'look at the N register. If it is 1, then jump to this instruction."

So look at it like this
16 / 5 = 1
N = 1? NO
11 / 5 = 2
N = 1? NO
6 / 5 = 3
N = 1? NO
1 / 5 = 4
N = 1? NO
1 / 5 = 5

Only now does N=1...after the instruction has already completed.

 

[FeathersMcGraw]

Originally posted by: Elemental007

Simple....in theory.

However I can only see when we go to 0 or less after the operation has already taken place. In other words, once I subtract to 0 or to a negative number, only then do the registers indicate that I've gone too far.

I can't just do a while loop.

Addition and subtraction are undoable operations. It's not like you can't regenerate the state of the previous loop iteration, you know.

 

[beer]

Originally posted by: FeathersMcGraw

Originally posted by: Elemental007

Simple....in theory.

However I can only see when we go to 0 or less after the operation has already taken place. In other words, once I subtract to 0 or to a negative number, only then do the registers indicate that I've gone too far.

I can't just do a while loop.

Addition and subtraction are undoable operations. It's not like you can't regenerate the state of the previous loop iteration, you know.

There has to be a better way than that though. I've thought of that, and I don't think that's how we're supposed to do it.

 

[notfred]

Originally posted by: Elemental007

Originally posted by: FeathersMcGraw

Originally posted by: Elemental007

Simple....in theory.

However I can only see when we go to 0 or less after the operation has already taken place. In other words, once I subtract to 0 or to a negative number, only then do the registers indicate that I've gone too far.

I can't just do a while loop.

Addition and subtraction are undoable operations. It's not like you can't regenerate the state of the previous loop iteration, you know.

There has to be a better way than that though. I've thought of that, and I don't think that's how we're supposed to do it.

If the instructor didn't tell you how to do it, then you're typically open to do whatever works.

link

 

[FeathersMcGraw]

Originally posted by: Elemental007

There has to be a better way than that though. I've thought of that, and I don't think that's how we're supposed to do it.

Oh, sure, post hoc add elegance into the solution requirements. Maybe you should be in marketing instead of engineering.

If you ignore the zero flag and simply iterate until the negative flag is set, adding the dividend to your running result always produces the modulus. If the modulus is zero, decrement one from the quotient. I believe it can't be made any nicer than that without a test operation that doesn't alter state.

 

[CSMOOTH]

To divide you would use a conditional loop:
a / b = c
here is the code in C and assembly

c=0
**if (b > a)
c = 0
modulus = b


else
while (a > b)
c++
a = a - b

modulus = a
c is dividend

MASM esque:

mov edx,0
**L2: cmp a,b
**jbe L1
inc edx
sub eax,ebx
jmp L2
L1:

eax has the modulus and edx has the divisor

** this is the line that you are having troubles with. There are a few ways to take care of this. If you have the compare and jump instructions then fine. If not, you can create a loop with a counter that is based on i, the OR with the zero and negative flag. If either goes off after the subtraction then you are done and the counter is set to 1. Use the AND between i and 1 and you have a valid loop control which will be 1 while A > B and 0 when A<B. That is what you are looking for I think.
Chris