(42S) Big Factorial

[Thomas Klemm]

This program allows to calculate all digits of \(n!\):

Code:

00 { 61-Byte Prgm }
01▸LBL "BIG!"
02 STO 01
03 RCL "1"
04▸LBL 00
05 RCL× 01
06 ENTER
07 RCL÷ 00
08 IP
09 STO "."
10 RCL× 00
11 -
12 INDEX "."
13 J+
14 ENTER
15 DIM?
16 RCL- ST Y
17 GETM
18 STO "."
19 DIM?
20 RCL+ ST Y
21 DIM "."
22 R↓
23 R↓
24 RCL+ "."
25 DSE 01
26 GTO 00
27 END

Question

Is there a better way to shift the elements of an array to the left?

Initialisation

We create an array 1 of length 10 and use 10 digits in each element.

1 ENTER 10 NEWMAT
EDIT
←
1
EXIT
STO "1"

E 10 STO 00

Example

69
XEQ "BIG!"

[ 1×10 Matrix ]

171'122'452
4'281'413'113
7'246'833'888
1'272'839'092
2'705'448'935
2'036'939'364
8'040'923'257
2'797'541'406
4'742'400'000
0

Compare this to:

69! = 171122452'4281413113'7246833888'1272839092'2705448935'2036939364'8040923257'2797​541406'4742400000'0000000000

Here we use 10 digits for each element of the array.
For higher values of \(n\) this needs to be reduced accordingly.
The result of multiplying by \(n\) must fit into the 12 digits provided by the HP-42S.

Using Free42 with its 34 decimal digits allows to calculate \(1000!\) without further adjustments.
You just have to create the array 1 as a [ 1×257 Matrix ].

[Werner]

A quick hack to see if it could be done:
All in the stack, with an automatically growing matrix.
I add a zero to the end (right) of the carry matrix with GROW J+, positioned at the end.
I shift the carry matrix left with a DELR if the leftmost carry is zero, else I enlarge the
value matrix with an INSR, adding a zero to the left.
The 1E10 can be calculated if needed, to be as large as possible without overflowing.

00 { 70-Byte Prgm }
01▸LBL "BIG!"
02 1
03 ENTER
04 NEWMAT
05 1
06 +
07 1ᴇ10
08 X<>Y
09▸LBL 02
10 RCL ST Z
11 ×
12 RCL ST Y
13 ÷
14 ENTER
15 FP
16 STO- ST Y
17 RCL× ST Z
18 X<>Y
19 EDIT
20 J-
21 GROW
22 J+
23 I+
24 X=0?
25 GTO 00
26 EXITALL
27 X<>Y
28 EDIT
29 INSR
30 GTO 01
31▸LBL 00
32 DELR
33▸LBL 01
34 EXITALL
35 +
36 DSE ST Z
37 GTO 02
38 END

Cheers, Werner

[Thomas Klemm]

Very nice.
With this we can calculate \(508!\). At least on the Free42.
The next challenge is to print it as a tree.
I'm not sure if that's possible though. Maybe we need to use a smaller one, e.g. \(284!\).
Or we print the trailing zeros as trunk?

I must admit that I was inspired by this recent post:

[Thomas Klemm]

Well, \(105!\) might work:

           1
          081
         39675
        8240290
       900504101
      30580032964
     9720646107774
    902579144176636
   57322653190990515
  3326984536526808240
 339776398934872029657
99387290781343681609728
          000
          000
          000
          000
          000
          000
        0000000


We only have to do it based on these numbers:

108'139'675
8'240'290'900
5'041'013'058
32'964'972
646'107'774
9'025'791'441
7'663'657'322
6'531'909'905
1'533'269'845
3'652'680'824
339'776'398
9'348'720'296
5'799'387'290
7'813'436'816
972'800'000
0
0

[Thomas Klemm]

It was a bit tedious to do it manually, but at least I have an idea how this could be done with a program.



But I cheated a bit printing the trunk.

[Thomas Klemm]

I would have liked to use Werner's excellent program with:

Code:

07 1ᴇ1

Unfortunately that doesn't work.

Therefore I use:

Code:

07 1ᴇ2

But now we have to split 2-digit numbers and align them with:

Code:

00 { 72-Byte Prgm }
01▸LBL "ALIGN"
02 10
03 ÷
04 ENTER
05 IP
06 STO "."
07 DIM?
08 STO+ ST X
09 X<>Y
10 DIM "."
11 R↓
12 R↓
13 FP
14 10
15 ×
16 TRANS
17 INDEX "."
18 I+
19 PUTM
20 RCL "."
21 TRANS
22 STO "."
23 DIM?
24 ×
25 1
26 DIM "."
27 EDITN "."
28 X=0?
29 DELR
30 EXITALL
31 48
32 STO+ "."
33 END

The variable "." now contains all the digits in a \(n \times 1\) matrix.
The value 48 was added because that is the value for 0 when using XTOA.

Once we have that, we extract groups of digits for each row and combine them with a shrinking list of spaces in the variable " ".

The input for this program is the number of lines to be printed:

Code:

00 { 66-Byte Prgm }
01▸LBL "TREE"
02 STO 00
03 1
04 STO 01
05 STO 02
06 NEWMAT
07 32
08 +
09 STO " "
10 GTO 01
11▸LBL 00
12 EDITN " "
13 DELR
14 EXITALL
15▸LBL 01
16 CLA
17 RCL " "
18 XTOA
19 INDEX "."
20 RCL 01
21 1
22 STOIJ
23 RCL 02
24 X<>Y
25 GETM
26 XTOA
27 PRA
28 RCL 02
29 STO+ 01
30 2
31 STO+ 02
32 DSE 00
33 GTO 00
34 END

Example

105
XEQ "BIG!"

[ 85×1 Matrix ]

XEQ "ALIGN"

12
XEQ "TREE"

The result is similar to the picture already posted.
However, the trunk built with zeros is missing.
I'm leaving that as an exercise.

[Thomas Klemm]

This creates another example of a tree factorial:

81
XEQ "BIG!"

[ 61×1 Matrix ]

XEQ "ALIGN"

11
XEQ "TREE"

[Thomas Klemm]

MATHEMATICAL GAMES
Martin Gardner

Scientific American
Vol. 217, No. 2 (August 1967), pp. 104-109 (6 pages)

[Nihotte(lma)]

(12-16-2024 05:38 PM)Thomas Klemm Wrote:  Very nice.
With this we can calculate \(508!\). At least on the Free42.
The next challenge is ...
...

Hi Thomas and Werner,

I must admit that the calculation of factorials must have inspired many of us and often encouraged us to surpass ourselves.
Always further and always faster if possible!
This led me to learn how to program my SHARP PC-1251 in SC61860 assembler to recover all the digits of increasingly larger factorials!!
Thank you for all this research and the article shared.
Merry Christmas!

Keep you safe

Laurent