Example Program to calculate Factorial
01-31-2018, 12:22 PM (This post was last modified: 01-31-2018 12:23 PM by Gamo.)
Post: #1
 Gamo Senior Member Posts: 605 Joined: Dec 2016
Example Program to calculate Factorial
I adapted this "Factorial Program" example from HP-25 Owner's Handbook and according to the hand book that let you see how this program work by your own.
I have changed the program to work for HP-11C or any other HP RPN programmable calculator that have conditional test and labels.
This intended to show the program steps as simple as possible to understand.

This example attached as PDF file.

Gamo

Attached File(s)
01-31-2018, 02:59 PM
Post: #2
 damaltor Member Posts: 231 Joined: Dec 2015
RE: Example Program to calculate Factorial
Great! This is also the Example used by Wikipedia for the HP-16C. That example has only nine steps, though it does not employ the validity check at the start, and the 16C has the DSZ (decrement, skip if zero) instruction that the 11C does not. It should be possible to make something out of the DSE instruction though. still i like about your program that it is easier to overlook which is good for starters, as the wikipedia example is heavily optimized and not as easy to understand on first look.

Maybe one could extend the Example on to "how to save space" or similar if the second program was added.

this is it:
Code:
001 LBL F   43,22, F  Define label F (mnemonic for "factorial") 002 x<>I    42 22     Store x in register I 003 1       1         Store 1 in x 004 LBL 0   43,22, 0  Define label 0 005 RCL I   45 32     Recall register I into x 006 ×       20        Multiply x and y 007 DSZ     43 23     Decrement register I and if not zero ... 008 GTO 0   22 0      ... go back to label 0 009 RTN     43 21     Stop program - result displayed in x
01-31-2018, 06:42 PM (This post was last modified: 01-31-2018 06:44 PM by Gene.)
Post: #3
 Gene Moderator Posts: 1,034 Joined: Dec 2013
RE: Example Program to calculate Factorial
(01-31-2018 02:59 PM)damaltor Wrote:  ...the 16C has the DSZ (decrement, skip if zero) instruction that the 11C does not.

Gene: Good point!
01-31-2018, 07:50 PM
Post: #4
 Didier Lachieze Senior Member Posts: 1,221 Joined: Dec 2013
RE: Example Program to calculate Factorial
(01-31-2018 06:42 PM)Gene Wrote:
(01-31-2018 02:59 PM)damaltor Wrote:  ...the 16C has the DSZ (decrement, skip if zero) instruction that the 11C does not.

Gene: Good point!

DSE works as well as DSZ in this case as the fractional part of the counter is zero !
Just replace DSZ by DSE at step 7, and LBL F by e.g. LBL A at step 1 and the 16C program above works perfectly on the 11C.
01-31-2018, 07:50 PM
Post: #5
 Guenter Schink Senior Member Posts: 346 Joined: Dec 2013
RE: Example Program to calculate Factorial
(01-31-2018 06:42 PM)Gene Wrote:
(01-31-2018 02:59 PM)damaltor Wrote:  ...the 16C has the DSZ (decrement, skip if zero) instruction that the 11C does not.

Gene: Good point!

But with an integer as counter DSE has the same effect as DSZ, me thinks.

Günter
01-31-2018, 08:01 PM (This post was last modified: 01-31-2018 08:06 PM by Dieter.)
Post: #6
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: Example Program to calculate Factorial
(01-31-2018 02:59 PM)damaltor Wrote:  ...the 16C has the DSZ (decrement, skip if zero) instruction that the 11C does not. It should be possible to make something out of the DSE instruction though.

Just replace DSZ with DSE. Since we're dealing with integers both will work.

BTW, is there another HP calculator that appeared after 1977 which features DSZ and ISZ instead of the more flexible DSE/ISG commands?
Until now I thought that the 19C/29C had been the last ones.

(01-31-2018 02:59 PM)damaltor Wrote:  this is it:

How does it behave if you enter zero ?-)
Simply add two steps at the beginning:

Code:
LBL F x=0? 1 ...

...and you're done.

Dieter
01-31-2018, 08:23 PM
Post: #7
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: Example Program to calculate Factorial
(01-31-2018 12:22 PM)Gamo Wrote:  I have changed the program to work for HP-11C or any other HP RPN programmable calculator that have conditional test and labels.

Any calculator with label addressing and an x=y? test. ;-)

(01-31-2018 12:22 PM)Gamo Wrote:  This intended to show the program step tests as simple as possible to understand.

For "as simple as possible" it still looks quite complicated. ;-)

