(49g 50g) Fast Pascal's triangle and its relatives

[John Keith]

By definition, each entry in Pascal's triangle is the sum of the two numbers above it. This leads to a very fast method of computing a row of Pascal's triangle given the previous row (as a list) on the stack:

Code:


\<< 2.
  \<< +
  \>> DOSUBS 1 SWAP + 1 +
\>>

The following program returns rows 0 through n of Pascal's triangle as a list of lists. It calculates the first 100 rows (a 63K byte object) in less than 20 seconds. No external libraries are required.

Code:


\<< I\->R \-> n
  \<< { 1 } { 1 1 } 2. n
    FOR k k 1. + DUP 1. + 2. / IP SWAP 2. / IP \-> c f
      \<< DUP 1. c SUB 2.
        \<< +
        \>> DOSUBS 1 SWAP + DUP 1. f SUB REVLIST +
      \>>
    NEXT n 1. + \->LIST
  \>>
\>>

While generating Pascal's triangle is not very useful in general, the entries of Pascal's triangle are the binomial coefficients, which can be useful themselves. As an example, here is a program, based on the one above, which returns the ordered Bell numbers from 0 through n:

Code:


\<< I\->R \-> n
  \<< 1 DUP DUP2 2. \->LIST 2. n
    FOR k k 1. + DUP 1. + 2. / IP SWAP 2. / IP \-> c f
      \<< k 1. + ROLLD k DUPN k \->LIST REVLIST k 2. + ROLL 1. c SUB 2.
        \<< +
        \>> DOSUBS 1 SWAP + DUP 1. f SUB REVLIST + DUP TAIL SWAP UNROT * \GSLIST SWAP
      \>>
    NEXT DROP n 1. + \->LIST
  \>>
\>>

This program should be used in exact mode as the numbers involved are very large. However, all three programs in this post will work on the HP48g/gx.