Example Program to calculate Factorial

[Gamo]

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

[damaltor]

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

[Gene]

(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!

[Didier Lachieze]

(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.

[Guenter Schink]

(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

[Dieter]

(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

[Dieter]

(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. ;-)
How about this?

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

[Thomas Okken]

(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).

[Gerson W. Barbosa]

(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

[Dieter]

(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

[Gamo]

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

[Csaba Tizedes]

... 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

[Gerson W. Barbosa]

(01-31-2018 08:23 PM)Dieter Wrote:  How about this?

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

How about that?

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]

[toml_12953]

(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

[Gene]

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

[Gamo]

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

[Thomas Okken]

(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.

[Csaba Tizedes]

(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

[Dieter]

(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

[Dieter]

(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