- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: John Wilson <wilson_at_dbit.dbit.com>

Date: Fri Jun 2 11:48:09 2000

On Fri, Jun 02, 2000 at 05:52:12AM -0700, Daniel A. Seagraves wrote:

*>Need this for my emulator, and nobody can explain to me how it works, and
*

*>I can't find any documentation that's useful to me. Specifically, I need stuff
*

*>like "you shift left and then check the last bit" etc. etc. Basically, I have
*

*>a bunch of ones and zeroes and I have to know how to add/subtract/multiply/
*

*>divide with them.
*

I'll assume you mean integer math.

ADD -- I hope I get this right:

For each bit, you have the two input bits, plus one sum output, and also one

carry in and one carry out. For the LSB, carry in is zero.

The sum output is the XOR of all three inputs (A, B, Cin), i.e. a change in

any input will toggle it. The Cout bit is set any time 2 or more of the

three inputs are set, so whatever that works out to (the OR of the three

possible ANDs would do it, but maybe there's an easier way).

SUB:

This is done by adding, with one of the inputs (hmm, is "subtrahend" the

word???) negated. Two's complement negation is done by complementing all the

bits and then adding one. And you can add the one by playing with the Cin bit

to the LSB (my mind is going blank, I can't think whether it has to be 1 or 0,

the sense of the carry is inverted when subtracting in this way).

MUL:

This is unsigned, for signed you have to take the absolute value and then

negate the result if the XOR of the input sign bits is 1.

It works exactly like multiplication by hand, except that you do it in binary,

which means you're just multiplying by 0 or 1 so the whole multiplication table

can be summed up with the AND operation:

- init sum to 0

- cycle through all the bits in A (doesn't matter which order), and for each

bit that's a 1, add in B shifted left by that number of places. So really,

just AND all the bits of B with that bit, shift it left to the same position,

and add it to the sum.

- you're done

DIV:

Once again this is unsigned, signed DIV instructions typically do funny things

with the sign of the remainder so check that carefully. Again it works just

like long division by hand, only in binary. So instead of wondering how many

times the divisor (?) goes into the dividend (?), you just wonder whether it

goes in at *all*, since you know the answer for each bit will just be 0 or 1.

So you can do it with a comparator and a subtractor, or you can always subtract

and decide whether to keep the result depending on whether it borrowed:

- init remainder to 0

- for all bits in the dividend, shift one bit left, filling the LSB with a 0

and shifting the bit out of the MSB into the LSB of the remainder (you

lose the MSB but it's always 0)

- if the remainder is .GE. the divisor, subtract the divisor from the

remainder and change the LSB of the (shifted) dividend from 0 to 1 (i.e.

INC it)

When you're done, the remainder is correct, and what was the dividend is now

the quotient. You could have assembled the quotient in its own register (since

you're generating it one bit at a time), but those LSBs of the dividend are

never used again so this is a cute way to do it all with one shift, and leads

to a very short routine in PDP-11 code (11 instructions IIRC).

Floating point */+- is exactly the same, but you have to worry about adding

and removing leading 1s (in formats that do that), chopping vs. rounding of the

LSB, and fixing the exponents to match. MUL and DIV are actually the easiest,

since all you have to do is add or sub the exponents and then do the integer

* or / operation on the mantissa, you can normalize it again in just one

or two shifts. With + and - you have to worry about shifting to align the

binary points before you start, and if the exponents are different by more

than the size of the mantissa there will be no overlap at all so you have

to ignore one or the other argument, depending on the FPU's rounding rules.

Once you align the points, do the + or -, and now you have to worry about

shifting left to re-normalize.

John Wilson

D Bit

Received on Fri Jun 02 2000 - 11:48:09 BST

Date: Fri Jun 2 11:48:09 2000

On Fri, Jun 02, 2000 at 05:52:12AM -0700, Daniel A. Seagraves wrote:

I'll assume you mean integer math.

ADD -- I hope I get this right:

For each bit, you have the two input bits, plus one sum output, and also one

carry in and one carry out. For the LSB, carry in is zero.

The sum output is the XOR of all three inputs (A, B, Cin), i.e. a change in

any input will toggle it. The Cout bit is set any time 2 or more of the

three inputs are set, so whatever that works out to (the OR of the three

possible ANDs would do it, but maybe there's an easier way).

SUB:

This is done by adding, with one of the inputs (hmm, is "subtrahend" the

word???) negated. Two's complement negation is done by complementing all the

bits and then adding one. And you can add the one by playing with the Cin bit

to the LSB (my mind is going blank, I can't think whether it has to be 1 or 0,

the sense of the carry is inverted when subtracting in this way).

MUL:

This is unsigned, for signed you have to take the absolute value and then

negate the result if the XOR of the input sign bits is 1.

It works exactly like multiplication by hand, except that you do it in binary,

which means you're just multiplying by 0 or 1 so the whole multiplication table

can be summed up with the AND operation:

- init sum to 0

- cycle through all the bits in A (doesn't matter which order), and for each

bit that's a 1, add in B shifted left by that number of places. So really,

just AND all the bits of B with that bit, shift it left to the same position,

and add it to the sum.

- you're done

DIV:

Once again this is unsigned, signed DIV instructions typically do funny things

with the sign of the remainder so check that carefully. Again it works just

like long division by hand, only in binary. So instead of wondering how many

times the divisor (?) goes into the dividend (?), you just wonder whether it

goes in at *all*, since you know the answer for each bit will just be 0 or 1.

So you can do it with a comparator and a subtractor, or you can always subtract

and decide whether to keep the result depending on whether it borrowed:

- init remainder to 0

- for all bits in the dividend, shift one bit left, filling the LSB with a 0

and shifting the bit out of the MSB into the LSB of the remainder (you

lose the MSB but it's always 0)

- if the remainder is .GE. the divisor, subtract the divisor from the

remainder and change the LSB of the (shifted) dividend from 0 to 1 (i.e.

INC it)

When you're done, the remainder is correct, and what was the dividend is now

the quotient. You could have assembled the quotient in its own register (since

you're generating it one bit at a time), but those LSBs of the dividend are

never used again so this is a cute way to do it all with one shift, and leads

to a very short routine in PDP-11 code (11 instructions IIRC).

Floating point */+- is exactly the same, but you have to worry about adding

and removing leading 1s (in formats that do that), chopping vs. rounding of the

LSB, and fixing the exponents to match. MUL and DIV are actually the easiest,

since all you have to do is add or sub the exponents and then do the integer

* or / operation on the mantissa, you can normalize it again in just one

or two shifts. With + and - you have to worry about shifting to align the

binary points before you start, and if the exponents are different by more

than the size of the mantissa there will be no overlap at all so you have

to ignore one or the other argument, depending on the FPU's rounding rules.

Once you align the points, do the + or -, and now you have to worry about

shifting left to re-normalize.

John Wilson

D Bit

Received on Fri Jun 02 2000 - 11:48:09 BST

*
This archive was generated by hypermail 2.3.0
: Fri Oct 10 2014 - 23:33:00 BST
*