Post Reply 
(49g 50g) Fast Pascal's triangle and its relatives
08-11-2018, 04:58 PM (This post was last modified: 01-28-2020 09:05 PM by John Keith.)
Post: #1
(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 requires the LSEQ command from the ListExt library. The program can be easily modified to use the built-in SEQ command if necessary. The variation below also requires GoferLists.

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 :: + Scanl1 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 :: + Scanl1 in line 8 which creates a list of triangular numbers 1 through n. Many other variations can be had by simple changes as above.
Find all posts by this user
Quote this message in a reply
08-12-2018, 12:41 AM (This post was last modified: 08-12-2018 12:47 AM by Joe Horn.)
Post: #2
RE: (49g 50g) Fast Pascal's triangle and its relatives
It's probably not very fast, but here's a very short RPL program (48G/GX or later) that returns the Nth row of Pascal's triangle:

Code:
<< IDN ->DIAG NEG PCOEF >>
BYTES: 26.0 #2587h

EDIT: Here's an even smaller one that's a tad faster:
Code:
<< 1. ->LIST -1. CON PCOEF >>
BYTES: 25.5 #E698h

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
08-12-2018, 02:12 PM
Post: #3
RE: (49g 50g) Fast Pascal's triangle and its relatives
Very neat! Slower than mine but less than 1/10 the size!
Find all posts by this user
Quote this message in a reply
08-19-2018, 02:14 PM (This post was last modified: 08-19-2018 07:10 PM by John Keith.)
Post: #4
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.
Find all posts by this user
Quote this message in a reply
08-20-2018, 12:43 AM
Post: #5
RE: (49g 50g) Fast Pascal's triangle and its relatives
(08-19-2018 02:14 PM)John Keith Wrote:  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 +
\>>

Smaller but a tad slower (just thinking of alternative methods for fun):

Code:
\<< 0 + LASTARG SWAP + ADD \>>

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
08-20-2018, 12:15 PM
Post: #6
RE: (49g 50g) Fast Pascal's triangle and its relatives
(08-20-2018 12:43 AM)Joe Horn Wrote:  Smaller but a tad slower (just thinking of alternative methods for fun):

Code:
\<< 0 + LASTARG SWAP + ADD \>>

Very clever! Alternative methods always appreciated. Smile
Find all posts by this user
Quote this message in a reply
03-02-2019, 07:12 PM
Post: #7
RE: (49g 50g) Fast Pascal's triangle and its relatives
(08-20-2018 12:43 AM)Joe Horn Wrote:  Smaller but a tad slower (just thinking of alternative methods for fun):

Code:
\<< 0 + LASTARG SWAP + ADD \>>

Similar idea without using LASTARG:
Code:
\<< 0 OVER + SWAP 0 + ADD \>>

BTW: Both variants work with { 1 } while John Keith's solutions starts working with { 1 1 }.
However they can't use the symmetry and do only half of the work when Pascal's triangle is generated.

Instead we'd have to use two programs say ODD and EVEN that we call alternatively.

ODD
Code:
\<< 0 OVER + REVLIST TAIL REVLIST ADD \>>

EVEN
Code:
\<< 0 OVER + SWAP DUP REVLIST HEAD + ADD \>>

Examples:

{ 1 }
ODD
{ 1 }
EVEN
{ 1 2 }
ODD
{ 1 3 }
EVEN
{ 1 4 6 }
ODD
{ 1 5 10 }
EVEN
{ 1 6 15 20 }
ODD
{ 1 7 21 35 }


Cheers
Thomas
Find all posts by this user
Quote this message in a reply
01-28-2020, 06:12 PM (This post was last modified: 01-28-2020 09:08 PM by John Keith.)
Post: #8
RE: (49g 50g) Fast Pascal's triangle and its relatives
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.
Find all posts by this user
Quote this message in a reply
Post Reply 




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