13 Sep
2016
13 Sep
'16
7:12 p.m.
On Tue, Sep 13, 2016 at 3:38 PM, Doug Ingraham <dpi at dustyoldcomputers.com>
wrote:
Thanks for an interesting bit of optimization!
Need some more optimization fun? :) Vince and I were working on some code
to add two signed 12 bit numbers and detect overflow, returning MAX_INT or
MIN_INT in AC in the case of overflow, or the sum in AC otherwise. Here's
what Vince came up with so far:
CHKOVF, 0
TAD OVFA /GET A
TAD OVFB /ADD B
DCA OVFSUM /SAVE IT
TAD OVFA /A XOR B
AND OVFB
CMA IAC
TAD OVFA
TAD OVFB
SPA CLA /IF SIGNS DIFFER...
JMP NOPROB /WE'RE DONE
TAD OVFA /MIGHT BE OVERFLOW, A XOR SUM
AND OVFSUM
CMA IAC
TAD OVFA
TAD OVFSUM
SMA /DID WE OVERFLOW (DIFFERENT SIGNS)?
JMP NOPROB /NO, NO PROBLEM
CLA CLL CMA RAR /YES, AC=3777 (MAX INT)
DCA OVFSUM /SAVE IT
TAD OVFA /GET THE SIGN OF CORRECT RESULT
SPA CLA /SHOULD IT BE NEGATIVE?
ISZ OVFSUM /YES, 3777 -> 4000 (MIN INT)
NOPROB, CLA /GET CORRECTED SUM
TAD OVFSUM
JMP I CHKOVF /OUTTA HERE
OVFA, 0
OVFB, 0
OVFSUM, 0
This tests the signs of both numbers; if they differ, there's no chance of
overflow. If they're the same, it checks the signs of the augend with the
sum; if they differ, an overflow occurred, and MAX_INT or MIN_INT will be
returned depending on the sign of the augend.
We tried clever tricks previously, using SNL/SZL and SMA/SPA after shifting
the sign of the augend into the link and keeping the addend in the AC, but
found these to be longer.
Kyle
14 Sep
14 Sep
5:17 a.m.
From: Kyle Owen: Tuesday, September 13, 2016 7:12 PM
TAD OVFA /A XOR B
AND OVFB
CMA IAC
TAD OVFA
TAD OVFB
Sigh.
There seems to be an issue with my implementation of XOR.
Before the CMA IAC there needs to be CLL RAL, to reposition
the carries before subtracting them. Both XORs are affected.
Since all we are interested in is the sign of the XOR results,
only some of the sums end up wrong. Mostly where both
operands are negative; there will be a carry out of the sign
bit when we add them together.
Kyle: I wrote to code to exhaustively enumerate the operand
space, and some Perl to generate "correct" answers. Wrote
the results to simulated paper tape. With the modification
described, the 250Mb result files match. Good thing that
paper tape was a simulated one :-).
Vince
7:42 a.m.
On 14/09/2016 13:17, Vincent Slyngstad wrote:
From: Kyle Owen: Tuesday, September 13, 2016 7:12 PM
Yes, the usual way is just what you describe: A + B - (2 * A AND B),
which works by calculating the bitwise carries and subtracting them from
the addition, to make it carryless. The AND tells you where they result
TAD OVFA /A XOR B
AND OVFB
CMA IAC
TAD OVFA
TAD OVFB
Sigh.
There seems to be an issue with my implementation of XOR.
Before the CMA IAC there needs to be CLL RAL, to reposition the carries
before subtracting them. Both XORs are affected. from but you have to shift them to the correct
positions before taking
the difference. You were missing the multiply x 2 (which
needs the CLL
first). Easily missed.
But unless I've missed something, you don't need a complete XOR, you
just need to check the sign bits.
--
Pete
Pete Turnbull
7:20 a.m.
On 14/09/2016 03:12, Kyle Owen wrote:
Need some more optimization fun? :) Vince and I were
working on some code
to add two signed 12 bit numbers and detect overflow, returning MAX_INT or
MIN_INT in AC in the case of overflow, or the sum in AC otherwise. Here's
what Vince came up with so far:
[ 29 words, 25 instructions, 13 instructions if obviously no overflow]
OK, here's my take on it. Not a huge saving, but 27 words, 23
instructions, 11 if no obvious overflow:
chkovf, 0 / entry point, stores return address
TAD ovfa / get first number
TAD ovfb / add the second
DCA ovfsum / save result
TAD ovfa / get first number again
RAL / save its sign bit
CLA RAR / now just the first sign bit in AC (and L=0)
TAD ovfb / add the second number, see if sign changes
SPA CLA / if result is positive, both were the same sign
JMP done / different signs, must be OK
/ both were same sign, so check for overflow (AC=0)
TAD ovfsum / get the addition result
RAL / save its sign bit
CLA RAR / now just the sign bit in AC, and L=0
TAD ovfa / add one of the operands, see if the sign changes
SMA CLA / if now negative, sign is different from operands
JMP done / positive = no overflow, no problem, done
/ fix for cases of overflow
CLA CLL CMA RAR / make 3777 (MAX INT)
DCA ovfsum / and save it
TAD ovfa / get the sign of correct result
SPA CLA / should it be negative?
ISZ ovfsum / if yes, 3777 -> 4000 (MIN INT)
CLA / really a NOP
done, TAD ovfsum / get the result
JMP I chkovf / fast return if all OK
ovfa, 0
ovfb, 0
ovfsum, 0
--
Pete
Pete Turnbull
9:02 a.m.
From: Pete Turnbull: Wednesday, September 14, 2016 7:20 AM
ISZ ovfsum / if yes, 3777 -> 4000 (MIN INT)
CLA / really a NOP
You should be able to remove the CLA, as that ISZ won't skip
and the AC is already clear.
Yours is definitely better, I think, as the XOR business didn't help
the readability either.
Vince
10:15 a.m.
On 14/09/2016 17:02, Vincent Slyngstad wrote:
From: Pete Turnbull: Wednesday, September 14, 2016
7:20 AM
Of course! LOL! I must have spent half an hour looking at that section
thinking of ways to eliminate one more instruction!
ISZ ovfsum / if yes, 3777 -> 4000 (MIN
INT) CLA
/ really a NOP
You should be able to remove the CLA, as that ISZ won't skip and the AC is already clear.
Hence the comment :-)
--
Pete
Pete Turnbull
3021
days inactive
3021
days old
5 comments
3 participants
participants (3)
-
kylevowen＠gmail.com -
pete＠dunnington.plus.com -
v.slyngstad＠frontier.com