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

Postby petermsiegel on Wed Aug 24, 2022 3:03 pm

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: 140
Joined: Thu Nov 11, 2010 11:04 pm

Re: need a big pascal's table

Postby Veli-Matti on Wed Aug 24, 2022 5:11 pm

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: 93
Joined: Sat Nov 28, 2009 3:12 pm

Re: need a big pascal's table

Postby petermsiegel on Thu Aug 25, 2022 12:59 am

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: 140
Joined: Thu Nov 11, 2010 11:04 pm

Re: need a big pascal's table

Postby Veli-Matti on Thu Aug 25, 2022 7:34 am

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: 93
Joined: Sat Nov 28, 2009 3:12 pm

Re: need a big pascal's table

Postby petermsiegel on Thu Aug 25, 2022 4:34 pm

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: 140
Joined: Thu Nov 11, 2010 11:04 pm

Re: need a big pascal's table

Postby Veli-Matti on Thu Aug 25, 2022 6:38 pm

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
Veli-Matti
 
Posts: 93
Joined: Sat Nov 28, 2009 3:12 pm

Re: need a big pascal's table

Postby petermsiegel on Thu Aug 25, 2022 8:46 pm

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
petermsiegel
 
Posts: 140
Joined: Thu Nov 11, 2010 11:04 pm

Re: need a big pascal's table

Postby tclviii-dyalog on Wed Sep 07, 2022 4:02 pm

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

Postby tclviii-dyalog on Wed Sep 07, 2022 4:35 pm

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

Postby petermsiegel on Wed Sep 07, 2022 9:07 pm

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: 140
Joined: Thu Nov 11, 2010 11:04 pm

PreviousNext

Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest