need a big pascal's table

[petermsiegel]

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

[Veli-Matti]

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

[petermsiegel]

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.)

[Veli-Matti]

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

[petermsiegel]

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
 }

[Veli-Matti]

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

[petermsiegel]

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  >>>    ⌊    <<<
 } 
      ⎕WA
6440150232
      ]runtime 'pascalCD6a 15000' 
* Benchmarking "pascalCD6a 15000"
              (ms) 
 CPU (avg):  14678 
 Elapsed:    17699 

[tclviii-dyalog]

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]

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

[petermsiegel]

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.