Understanding HP-16C integer division



#2

I was going through the user guide for the HP-16C. On page 41 is this example. I see that it gets the answer it does, but I don't understand how it gets that answer.

The left are the commands from the example, the right is the screen display.

[HEX] 5A0 [ENTER]      5A0 h
[OCT] 177764 177764 o
[/] 177610 o
[HEX] FF88 h

So we are dividing 0x5A0 by 0177764. In my integer world, this should be zero. Can anyone give me the logic behind an answer of 0xFF88?


Edited: 16 Oct 2012, 3:17 a.m.


#3

Expressing everything in decimal:

        1440 / -12 = -120

Look at the status at the top of the example. Two's complement, sixteen bit arithmetic.


- Pauli


#4

The example in the book is 16-bit, 2's complement.

I understand the decimal representation of the bits.

0x5A0   = 00000101 10100000 = 1440
0177764 = 11111111 11110100 = -12
I can understand that the answer is -120 (0xff88), at least logically doing the math in my head. I guess what I don't understand is how you get:
00000101 10100000 /
11111111 11110100
=================
11111111 10001000
I guess I'm just trying to work in my head how it is done. I program in C a lot, so usually think in terms of that. Trying it, if I set each value to a short, then if I do the divide, I get -120. If I use a long, I don't, as 0177764 doesn't set the sign bit in a 32-bit number. You just get zero.

So why does the division work if the number is negative, or am I thinking about it wrong.

I'm guessing the HP-16C has it's division routine coded to handle these different cases. How could you code a division routine so that it always handled things correctly?


#5

The WP 34S has such an integer divide coded. I suspect the 16c is quite different although the answers are the same. The 16c hardware lacks division as a cpu instruction.

My implementation gets rid of the signs, does the division using positive numbers and puts back the appropriate sign at the end.


- Pauli

#6

HI.

Just to add one suggestion to Paul's clarifying follow-up, try this:

[f][DEC]    -120 d <shown briefly or as long as you keep [DEC] pressed>
Cheers.

Luiz (Brazil)

Edited: 16 Oct 2012, 6:39 a.m.

#7

Quote:
I was going through the user guide for the HP-16C. On page 41 is this example. I see that it gets the answer it does, but I don't understand how it gets that answer.

The left are the commands from the example, the right is the screen display.

[HEX] 5A0 [ENTER]      5A0 h
[OCT] 177764 177764 o
[/] 177610 o
[HEX] FF88 h

So we are dividing 0x5A0 by 0177764. In my integer world, this should be zero. Can anyone give me the logic behind an answer of 0xFF88?



Jimi,

A wild educated guess: It might be the bit size you are working with. I am not an expert with the 16C, I don't own a physical one but an app, but I think you can change it. I don't know how though.

Converting 5A0 h to binary gives me 10100000 b (1440)
While 17 7764 o gives me 11110100 b (-12)

I am thinking that the 16C is currently working with 8 bits.

--------------
For comparison purposes, I redid the calculation on the 32 SII and got 0.

5A0 h (0101 1010 0000 b, 1,440)
ENTER
177764 o (1111 1111 1111 0100 b, 65,524)
/

Result: 0 (everywhere. I think the 32 sII operates on 36 bits)

Eddie


#8

Hi, Eddie.

The HP16C allows unsigned, 1's and 2's complement mode representation. The HP32S only works with unsigned, so it cannot emulate the HP16C results, which are correct if 2's complement mode is set.

Cheers.

Luiz (Brazil)


#9

Luiz,

Good to know. Question: what is the difference between 1's and 2's complement? I thought 2's complement was another way of negating numbers.

Thanks,

Eddie

Edited: 16 Oct 2012, 9:05 a.m.


#10

1s compliment is just flipping all of the bits 2s compliment flips all the bits and adds 1.

#11

Get a 34S and you can experience it :-)

#12

One's compliment is an alternate way of specifying negative numbers. Both 2's and 1's comp have their advantages in certain areas. For example, the IPv4 checksum in an IPv4 datagram is in a 1's comp representation because this makes the calculation endian agnostic. This is not so using 2's comp.

It is interesting to note that because negatives are just the compliment of their positive representation, 1's comp has 2 different representations for zero: a 'negative' zero and a 'positive' zero (if there is such a thing for either :-). The negative zero is sometimes displayed as -0 (thinking back semi-fondly of my CDC 6400 days). You can see this on an HP-16C (or DM-16CC, etc.) by doing the following:

DEC
4
f WSIZE
f 1'S
0
BIN <- shows "0 B"
CHS <- shows "1111 B"
CHS <- shows "0 B"
DEC <- shows "0 D"
CHS <- shows "-0 D"
CHS <- shows "0 D"

Positive numbers are identical for both 1's and 2's comp. They only differ in their negative representation. Because there is this oddity of -0, the dynamic range of 1's comp negative numbers is 1 less than that of 2's comp.

For example, assuming a 4 bit number, here is what they look like:

Decimal   2's comp   1's comp
7 0111 0111
6 0110 0110
5 0101 0101
4 0100 0100
3 0011 0011
2 0010 0010
1 0001 0001
0 0000 0000
-0 N/A 1111
-1 1111 1110
-2 1110 1101
-3 1101 1100
-4 1100 1011
-5 1011 1010
-6 1010 1001
-7 1001 1000
-8 1000 N/A

I am sure someone more educated than I can tell why the 2's comp won out over 1's comp. Most of the machines I used in the early 70's were from Control Data Corporation and they used 1's comp (to the best of my recollection). It would be interesting to see a history of the various architectures and when things stabilized in the predominant 2's comp world we see now.


#13

