(49g 50g) Fast Pascal's triangle and its relatives
08-19-2018, 02:14 PM (This post was last modified: 08-19-2018 07:10 PM by John Keith.)
Post: #4
 John Keith Senior Member Posts: 861 Joined: Dec 2013
RE: (49g 50g) Fast Pascal's triangle and its relatives
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.
 « Next Oldest | Next Newest »

 Messages In This Thread (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 08-11-2018, 04:58 PM RE: (49g 50g) Fast Pascal's triangle and its relatives - Joe Horn - 08-12-2018, 12:41 AM RE: (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 08-12-2018, 02:12 PM RE: (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 08-19-2018 02:14 PM RE: (49g 50g) Fast Pascal's triangle and its relatives - Joe Horn - 08-20-2018, 12:43 AM RE: (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 08-20-2018, 12:15 PM RE: (49g 50g) Fast Pascal's triangle and its relatives - Thomas Klemm - 03-02-2019, 07:12 PM RE: (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 01-28-2020, 06:12 PM RE: (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 12-15-2021, 07:31 PM

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