Dyalog Forums

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

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

And with this small change, it's ready to be an official entry into the dfn library. (It avoids the obscure row increment and runs 6-7% faster.)

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

Really nice.

As a reductio ad absurdum et obscurum, ⌽⍵ happens to be equivalent to 1⌽⍵ here:

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

)save
Cannot 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

There's this odd workaround...

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

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

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.