Code:
01  LBL A   Factorial  02  ABS     Make sure input is not negative 03  INT     Make sure input is an integer 04  X=0?    If input is zero... 05  1       ...then change it into 1 (0! = 1! = 1) 06  STO 1   Store input n as initial product 07  LBL 3   Start of loop 08  1    09  -       decrement factor 10  X=0?    has factor become zero? 11  GTO 2   then quit program 12  STOx1   else multiply product by factor 13  GTO 3   and do another loop 14  LBL 2   exit routine: 15  RCL 1   Recall result 16  RTN     and quit

Think simple. :-)

Dieter
01-31-2018, 08:47 PM (This post was last modified: 01-31-2018 09:19 PM by Thomas Okken.)
Post: #8
 Thomas Okken Senior Member Posts: 1,055 Joined: Feb 2014
RE: Example Program to calculate Factorial
(01-31-2018 08:23 PM)Dieter Wrote:  Think simple. :-)

HP-25 style:

Code:
01 ABS     Make sure input is not negative 02 INT     Make sure input is an integer 03 1       This starts the product 04 X<>Y 05 GTO 10 06 *       Multiply product by current factor 07 LASTX   Find next factor 08 1 09 - 10 X≠0?    If current factor is nonzero, continue 11 GTO 06   12 RDN     Retrieve product from Y 13 GTO 00

EDIT: Rearranged code slightly to make the flow of control look a bit cleaner (didn't save any GTOs, though).
01-31-2018, 10:04 PM (This post was last modified: 01-31-2018 10:07 PM by Gerson W. Barbosa.)
Post: #9
 Gerson W. Barbosa Senior Member Posts: 1,332 Joined: Dec 2013
RE: Example Program to calculate Factorial
(01-31-2018 08:47 PM)Thomas Okken Wrote:  HP-25 style:

Code:
01 ABS     Make sure input is not negative 02 INT     Make sure input is an integer 03 1       This starts the product 04 X<>Y 05 GTO 10 06 *       Multiply product by current factor 07 LASTX   Find next factor 08 1 09 - 10 X≠0?    If current factor is nonzero, continue 11 GTO 06   12 RDN     Retrieve product from Y 13 GTO 00

0h, and I thought mine was good enough… At least now I know what I could have done to save yet one more step. Thanks!
Done it on my 33C. I didn’t care to make sure the input was an integer or greater than zero as I was not aware of that requirement.
Code:
 01 1 02 x<>y 03 x=0 04 GTO 11 05 * 06 LASTx 07 1 08 - 09 x>0 10 GTO 05 11 Rv 12 GTO 00
01-31-2018, 10:54 PM
Post: #10
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: Example Program to calculate Factorial
(01-31-2018 08:47 PM)Thomas Okken Wrote:  HP-25 style:
...
EDIT: Rearranged code slightly to make the flow of control look a bit cleaner (didn't save any GTOs, though).

(01-31-2018 10:04 PM)Gerson W. Barbosa Wrote:  0h, and I thought mine was good enough… At least now I know what I could have done to save yet one more step. Thanks!
Done it on my 33C. I didn’t care to make sure the input was an integer or greater than zero as I was not aware of that requirement.

Then add two steps penalty. ;-)

Here's my HP25 / HP33E/C version:

Code:
01 ABS     Make sure input is not negative 02 INT     Make sure input is an integer 03 1       This starts the product 04 X<>Y 05 X=0?    If the factor has become zero 06 GTO 12  then exit 07 *       else multiply product by current factor 08 LASTX   Find next factor 09 1 10 - 11 GTO 05  Next loop 12 R↓      Retrieve product from Y 13 GTO 00  and quit

A bit cleaner than Thomas' version and one step shorter than Gerson's (if you add ABS INT). And finally it even works with calculators that only feature a very limited set of test commands – only x=0? is required.

BTW all this is better than HP's own factorial program in the HP25 Applications Programs book (p. 110) which requires one register and does not even handle 0! correctly. Instead it gets stuck in an infinite loop... #-)

Dieter
02-01-2018, 01:50 AM (This post was last modified: 02-01-2018 01:51 AM by Gamo.)
Post: #11
 Gamo Senior Member Posts: 605 Joined: Dec 2016
RE: Example Program to calculate Factorial
Dieter program for HP 25 version is very well done that even include ABS and INT. Very short and really simple easy to understand program so far.

I added the ABS steps to work for HP-12C and still the program steps is under 20 steps.

Code:
 01  ENTER 02  x 03  SQR 04  INTG 05  1 06  X<>Y 07  X=0 08  GTO 14 09  x 10  LSTx 11  1 12  - 13  GTO 07 14  Roll Down 15  GTO 00

Gamo
02-01-2018, 08:06 PM
Post: #12
 Csaba Tizedes Senior Member Posts: 467 Joined: May 2014
RE: Example Program to calculate Factorial
... and HP-12C version in engineer style:

The core is 3 steps:
Code:
01: LN 02: \GS- 03: GTO 01

Preparation for use required to clear statistics registers, store your number (N) in R1, then goto the start of program memory, run the program and you'll get the -LN(N!) in R2.
You can get N! if you type
Code:
RCL 2 CHS e^x

If you like waste some memory you can program it fully (9 steps):
Code:
01: STO 1 02: LN 03: \GS- 04: x=0 05: GTO 07 06: GTO 02 07: RCL 2 08: CHS 09: e^x

Use:
1.) f CLEAR \GS
2.) f CLEAR PRGM
3.) Type N
4.) R/S

Benchmark:
69! = 1.711224655E99, running time: 62 secs on "classic" 12C Made in Brazil (S/N: 3107B...)

Some hints are welcome to optimize the code (twisted GTO 07/02 really terrible)

Csaba
02-02-2018, 12:59 AM (This post was last modified: 02-04-2018 03:43 AM by Gerson W. Barbosa.)
Post: #13
 Gerson W. Barbosa Senior Member Posts: 1,332 Joined: Dec 2013
RE: Example Program to calculate Factorial

Code:
01  LBL A   Factorial  02  ABS     Make sure input is not negative 03  INT     Make sure input is an integer 04  X=0?    If input is zero... 05  1       ...then change it into 1 (0! = 1! = 1) 06  STO 1   Store input n as initial product 07  LBL 3   Start of loop 08  1    09  -       decrement factor 10  X=0?    has factor become zero? 11  GTO 2   then quit program 12  STOx1   else multiply product by factor 13  GTO 3   and do another loop 14  LBL 2   exit routine: 15  RCL 1   Recall result 16  RTN     and quit

Code:
 01 LBL A 02 ABS 03 INT 04 x=0 05 e^x 06 1 07 STO I 08 LBL 1 09 STO* I 10 1 11 + 12 x<=y 13 GTO 1 14 Rv        15 x<>I 16 RTN