2's complement has the advantage that addition and subtraction work the same as in unsigned mode. In an 8 bit unsigned world, numbers range from 0 to 255. 2'complement numbers range from -128 to +127 where +127 + 1 wraps to -128. It's just a matter of interpreting the results with the left most bit set. In 1's complement, addition of negative numbers needs special treatment.


#14

Marcus has hit the nail on the head. Neil, look at your own 1's complement and 2's complement bit patterns. In a "simple binary adder", the 1's complement case implies that -0 + 1 = 0 !!! (The bit pattern wraps from 1111 to 0000, kind of like 999 + 1 = (1)000, using a 3-digit decimal adder.) In 2's complement, the "simple binary adder" correctly says that -1 + 1 = 0 (same bit patterns). This behavior of 2's complement addition/subtraction close to zero is what's important, and keeps the hardware simple and fast.

Notice, however, with 2's complement, what happens at the 7 + 1 = -8 end, though. You simply MUST be aware of the word length and representation. I've seen any number of cases of code where the programmer was using an 8-bit signed (2's complement) integer and wrote an expression like:

IF (x = 200) THEN ..... END_IF;

There are two problems here. First, the Editor/Compiler in Question is not smart enough to even warn about this, even though it "knows" the Type of "x". Second, and more important, the Implementation in Question treats "200" as a 32-bit signed integer constant, and it promotes the x operand to a 32-bit signed integer before it performs the operation. x is always promoted by "sign extension" -- taking "bit 7" (the high-order bit of the 8-bit integer) and copying it out to the new bits of higher order, thus maintaining its arithmetic value. So the comparison is comparing x (which is always in the range -128 .. 127) to 200, which will never evaluate true.

The first edition of Kernighan and Ritchie "The C Programming Language" kind of "punted" (and told the truth about varied implementations at the time) and stated that the only thing you can infer about integer types from the language definition (not knowing the details of the language implementation) is that a "long int" is "at least as long" as an "int", and an "int" is "at least as long" as a "short int". Ever since, people have debated in standards committees (so, ANSI-C) and written (fairly confusing, in some implementations) header files and compiler options to determine the sizes of these integers.

When the industrial Programmable Controller language standard IEC-61131-3 was written, they cast it in stone: SINT (short signed integer) = 8 bits, INT = 16 bits, DINT (double integer) = 32 bits, and LINT (long integer) = 64 bits. These are all 2's complement signed, to get back on topic....

Dale

#15

One advantage of 2's complement over 1's complement is that it has only one representation of zero. 1's complement has negative and positive zero.

As I recall, another significant advantage of 2's complement is that the same hardware can add and subtract numbers regardless of whether they're positive or negative.


#16

I think this single H/W holds for 1's comp as well. It is just the interpretation of the result that is different. If you are consistently X's compliment, then it is self consistent.

Take the following examples (tried on my trusty 48):

Decimal:   -6 + 6 = 0
1's comp: #1001b + #0110b = #1111b (correct, -0)
2's comp: #1010b + #0110b = #0000b (correct)

Decimal: -6 + 5 = -1
1's comp: #1001b + #0101b = #1110b (correct, -1)
2's comp: #1010b + #0101b = #1111b (correct, -1)

A few years ago I was involved in building a complete TCP/IP stack in H/W and don't recall I had to do anything special with the IPv4 checksum. Mind you, since the rest of the design was is 2's comp, we did have to interpret the 2 forms of 0 when doing comparisons (there goes that self consistent thing... :-).


#17

Neil,

You forgot the third case:

Decimal: -6 + 7 = 1
1's comp: #1001b + #0111b = #0000b (incorrect!)

The same H/W adder can be used to add unsigned or signed integers with 2's comp. But, not with 1's comp -- you would need to increment the result by one if a carry resulted from the adder.

I'm pretty should this is why 2's comp won out and is used almost universally now in digital systems.

-Brian


#18

Argh! Looks like you are right! Looking back in my (really old) Verilog I see I folded the carry into the final summation.

That would definitely answer the question of why one overtook the other.

Thanks for picking that up.

#19

Hi.

Now you have many references, but somehow I thought it would be easier to let HP explain it by itself, so I took these pages from the original HP16C manual, have them 'OCR'ed' and then I composed the PDF.

Cheers.

Luiz (Brazil)


#20

Thanks Luiz! Thanks everyone!


Possibly Related Threads…
Thread Author Replies Views Last Post
  Need help understanding math.... cyrille de Brébisson 9 3,942 12-13-2013, 02:23 AM
Last Post: Didier Lachieze
  Bought a 16C to compensate a little Eelco Rouw 23 8,124 12-07-2013, 01:26 PM
Last Post: Eelco Rouw
  HP Prime polynomial long division bluesun08 13 3,727 10-30-2013, 03:29 AM
Last Post: parisse
  Shiny new 16C! Keith Midson 7 2,629 10-27-2013, 02:22 AM
Last Post: Keith Midson
  HP Prime: Edit integer in RPN mode plivesey 15 5,023 10-18-2013, 04:34 PM
Last Post: kris223
  Prime Edit Integer kris223 8 2,665 09-24-2013, 06:43 PM
Last Post: kris223
  Joys of eBay: HP-32S, HP-32SII, HP-42S, HP-16C, ... Sasu Mattila 7 2,567 09-23-2013, 04:39 PM
Last Post: Julián Miranda (Spain)
  Why does PEMDAS do multiplication and division before addition and subtraction? Don Shepherd 12 3,495 07-31-2013, 10:59 AM
Last Post: robert rozee
  HP-16C simulator fhub 12 3,567 06-30-2013, 10:14 PM
Last Post: Robert Prosperi
  Program for HP-16c... Leonid 9 3,183 06-07-2013, 08:51 PM
Last Post: David Hayden

Forum Jump: