(49g 50g) Fast Pascal's triangle and its relatives
08-11-2018, 04:58 PM (This post was last modified: 12-15-2021 07:26 PM by John Keith.)
Post: #1
 John Keith Senior Member Posts: 840 Joined: Dec 2013
(49g 50g) Fast Pascal's triangle and its relatives
Given an integer on the stack, this program will return the corresponding row of Pascal's triangle. Its speed comes from taking advantage of the symmetry of Pascal's triangle and only calculating explicit values for the left half of the row. Values are calculated by an efficient algorithm that does not require COMB (binomial coefficients). This algorithm, called the "ConvOffs transform" is explained in the seventh comment of the OEIS link below. A general program is in this thread.

This program and the variation below require ListExt 1.3. The program can be easily modified to use the built-in SEQ command if necessary.

Code:
 %%HP: T(3)A(R)F(.); \<< DUP I\->R   IF DUP 1. >   THEN @ special cases for rows less than 4     IF DUP 3. >     THEN DUP 2. / IP SWAP 1. + 2. / IP     ELSE 0.     END  \-> m t  @ main part of program:     \<< 1 SWAP LSEQ DUP 1. m SUB SWAP REVLIST 1. m SUB 2.       \<< PICK3 * SWAP /       \>> DOLIST + DUP 1. t SUB REVLIST +     \>>   ELSE @fake it! 1. SAME { DUP 2. \->LIST } { DROP { 1 } } IFTE   END \>>

A simple variation will return rows of the Narayana triangle. More information here. This program should be run in exact mode since numbers can quickly grow to larger than 12 digits.

Code:
 %%HP: T(3)A(R)F(.); \<< 1 - DUP I\->R   IF DUP 1. >   THEN     IF DUP 3. >     THEN DUP 2. / IP SWAP 1. + 2. / IP     ELSE 0.     END \-> m t     \<< 1 SWAP LSEQ :: + LSCAN DUP 1. m SUB SWAP REVLIST 1. m SUB 2.       \<< PICK3 * SWAP /       \>> DOLIST + DUP 1. t SUB REVLIST +     \>>   ELSE 1. SAME { DUP 2. \->LIST } { DROP { 1 } } IFTE   END \>>

The only changes are the 1 - in the first line since the Narayana triangle begins with row 1 rather than row 0, and the addition of :: + LSCAN in line 8 which creates a list of triangular numbers 1 through n. Many other variations can be had by simple changes as above.
 « 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)