Same number of steps, but you can always can make it shorter :-) (not by simply removing line #14, of course).

Gerson.

PS: Well, you’ve had your chance. In order to make it three steps shorter just remove the redundant steps 03 through 05. Also, instead of using the specific instruction x<>I it’s better to use the more general instructions R/\ and RCL I after GTO 01.

But what is the point implementing the factorial function on a calculator that has it already built-in?

HP-33C/E

Code:
 01 ABS             ; optional 02 1 03 STO 0 04 STO* 0 05 1 06 + 07 x<=y 08 GTO 04 09 Rv              ; optional  10 Rv              ; optional  11 RCL 0 12 GTO 00
[/quote]
02-02-2018, 01:16 AM
Post: #14
 toml_12953 Senior Member Posts: 1,468 Joined: Dec 2013
RE: Example Program to calculate Factorial
(02-01-2018 08:06 PM)Csaba Tizedes Wrote:  Benchmark:
69! = 1.711224655E99, running time: 62 secs on "classic" 12C Made in Brazil (S/N: 3107B...)

But it's wrong!

69! is 1.711224655 E 98

Tom L
If you buy a drink for someone in order to congratulate them,
is it a Mazel Tov cocktail?
02-02-2018, 02:44 AM
Post: #15
 Gene Moderator Posts: 1,034 Joined: Dec 2013
RE: Example Program to calculate Factorial
For historical purposes and ideas...

Here is factorial from V2N10P11 of PPC Journal:

01 STO 0
02 GTO 05
03 -
04 ST0 x 0
05 1
06 X<Y
07 GTO 03
08 X=Y
09 RCL 00
10 GTO 00 (or R/S)

Here is factorial from V3N5P4

01 STO 0
02 1
03 -
04 STO x 0
05 1
06 X NE Y
07 GTO 03
08 RCL 0
09 GTO 00

Also from V3N5P4

01 ENTER
02 ENTER
03 1
04 X=Y
05 GTO 10
06 -
07 X
08 LASTX
09 GTO 03
10 RDN
11 RDN
12 GTO 00
02-02-2018, 03:41 AM (This post was last modified: 02-02-2018 03:46 AM by Gamo.)
Post: #16
 Gamo Senior Member Posts: 605 Joined: Dec 2016
RE: Example Program to calculate Factorial
When we make our own program somehow the internal function compute faster than programs version. Is this due to the advantage of build-in functions is in ROM or algorithm formula program is better than our own program? Like these factorial programs.
For modern 12C+ or 15C LE no speed differences.

Gamo
02-02-2018, 05:05 AM
Post: #17
 Thomas Okken Senior Member Posts: 1,055 Joined: Feb 2014
RE: Example Program to calculate Factorial
(02-02-2018 03:41 AM)Gamo Wrote:  When we make our own program somehow the internal function compute faster than programs version. Is this due to the advantage of build-in functions is in ROM or algorithm formula program is better than our own program? Like these factorial programs.
For modern 12C+ or 15C LE no speed differences.

It is possible that the ROM uses a better algorithm, but in the case of n!, I think the basic multiplication is used everywhere.

The reason user programs are slower than ROM routines is because of the extra work the calculator has to do while executing user code: it has to fetch the user code instructions from memory, then decode and execute them, one by one for each program step.

When it is running a ROM routine, only the machine code that performs the calculation is executed; when it is running user code, it has to do all that work *and* the work of decoding and executing the user code instructions.

How much that overhead adds up to depends on various details, and can vary a lot. For example, on my HP-42S, calculating 253! with the built-in N! function takes about 2 seconds, while the program takes about 12 seconds, so 6 times slower; in Free42, the program is only 1.5 times slower than the built-in function.
02-02-2018, 07:39 AM
Post: #18
 Csaba Tizedes Senior Member Posts: 467 Joined: May 2014
RE: Example Program to calculate Factorial
(02-02-2018 01:16 AM)toml_12953 Wrote:
(02-01-2018 08:06 PM)Csaba Tizedes Wrote:  Benchmark:
69! = 1.711224655E99, running time: 62 secs on "classic" 12C Made in Brazil (S/N: 3107B...)

But it's wrong!

69! is 1.711224655 E 98

Tom, you know, I have a lovely secretary Ms. Type. She's so cute but I must to correct she's typos always. I'll correct it, thanks.

By the way your answer clearly shows you don't tried my 3 steps solution.

If I posted it in 2003 and if Valentine Albillo had been here he answer something like this: 'Hey, Csaba, this is REALLY interesting idea to implement a counter using statistics. And that' s foolish to make logarithm and summing with \GS'

All the above solutions are use the classic 'grab the numbers and make the product of them'. My idea is that, make the logarithm of the product and use the automatic counting of statistics AND make summation IN ONE STEP.

Therefore the factorial function CAN BE implement ONLY in 3 steps.
The other steps only for non-engineer users.

Csaba
02-02-2018, 08:28 AM
Post: #19
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: Example Program to calculate Factorial
(02-02-2018 02:44 AM)Gene Wrote:  For historical purposes and ideas...

Here is factorial from V2N10P11 of PPC Journal:

01 STO 0
02 GTO 05
03 -
04 ST0 x 0
05 1
06 X<Y
07 GTO 03
08 X=Y
09 RCL 00
10 GTO 00 (or R/S)

That's a nice one.

(02-02-2018 02:44 AM)Gene Wrote:  Here is factorial from V3N5P4

01 STO 0
02 1
03 -
04 STO x 0
05 1
06 X NE Y
07 GTO 03
08 RCL 0
09 GTO 00

This one doesn't get 0! right and it even fails for 1!. Both inputs cause an infinite loop. But that's not worse than the solution in the Applications Progams book which fails in the same way – just another example of poor programming by HP themselves. I really wonder if they were not able to do better or if they simply didn't care. #-\

(02-02-2018 02:44 AM)Gene Wrote:  Also from V3N5P4

01 ENTER
02 ENTER
03 1
04 X=Y
05 GTO 10
06 -
07 X
08 LASTX
09 GTO 03
10 RDN
11 RDN
12 GTO 00

And that one also cannot handle 0!.

Dieter
02-02-2018, 08:44 AM
Post: #20
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: Example Program to calculate Factorial
(02-02-2018 05:05 AM)Thomas Okken Wrote:  It is possible that the ROM uses a better algorithm, but in the case of n!, I think the basic multiplication is used everywhere.

Now take a real (hardware) HP35s and calculate a few factorials:

100! ... 120! ... 150! ... the calculation takes about one second until the result is displayed. Then continue:
155! ... 157! ... 158! ... again, it takes about 1½ seconds.
159! ... 160! ... and now the answer is returned almost immediately. Up to 253! it gets only slightly slower, finally about half a second is required. So 250! is about twice as fast as 150!.

What's going on there? Since the 35s factorial key also handles the Gamma function and Gamma is calculated faster than a simple factorial (yes – try 150! and 150,2!) I suspect this may be related to a fast Gamma code.

Dieter
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)