Post Reply 
(49g 50g) Fast Pascal's triangle and its relatives
08-11-2018, 04:58 PM (This post was last modified: 08-11-2018 05:01 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 is explained in the seventh comment of the OEIS link below.

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 ROT
@ list of numbers 1..n and its reverse
 LSEQ DUP REVLIST \-> m t a b
@ main part of program:
    \<< a 1. GET b 1. GET 2. m
      FOR j DUP b j GET * a j GET /
      NEXT m 1. + \->LIST 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 ROT LSEQ
    \<< +
    \>> Scanl1 DUP REV \-> m t a b
    \<< a 1. GET b 1. GET 2. m
      FOR j DUP b j GET * a j GET /
      NEXT m 1. + \->LIST 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 lines 8 and 9 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

X<> c
-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
Post Reply 




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