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

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (49g 50g) Fast Pascal's triangle and its relatives (/thread-11208.html)

(49g 50g) Fast Pascal's triangle and its relatives - John Keith - 08-11-2018 10:58 AM

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.

RE: (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 01-28-2020 12:12 PM

The programs in the first post have been updated with shorter and faster versions. The first program in the ConvOffs Transform thread has also been updated with the same optimization.

Additional note: The connection between the two programs is that the Narayana triangle is made by transforming the triangular numbers, which are the partial sums of the natural numbers. This idea can be extended ad infinitum by repeated summation.

For example, the tetrahedral numbers are the partial sums of the triangular numbers. The resulting triangle is A056939. This and other examples are shown in Figure 1 of this paper, although the algorithm used in the paper is a different one.

This can also be extended into the realm of transforms. The Narayana transform is related to the binomial transform in the same way that the Narayana triangle is related to Pascal's triangle. Analogous new transforms can be made based on A056939 etc. but as far as I know these theoretical transforms have never been explored.

RE: (49g 50g) Fast Pascal's triangle and its relatives - John Keith - 12-15-2021 01:31 PM

The Narayana triangle in post #1 has been edited to remove dependency on GoferLists. It now uses the ListExt command LSCAN from version 1.3 instead of Scanl1 from GoferLists.