## need a big pascal's table

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

### Re: need a big pascal's table

Veli-Matti,

Very nice (and much closer to our intuition of how to solve it)...

I'm assuming you have ⎕ML≥2. With ⎕ML∊0 1, the train (↑⌽) would be (⊃⌽).

In any case, a very nice volley of code improvements. I'm curious (but not curious enough) as to whether Python or similar could code it in a similarly elegant way (via numPy?) with comparable performance improvements. There is a routine: scipy.linalg.pascal that does it for you.

Good show, Veli-Matti! (And good luck to you, tclviii-dyalog, in your adventures).
-Pete
petermsiegel

Posts: 127
Joined: Thu Nov 11, 2010 11:04 pm

### Re: need a big pascal's table

Once an APL2 bigot, always an APL2 bigot..
..but thanks for appraisal :)

A couple of millisecs can be gained by just a couple of minor changes
`      pascalCD3←{     (⎕IO ⎕ML)←0 3 ⋄ ⎕FR←(⍵>999)(↑⌽)645 1287     ∆←⍵ ⍵⍴0 ⋄ ∆[;0]←1 ⋄ r←0     ∆⊣{∆[r;⍳1+r⊣r+←1]←(⍵,0)+0,⍵}⍣(⍵-1)⊢1 }`

I have to admit that the ..1+r⊣r+←1.. part puzzled me for some time, but then it hit me!

Thanks for nice challenge, both of you!
-wm
Veli-Matti

Posts: 92
Joined: Sat Nov 28, 2009 3:12 pm

### Re: need a big pascal's table

And with this small change,
Code: Select all
`∆⊣{∆[≢⍵;⍳1+≢⍵]←(⍵,0)+0,⍵}⍣(⍵-1)⊢1`
it's ready to be an official entry into the dfn library. (It avoids the obscure row increment and runs 6-7% faster.)
petermsiegel

Posts: 127
Joined: Thu Nov 11, 2010 11:04 pm

### Re: need a big pascal's table

