divisors
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 !
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 !
3 posts
• Page 1 of 1
divisors
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.
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.
And the divisors:
Inspection of the intermediate results in div illustrates why and how it (and ndiv) work:
(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.
)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
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.
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.
-
Adam|Dyalog - Posts: 134
- Joined: Thu Jun 25, 2015 1:13 pm
Re: divisors
I know it's brute-forcier than brute force, but as a tacit fan I like
Or
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?
⎕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
3 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group