divisors

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 !

divisors

Postby Roger|Dyalog on Sat Apr 25, 2020 7:14 am

Motivated by a query on the J Forum earlier today, I looked at the computation of the divisors of an integer, and discovered that such a function is not in the dfns workspace. However, the function pco is in the dfns workspace, and is a good place to start.

      )copy dfns pco

2 pco 360
2 3 5
3 2 1
×/ 2 3 5 * 3 2 1
360

2 pco ⍵ returns a 2-row matrix of the prime factors and corresponding exponents. If e are the exponents, then the number of divisors of ⍵ is ×/1+e.

      ndiv←{×/1+1⌷2 pco ⍵}

ndiv 360
24

And the divisors:

      div ← {{⍵[⍋⍵]} , ⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ ↓2 pco ⍵}

div 360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

≢div 360
24

divBF ← {1+⍸0=⍵|⍨1+⍳⍵} ⍝ brute force solution

divBF 360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

(div ≡ divBF)¨ 1+?4 5⍴1e7 ⍝ check some random arguments
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Inspection of the intermediate results in div illustrates why and how it (and ndiv) work:

      2 pco 360               ⍝ start with the primes and exponents
2 3 5
3 2 1
↓ 2 pco 360 ⍝ split into primes and exponents
┌─────┬─────┐
│2 3 5│3 2 1│
└─────┴─────┘
(p e)← ↓ 2 pco 360 ⍝ name them to facilitate explanation
p
2 3 5
e
3 2 1
⍳¨1+e ⍝ all the different ways a prime can contribute
┌───────┬─────┬───┐
│0 1 2 3│0 1 2│0 1│
└───────┴─────┴───┘
p*⍳¨1+e ⍝ the actual contributions
┌───────┬─────┬───┐
│1 2 4 8│1 3 9│1 5│
└───────┴─────┴───┘
⊃ {⍺*⍳¨1+⍵}⌿ p e ⍝ the preceding lines combined into one
┌───────┬─────┬───┐
│1 2 4 8│1 3 9│1 5│
└───────┴─────┴───┘

⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ p e ⍝ all possible products of prime powers
1 5
3 15
9 45

2 10
6 30
18 90

4 20
12 60
36 180

8 40
24 120
72 360
, ⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ p e ⍝ ravel the products
1 5 3 15 9 45 2 10 6 30 18 90 4 20 12 60 36 180 8 40 24 120 72 360

{⍵[⍋⍵]} , ⊃∘.×⌿ ⊃{⍺*⍳¨1+⍵}⌿ p e ⍝ sort them
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

div 360
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360

(Misalignments in the display are due to defects in the APL Chat Forum software.)

Aside: "Tacit" fans will note that the snippet {⍺*⍳¨1+⍵} in div can be written as *∘(⍳¨∘(1∘+)), but in this instance it is not as clear as the dfn, in my opinion. The balance may tip the other way if there is an increment primitive function, such as ≥⍵ ←→ 1+⍵, whence the tacit version becomes *∘(⍳¨∘≥).

From the ideas in the J Wiki Essay Divisors, 2005-11-17.
Roger|Dyalog
 
Posts: 238
Joined: Thu Jul 28, 2011 10:53 am

Re: divisors

Postby Adam|Dyalog on Fri May 01, 2020 10:22 am

Tacit train fan here.

While {⍺*⍳¨1+⍵} as a purely derived non-train function is indeed awkward, the train ⊣*∘⍳¨1+⊢ looks fine, I think. Unfortunately, depending on the cleverness of the interpreter, performance might suffer due to * not using vectorising code, but ⊣*1(⍳¨+)⊢ fixes that. In 18.0 we can write ⊣*1⍳¨⍤+⊢ instead. Of course, an increment function ≥ would allow us to write *∘⍳¨∘≥ or your *∘(⍳¨∘≥) for full performance.
User avatar
Adam|Dyalog
 
Posts: 134
Joined: Thu Jun 25, 2015 1:13 pm

Re: divisors

Postby RichardP|Dyalog on Wed Feb 03, 2021 12:49 pm

I know it's brute-forcier than brute force, but as a tacit fan I like
      ⎕IO←0
{∪⍵∨1+⍳⍵}
(∪⊢∨1+⍳)

Or
      ⎕IO←1
{∪⍵∨⍳⍵}
(∪⊢∨⍳)


Some might consider this code golf, but I think its use of GCD suggests "divisors". It basically says "unique divisors".

Somewhat related, I have a small question about APL implementation:
Is it more desirable that the APLer has an accurate view of the computational complexity of an expression based on the primitives used, or that the APLer can write whatever and hope that one day all expressions are interpreted to the most efficient version that will produce the same result?
RichardP|Dyalog
 
Posts: 30
Joined: Fri Oct 12, 2018 3:05 pm


Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest