history of the 4-level stack

[axd1967]

Hello,

I'm trying to find out what lead HP to evolve to a 4-stack layout.

The 9100 [1] started with X (keyboard), Y (accu). Browsing the 9100B manual (p. 10) tells me Z is a kind of "temporary" storage (used for 'temporary' storage; the number is stored in the Z register while arithmetic operations are performed on two other numbers in the X and Y registers, then the number in Z can be returned to Y and included once again in the calculation . Use of the Z register saves using the program and data storage registers.), not very convincing.

[2] reads "Experienced HP calculator users have determined that by starting every problem at its innermost number or parentheses and working outward, just as you would with paper and pencil, you maximize the efficiency and power of your HP calculator." Which is not a lie, but does not admit that not all expressions will be solvable with 4 levels... The solution is registers (Section 4).

Likewise, [3] reads "Automatic storage of intermediate results is the reason that the HP-41 C makes solution of even the most complex equations simple." Again, not very honest, seems to me.

Why not more, or less? (Especially when expressions exist that cannot be evaluated with 4 levels.)

Why did they evolve from 3 to 4 levels? I can't believe it is only to be able to provide the T trick (endless provision of a constant for non-commutative ops, [4]).

One hypothesis of mine was that this is somehow related to the three types of operations: sums, products, powers.

Someone hinted that maybe "Architecturally, addressing a fourth thing is pretty cheap, and costs only a few transistors. Adding a FIFTH register, on the other hand, would be a massive change, adding an extra wire to the bus, an extra bit to the microcode field, ...".

I can't recall exactly where someone wrote that T was related to trig calculations.

I started bundling related articles at [5].

rgds,

-alex-

ps - having a 48SX and a swiss micro 15C clone (horrible keys), browsing the 9100 user manual does not give me confidence I would be able to correctly operate a 9100...

[1] http://www.hpmuseum.org/rpnvers.htm#3level
[2] HP-67 Owners Handbook, p. 66 (Automatic stack)
[3] HP-41 C/CV Owner's hb, Section 3 (Automatic stakc)
[4] HP-41 CX owners manual vol 2, p177
[5] https://delicious.com/axd/HP,stack

[walter b]

(09-05-2014 09:11 PM)axd1967 Wrote:  I can't recall exactly where someone wrote that T was related to trig calculations.

Remember you're in a museum. Visiting another room beyond its cafeteria, you'd have found this:



(also exposed in other languages).

d:-)

[walter b]

(09-05-2014 09:11 PM)axd1967 Wrote:  I can't recall exactly where someone wrote that T was related to trig calculations.

BTW, the explanation is also found in one of the threads you collected in [5] (guess which?). You see, collecting's not sufficient, one should still be able to oversee one's collection.

d;-)

[jebem]

Hi Alex, welcome to our MoHPC forums.
Nice thread and question, but I guess the answer will vary depending on your view point.

My 2 cents:
Like any other technology, calculators evolved depending not only on science reasoning but also on other factors constraining the final design (budget, time to delivery, marketing, available technology,...).

So 4 levels seems to be a good number of registers to allow most of math real number operations while allowing humans to remember its contents.
Handling more than that means you are above average memorizing stack contents, or you are using a modern multi line display calculator.
Most of the machines in that era were also programmed, or should I say macro coded, in machine key coding using very basic low level control structures.
This was the beginning of portable computing after all.

It is not a coincidence that when multi line displays arrived to market, new programming paradigms also emerged, like RPL for instance, capable of structured thinking in order to get rid of the machine code spaghetti progamming used before.

[Jeff_Kearns]

(09-05-2014 09:11 PM)axd1967 Wrote:  [1] http://www.hpmuseum.org/rpnvers.htm#3level
[2] HP-67 Owners Handbook, p. 66 (Automatic stack)
[3] HP-41 C/CV Owner's hb, Section 3 (Automatic stakc)
[4] HP-41 CX owners manual vol 2, p177
[5] https://delicious.com/axd/HP,stack

Hi Alex,

Your main questions seem to be, why did HP evolve from a 3-level stack in the 9100 (circa 1968) to a 4-level stack in the HP-35 (circa 1972), and why are there not less or more than 4-level stacks in classic RPN?

First off, the 'true' history of RPN seems rather muddled, and I suggest you read the evolution of RPN and numeric entry on the museum site as a starting point.

The highly recommended reference book: "Algorithms for RPN Calculators", by John A. Ball, 1978, has a section on the history of RPN, wherein he claims the RPN calculator "owes about as much to the venerable mechanical calculator, and to a number of anonymous designers, some of whom worked at Friden, as it does to Jan Lukasiewicz".

'The Definitive Guide to How Computers Do Math", by Clive Maxfield and Alvin Brown, 2005, states that Charles Leonard Hamlin (1822-1985), one of Australia's first computer programmers, pioneered the placement of operators after the operands, and that his method is what became known as reverse Polish notation (RPN).

Even though the Friden EC-130, circa 1964, and the Monroe Epic Calculator, circa 1966, do not mention "RPN" or Lukasiewicz (roughly pronounced woo-ka-shea-vich), they clearly operated according to a postfix, parentheses-free, 'RPN'-like fashion - and they each had a 4-level push-down stack. Undoubtedly, HP improved on this with the repeating T register and seems to be the first company to use the term RPN (which they patented).

I think if you search the archives you will many discussions about RPN stack levels and I would say Jose Mesquita provided a good summary in his response - that it is all about compromise. Less than 4 levels is undesirable (a 2 level stack would be the absolute minimum to even qualify as a calculator) and more than 4 level stacks would make memorization of stack contents difficult for most people.

Jeff K

[axd1967]

(09-06-2014 06:08 AM)walter b Wrote:  

(09-05-2014 09:11 PM)axd1967 Wrote:  I can't recall exactly where someone wrote that T was related to trig calculations.

Remember you're in a museum. Visiting another room beyond its cafeteria, you'd have found this:



(also exposed in other languages).

d:-)

Thx; so what could be the nature of the interaction between trig ops and T? Maybe trig ops involve polynomials, for which the T-drop down is handy? But wouldn't 3 levels also accomplish this?

Edit added: Classic Series Technology says "The final register did double duty as the topmost register in the stack (T) and as a working register for trigonometric functions. Thus when a trig function was used, the topmost value in the stack was lost.".

[axd1967]

Quote:My 2 cents:
Like any other technology, calculators evolved depending not only on science reasoning but also on other factors constraining the final design (budget, time to delivery, marketing, available technology,...).

It feels like this is the main reason for 4 levels, plus the CPU architecture had room for it (and no more!).

[axd1967]

Quote:Even though the Friden EC-130, circa 1964, and the Monroe Epic Calculator, circa 1966, do not mention "RPN" or Lukasiewicz (roughly pronounced woo-ka-shea-vich), they clearly operated according to a postfix, parentheses-free, 'RPN'-like fashion - and they each had a 4-level push-down stack. Undoubtedly, HP improved on this with the repeating T register and seems to be the first company to use the term RPN (which they patented).

Interesting, this suggests that '4' is an interesting value.

Quote:I think if you search the archives you will many discussions about RPN stack levels and I would say Jose Mesquita provided a good summary in his response - that it is all about compromise. Less than 4 levels is undesirable (a 2 level stack would be the absolute minimum to even qualify as a calculator) and more than 4 level stacks would make memorization of stack contents difficult for most people.

Machine searched all archives (1,2,3,4) for "Jose Mesquita" but found nothing, sorry. Can you provide links to the relevant article(s)?

BTW, not sure '4' is an optimal value, see The Magical Number Seven, Plus or Minus Two (although '4' also pops up in the article), which dates from 1956, so HP might have been aware of it.

Meanwhile, I had already found this thread most interesting.

[walter b]

(09-06-2014 06:06 PM)axd1967 Wrote:  

Quote:I think if you search the archives you will many discussions about RPN stack levels and I would say Jose Mesquita provided a good summary in his response - that it is all about compromise. Less than 4 levels is undesirable (a 2 level stack would be the absolute minimum to even qualify as a calculator) and more than 4 level stacks would make memorization of stack contents difficult for most people.

Machine searched all archives (...) for "Jose Mesquita" but found nothing, sorry. Can you provide links to the relevant article(s)?

Good things are sometimes closer than you expect. The user "jebem" is the one you are looking for (post #4).

And about the statement more than 4 level stacks would make memorization of stack contents difficult for most people (read that far more than once here): True for sure but actually nobody needs memorizing all stack contents unless doing high level stack gymnastics. You just have to know how the stack works and that you can trust your intermediate results pop up again just at the right time - that's all. I never had the ambition to memorize all stack contents - nonetheless RPN works for me as well, be it with 4 or 8 levels.

d:-)

[Jeff_Kearns]

(09-06-2014 06:06 PM)axd1967 Wrote:  Machine searched all archives

Try searching with words like: "RPN stack site:hpmuseum.org" and get results like this. In particular, here is a good discussion.

Jeff K

[axd1967]

(09-07-2014 01:33 AM)Jeff_Kearns Wrote:  

(09-06-2014 06:06 PM)axd1967 Wrote:  Machine searched all archives

Try searching with words like: "RPN stack site:hpmuseum.org" and get results like this. In particular, here is a good discussion.

Jeff K

:-) Already found that one! It's the most interesting thread yet.

[axd1967]

Quote:Good things are sometimes closer than you expect. The user "jebem" is the one you are looking for (post #4).

OK - finally got it - we are referring to this thread's post #4. Thx.

For the moment, I still believe 4-stack is the result of CPU architecture.

Questions that remain:

1. Why did trig operations impact T in the 35? Why not 'log', for example? (answered, see #16)
2. Why move from 3 to 4 levels - is there another answer than simply the fact that CPU architecture offered 4? (answered, see post #19)
3. (And, slightly OT: was there a particular reason Friden offered 4 levels?)
   

[peacecalc]

Hello RPN fans,

Quote:walter b wrote: (post #9)

And about the statement more than 4 level stacks would make memorization of stack contents difficult for most people (read that far more than once here): True for sure but actually nobody needs memorizing all stack contents unless doing high level stack gymnastics. You just have to know how the stack works and that you can trust your intermediate results pop up again just at the right time - that's all. I never had the ambition to memorize all stack contents - nonetheless RPN works for me as well, be it with 4 or 8 levels.

Your argument doesn't hold, if you work out a program with such a stack. I often had to draw a sketch where I could see which value is in which stack place . It is a kind of sadism to program stack manipulation over lets say six stack places (with my preferred HP 50g).

Greetings
peaceglue

[Thomas Klemm]

(09-07-2014 10:19 AM)axd1967 Wrote:  Why did trig operations impact T in the 35? Why not 'log', for example?

In short: the pseudo-multiplication used to calculate tangens involves 2 coordinates to keep track of. Thus the list of pseudo-quotients is saved to the stack (c -> stack) and later recalled again (stack -> a):

Code:

tan18:    shift right b[wp]
    shift right b[wp]
tan19:    c - 1 -> c[s]
    if no carry go to tan18
    a + c -> c[wp]
    a - b -> a[wp]
    b exchange c[wp]
tan13:    b -> c[w]
    a - 1 -> a[s]
    if no carry go to tan19
    a exchange c[wp]
    stack -> a
    if b[s] = 0
         then go to tan15
    shift left a[w]
tan14:    a exchange c[wp]
    c -> stack
    shift right b[wp]
    c - 1 -> c[s]
    b exchange c[s]

In case of logarithms it's just one constant that has to be multiplied by the pseudo-quotient and added to a total.

I recommend to have a look at:
HP35 trigonometric algorithm
HP 35 Logarithm Algorithm

Quote:Note that the stack is used (at 01374) destroying thus its top.

Cheers
Thomas

[axd1967]

Quote:It is a kind of sadism to program stack manipulation over lets say six stack places (with my preferred HP 50g).

As Walter writes, it doesn't really matter how much is on the stack; all that matters is the few arguments that the current subroutine needs, and what arguments it is expected to put on the stack before quitting. Because routines can call each other (even recursively), they will add their layers of temporary objects on the stack, but if well written, they will only leave data behind that the caller needs.

A casual user might indeed get lost when interrupting an app that is running deep in calls, but that doesn't matter from the perspective of each routine.

So a well written app should end with no garbage left on the stack, only with the expected output.

[axd1967]

Quote:Note that the stack is used (at 01374) destroying thus its top.

Great! (for 01374, see also here.)

[walter b]

(09-07-2014 02:21 PM)axd1967 Wrote:  

peacecalc Wrote:It is a kind of sadism to program stack manipulation over lets say six stack places (with my preferred HP 50g).

As Walter writes, it doesn't really matter how much is on the stack; all that matters is the few arguments that the current subroutine needs, and what arguments it is expected to put on the stack before quitting.

@axd1967: you're right though actually I was thinking of calculations instead of subroutines.

@peacecalc: definitly. Who does such horrible things?

d:-)

[peacecalc]

Quote:walter b asks:
@peacecalc: definitly. Who does such horrible things?

I'm good in doing such things! I've tried it two or three times, then I compared the performance of the calculator with values hold on the stack (and with necessery manipulations commands) and on the other side code with local variables. I was really disappointed: The stack version isn't faster then the version with locals, and the code with the locals is much more better for reading and debugging.

Greetings
peacecalc

[Jeff_Kearns]

(09-05-2014 09:11 PM)axd1967 Wrote:  Hello,

I'm trying to find out what lead HP to evolve to a 4-stack layout.

Here is a copy/paste from HP Solve Issue 14, 2009-08: The “RPN” Stack - Future & Past (Part 2)

Quote:The “RPN” Stack - Future & Past (Part 2)

In the last issue of HP Solve the RPN stack was described and a resource was referenced that provided all possible reorganizations of the four stack registers. The article finished with the following paragraph. “Why is the HP RPN stack four high? Why did HP use RPN? What was the basis for the first HP RPN pocket calculator? These and other RPN related questions will be discussed in our next issue.”

On May 14, 2009, there was a special event at HP Labs when an IEEE (Institute of Electrical and Electronics Engineers) milestone in electrical engineering and computing presented a plaque honoring HP for its work on the first pocket scientific RPN calculator, the HP-35A. HP invited all members of the HP- 35A design team to attend the award ceremony, and it was a great opportunity for HP Solve to talk to Tom Osborne, the engineer responsible for bringing RPN to HP in the mid 60’s.

Tom designed and built the prototype machine that formed the basis for the HP9100. This famous machine is called the Green Machine because of the Cadillac Green Metallic paint he used on its balsa wood case.

When the HP 9100 was finished Bill Hewlett asked if the same capability could be put into a shirt pocket and the HP-35A evolved. See figure 1. One of the unique features of the HP 9100 was that it included transcenddental functions.

According to Tom the HP-35A stack was only four registers high because that is all that the memory budget would allow. Memory technology was in its infancy and still very expensive. The HP 9100 stack was only three registers high. Tom wanted to make the stack as high as possible. Tom Osborne had spent time at SCM working on an electronic calculator and he had been exposed to RPN. RPN is a natural way to implement arithmetic in electronic circuits. Here is how Tom Osborne explains it.

“No one that I knew at HP Labs was familiar with RPN when I designed the 9100A. The green machine I took to HP was an interesting combination of infix for multiply and divide but post fix for add and subtract. The 9100A stack was high enough to solve most of the normal computations we encountered.
With a bit of mental parsing on the input a 2 deep stack can solve any two operand problem, so we were more than covered. A really deep stack is required if one goes formal and leaves all of the operands in their original order and then relocates the postfix operators (as a full blown parser does).”

“The 9100A stack left the results of a computation in the next to the bottom of the stack (the Y register) - a normal RPN machine would drop the result of a calculation into the bottom of the stack - as I recall, that is what Friden did, and I wanted to avoid any patents they may have had.”
“I also inverted the stack's direction from what was done in computers. That way the dividend and divisor were properly located with the divisor below the dividend. Bob Barton went the other way because he visualized the stack as a stack of dishes at the front end of a cafeteria line where one takes the dish at the top of the stack rather than the one at the bottom of the stack.”

“I probably would have used postfix on store if we had more than 10 storage cells (0-9), but "STO N" seemed much more easily understood than "N STO". However with more than 10 numeric memory cells then RPN would have won because it saves a keystroke. "STO 11" would have to be "STO 11 Enter" vs. "11 STO".”

“By the way, I don't remember how PFN (for Parenthesis Free Notation) first came up. It may have been a customer recommendation. I wish I had thought of it at the beginning - but it’s never too late to make things right ... right?”
You may read more about the development of the HP9100 by Tom Osborne at:
http://www.hp9825.com/html/osborne_s_story.html

[/code]

[axd1967]

Great info, thx!