(48G/50g) Binomial Transform, Difference Table
01-17-2019, 09:56 PM (This post was last modified: 09-20-2019 02:04 PM by John Keith.)
Post: #1
 John Keith Senior Member Posts: 483 Joined: Dec 2013
(48G/50g) Binomial Transform, Difference Table
Difference tables and the binomial transform are powerful methods for analyzing integer sequences and their underlying logic. See also Conway and Guy, "The Book of Numbers", chapter 3.

Difference tables can be easily created using the \GDLIST (Delta-LIST) command on many HP calculators. Given a list of integers on level 1, the following program returns a difference table as a list of lists:

Code:
 \<< DUP DUP SIZE \-> n   \<< 2. n     START \GDLIST DUP     NEXT DROP n \->LIST   \>> \>>

A simple modification of the program above will return the inverse binomial transform of the list on level 1:

Code:
 \<< DUP SIZE \-> n   \<< 2. n     START DUP HEAD NEWOB SWAP \GDLIST     NEXT EVAL n \->LIST   \>> \>>

Modifying the above program by inserting NEG after \GDLIST will produce the variation described by Thomas Klemm in this post.

And finally another modification returns the binomial transform, the inverse of the function of the program above:

Code:
 \<< DUP HEAD SWAP DUP SIZE \-> n   \<< 2. n     START 2.       \<< +       \>> DOSUBS DUP HEAD NEWOB SWAP     NEXT DROP n \->LIST   \>> \>>

Unlike \GDLIST, the two programs above do not shorten the list. If a list of integers is transformed by one program followed by the other, the original list will return unchanged.

...And one more useful variation, called "inverse summation" in this paper.

Code:
 \<< DUP HEAD NEWOB SWAP \GDLIST + \>>

This is the exact inverse of the cumulative or partial sum, and does not shorten the list.

Edited 9/20/2019 to add NEWOB to binomial transform, inverse binomial transform, and inverse summation programs. This simple addition allows the programs to process much larger lists and makes the programs run somewhat faster.
 « Next Oldest | Next Newest »

 Messages In This Thread (48G/50g) Binomial Transform, Difference Table - John Keith - 01-17-2019 09:56 PM RE: (48G/50g) Binomial Transform, Difference Table - Thomas Klemm - 01-18-2019, 05:53 AM RE: (48G/50g) Binomial Transform, Difference Table - John Keith - 01-18-2019, 08:01 PM RE: (48G/50g) Binomial Transform, Difference Table - Thomas Klemm - 01-18-2019, 08:14 AM RE: (48G/50g) Binomial Transform, Difference Table - John Keith - 01-18-2019, 07:39 PM RE: (48G/50g) Binomial Transform, Difference Table - Thomas Klemm - 01-18-2019, 08:50 PM RE: (48G/50g) Binomial Transform, Difference Table - John Keith - 01-18-2019, 09:44 PM RE: (48G/50g) Binomial Transform, Difference Table - John Keith - 05-27-2019, 09:07 PM

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