Good grief! (why didn't I notice that?)

Here's a short recap of the development:
`      ⍝      ]runtime "pascal0 1000"   ⍝ ⍉(⍳⍵)∘.!⍳⍵ Elapsed:    41365       ]runtime "pascal1 1000"   ⍝ (∘.≥⍨v)×(⊢!⍉)⍵ ⍵⍴v←¯1+⍳⍵ Elapsed:    40769       ]runtime "pascal1a 1000"  ⍝ 1,0⍪×\(∘.≥⍨v)×((⌽v-1)⌽r⍴⌽v)÷(r←2⍴⍵-1)⍴v←⍳⍵-1 Elapsed:     267       ]runtime "pascal2 1000"   ⍝ Peter: q,←c←⌊c×(n-k)÷k Elapsed:     516       ]runtime "pascal3 1000"   ⍝ m[r;1+i]←×\(⌽i)÷i←⍳r-1 Elapsed:     166       ]runtime "pascal4 1000"   ⍝ m⊣{m[r;1↓⍳r]←×\(⌽÷⊢)⍳r-r+←1}⍣⍵-1⊢1 Elapsed:     159       ]runtime "pascalCD 1000"  ⍝ Peter: ∆⊣CNext⍣(⍵-1)⊣1 Elapsed:      91`

The nice invention (for me at least) is the idiom
`      {1,×\(⌽÷⊢)⍳⍵-1} (⎕IO=1)`
which may be used for getting the coefficients for n'th row of the Pascal triangle.

pascalCD was so effective, that testing with bigger data was feasible (Win10 & 64-bit 18.2, 2.5G workspace):
`      ⍝      ]runtime "pascalCD 10000"   Elapsed:    9341       ]runtime "pascalCD2 10000" ⍝ ∆⊣{∆[r;⍳1+r⊣r+←1]←(⍵,0)+0,⍵}⍣(⍵-1)⊢1 Elapsed:    3530       ]runtime "pascalCD3 10000" ⍝ Peter: ∆⊣{∆[≢⍵;⍳1+≢⍵]←(⍵,0)+0,⍵}⍣(⍵-1)⊢1 Elapsed:    3498       ]runtime "pascalCD4 10000" Elapsed:    3434`

The differences are small, so I cannot boast having made the quickest one, but at least there's a different approach:
`      pascalCD4←{     (⎕IO ⎕ML)←0 3 ⋄ ⎕FR←(⍵>999)(↑⌽)645 1287      ⊃∆⊣{↑∆,←⊂(1∘⌽+⊢)0,⍵}⍣(⍵-1)⊢∆←1 }`

-wm
Veli-Matti

Posts: 92
Joined: Sat Nov 28, 2009 3:12 pm

### Re: need a big pascal's table

Really nice.

As a reductio ad absurdum et obscurum, ⌽⍵ happens to be equivalent to 1⌽⍵ here:
Code: Select all
`  pascalCD5←{     (⎕IO ⎕ML)←0 3 ⋄ ⎕FR←(⍵>999)(↑⌽)645 1287      ⊃∆⊣{↑∆,←⊂(⌽+⊢)0,⍵}⍣(⍵-1)⊢∆←1 }`
petermsiegel

Posts: 127
Joined: Thu Nov 11, 2010 11:04 pm

### Re: need a big pascal's table

Of course...

Good news: I found even quicker solution:

`      ⍝      ]runtime -c "pascalCD6 1000" "pascalCD3 1000"  pascalCD6 1000 → 3.2E¯3 |     0% ⎕⎕⎕                                        pascalCD3 1000 → 3.9E¯2 | +1118% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕`

Bad news: there's something fishy when the size goes beyond 1000 :(

`      ⍝      ]runtime "pascalCD3 1000"  ⍝ ∆⊣{∆[≢⍵;⍳1+≢⍵]←(⍵,0)+0,⍵}⍣(⍵-1)⊢1 CPU (avg):    47  Elapsed:      47       ]runtime "pascalCD6 1000"   CPU (avg):     0  Elapsed:       8      ]runtime "pascalCD6 1100"  * Benchmarking "pascalCD6 1100"* Command Execution Failed: DOMAIN ERROR`

After that you'll run into _real_ problems

`      )saveCannot perform operation when # is referenced by session namespace.Reached via:⎕SE.SALTUtils...dmx...EN`

The function:
`      pascalCD6←{     (⎕IO ⎕ML)←0 3 ⋄ ⎕FR←(⍵>999)(↑⌽)645 1287     ⊃∆⊣{↑∆,←⊂2+/0,⍵,0}⍣(⍵-1)⊢∆←1 }`

I have already reported this to Dyalog.

-wm
Veli-Matti

Posts: 92
Joined: Sat Nov 28, 2009 3:12 pm

### Re: need a big pascal's table

There's this odd workaround...
Code: Select all
`pascalCD6a←{ ⍝ Theory: problem for 2+/ with decimal floats???                             ⎕IO ⎕ML←0 2 ⋄ ⎕FR←(⍵>999)(↑⌽)645 1287     ⊃∆⊣{↑∆,←⊂2+/⌊0,⍵,0}⍣(⍵-1)⊢∆←1    ⍝  Add  >>>    ⌊    <<< }       ⎕WA6440150232      ]runtime 'pascalCD6a 15000' * Benchmarking "pascalCD6a 15000"              (ms)  CPU (avg):  14678  Elapsed:    17699 `
petermsiegel

Posts: 127
Joined: Thu Nov 11, 2010 11:04 pm

### Re: need a big pascal's table

now that i have stopped herding Elsinore, New Jersey, and Canadian, ducklings, I can address this
(be nicer to Karen Shaw people, i had no idea what she goes through till i was tasked with the New York meeting)

first let me thank everybody for their efforts, you all went above and beyond.

having looked at everything, i was reminded of an old article of Roger's about the diagonals of pascals triangle, where i first saw the idea that

pascal[i+1;]←(0,pascal[i;])+pascal[i;],0
(the answer to every problem is always and old HUI article, isnt it? and if the answer is not and old HUI article, it's an old SCHOLES article)

But, I learned my APL before left tacks and right tacks, forks, power operators and tacit programming etc, So I decided to try going completely "old school"

so first a straightforward circa 1970 implementation

∇ result←pascal∆loop∆iota rows;⎕IO;bv;i;⎕FR;triangle
⍝ return pascals triangle using bignums
⎕FR←1287 ⍝ big nums
⎕IO←1 ⍝ ive 5 fingers, not 4 fingers and a zeroeth thumb
bv←rows⍴start ⍝ before loop control, branch vectors were fastest way to loop
bv[rows]←out
i←1
triangle←(rows,rows)↑1
start:
triangle[i+1;⍳i+1]←(0,triangle[i;⍳i])+triangle[i;⍳i],0
end:→bv[i←i+1]
out:result←triangle

⎕TS ⋄ sink←pascal∆loop∆iota 10000 ⋄ ⎕TS
2022 9 7 11 48 16 842
2022 9 7 11 48 19 476

and pascalCD4 (that is the fastest, isnt it?)
⎕TS ⋄ sink←pascalCD4 10000 ⋄ ⎕TS
2022 9 7 11 28 19 402
2022 9 7 11 28 21 958

so, almost the same

it's nice to know that an old man's guile and cunning can keep up with the kid's youth and fancy tacit tacky forks
tclviii-dyalog

Posts: 28
Joined: Tue Mar 02, 2010 6:04 pm

### Re: need a big pascal's table

just saw that pascalCD6a might be faster than pascalCD4

⎕TS ⋄ sink←pascal∆loop∆iota 10000 ⋄ ⎕TS
2022 9 7 12 32 56 50
2022 9 7 12 32 58 979
⎕TS ⋄ sink←pascalCD6a 10000 ⋄ ⎕TS
2022 9 7 12 33 21 700
2022 9 7 12 33 25 49

still pretty close
tclviii-dyalog

Posts: 28
Joined: Tue Mar 02, 2010 6:04 pm

### Re: need a big pascal's table

Good show. I can save you 5% with the new-fangled power operator, but you are right: the goto style performs just as well and saving 240 ms isn't important at all here. It's a fun exercise, but "proves" the old adage that the programmer's productivity is more important than the computer time.
petermsiegel

Posts: 127
Joined: Thu Nov 11, 2010 11:04 pm

PreviousNext