conditional test in D-Fns

Learning APL or new to Dyalog? Ask "silly" questions here, without fear...

conditional test in D-Fns

Postby BenoitM on Sun Aug 14, 2022 10:49 pm

Playing with the 3N+1 problem, I am trying to define a direct function (I do not want to use a procedural function for this) that takes a number and either halves it if it is even, or perform 3N+1 if it is odd.

I tried various things that work on a number, but they do not work on an array such as ⍳100000 or larger.

next←{((odd ⍵)×(1+3×⍵))+((even ⍵)×(⍵÷2))}, alongside even←{0=2⊤⍵} and odd←{0≠2⊤⍵} works on an array but it is very inelegant, and probably takes too much time.

Is there a better way?
BenoitM
 
Posts: 10
Joined: Tue Jan 12, 2021 3:04 pm

Re: conditional test in D-Fns

Postby Veli-Matti on Mon Aug 15, 2022 6:20 am

Hi,
I would write the dfn as
      {(b×1+3×⍵)+⍵×0.5×~b←2|⍵}

but of course there are pretty many ways to do the task.

-Veli-Matti
Veli-Matti
 
Posts: 93
Joined: Sat Nov 28, 2009 3:12 pm

Re: conditional test in D-Fns

Postby petermsiegel on Mon Aug 15, 2022 2:49 pm

How about this definition with a guard and each?
Code: Select all
      ge←{2|⍵: 1+3×⍵ ⋄ ⍵×0.5 }¨         ⍝ guard-each variant
      v_m←{(b×1+3×⍵)+⍵×0.5×~b←2|⍵}      ⍝ Veli-Matti
      (v_m ⍳10000)≡ge ⍳10000
1
      ge 1 1000 10001
4 500 30004
      v_m 1 1000 10001
4 500 30004
     
It's not as fast as Veli-Matti's because of the use of each (¨).
petermsiegel
 
Posts: 141
Joined: Thu Nov 11, 2010 11:04 pm

Re: conditional test in D-Fns

Postby Veli-Matti on Mon Aug 15, 2022 4:42 pm

Exactly!

Of course I first tested with the guarded version, which is the way I usually write code nowadays. Just a quick test with different approaches gives (ver 18.2):
      ]runtime -c  "{(b×1+3×⍵)+⍵×0.5×~b←2|⍵}⍳100000" "(((2∘|)×1+3×⊢)+(~2∘|)×0.5×⊢)⍳100000" "{2|⍵:1+3×⍵ ⋄ ⍵×0.5}¨⍳100000"

{(b×1+3×⍵)+⍵×0.5×~b←2|⍵}⍳100000 → 4.9E¯4 | 0% ⎕
(((2∘|)×1+3×⊢)+(~2∘|)×0.5×⊢)⍳100000 → 4.4E¯4 | -11% ⎕
{2|⍵:1+3×⍵ ⋄ ⍵×0.5}¨⍳100000 → 1.7E¯2 | +3350% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕


-Veli-Matti
Veli-Matti
 
Posts: 93
Joined: Sat Nov 28, 2009 3:12 pm

Re: conditional test in D-Fns

Postby petermsiegel on Mon Aug 15, 2022 8:33 pm

Just for pedagogical fun, I tried the guard version and your "vector-friendly" version with an added twist: there's a long-running function in one of the branches. (I chose the ArcTan function example in the dfns notes.limit documentation, not because anyone would use that code, but to simulate complex code). Here's the result:
Code: Select all
⍝  Paste in ArcTan from notes.limit verbiage, copied from dfns...
   )copy dfns notes.limit
      ...   ⍝ look inside "limit" and copy and ⎕FX the ArcTan function example
⍝  Create variants ge2 and v_m2 that call ArcTan...
   ⎕CR¨ 'ge2' 'v_m2'
{2|⍵:ArcTan ⍵ ⋄ ⍵×0.5}¨   v_m2←{(b×ArcTan¨⍵)+⍵×0.5×~b←2|⍵}
   cmpx 'ge2 ⍳10000' 'v_m2 ⍳10000'
ge2 ⍳10000  → 4.9E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕                   
v_m2 ⍳10000 → 9.4E¯1 | +92% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕


I prefer the vector code you wrote (even in C or C++), except where one or both alternatives are long running or have side effects, such as writing an update file, etc. It took a lot of code to advantage the guard version.

Cheers...
petermsiegel
 
Posts: 141
Joined: Thu Nov 11, 2010 11:04 pm

Re: conditional test in D-Fns

Postby Veli-Matti on Tue Aug 16, 2022 1:13 pm

Yes, for years I have preferred clarity over obfuscation (but have to admit that sometimes I like to play with one-liners just for the old times' sake..). Usually the algorithm is clear with a short dfn as in your example, maintaining the spaghetti code isn't that funny.

There's at least one, a tad shorter, approach to the original problem:
      {2÷⍨@(⍸~b)⊢(1+3×⊢)@(⍸b←2|⍵)⊢⍵}

which is approximately as quick as the previous solutions.

-Veli-Matti
Veli-Matti
 
Posts: 93
Joined: Sat Nov 28, 2009 3:12 pm

Re: conditional test in D-Fns

Postby petermsiegel on Tue Aug 16, 2022 5:19 pm

[THUMBS UP]
petermsiegel
 
Posts: 141
Joined: Thu Nov 11, 2010 11:04 pm

Re: conditional test in D-Fns

Postby BenoitM on Tue Aug 16, 2022 7:22 pm

Veli-Matti, Peter,

Thank you for your help and the insight on what drives execution speed.
In case you are interested, there is a good video on the 3N+1 problem from Veritasium on youtube at https://www.youtube.com/watch?v=094y1Z2wpJg
BenoitM
 
Posts: 10
Joined: Tue Jan 12, 2021 3:04 pm

Re: conditional test in D-Fns

Postby BenoitM on Tue Aug 16, 2022 7:27 pm

And thank you for giving me something to study:
I really do not understand the last one: {2÷⍨@(⍸~b)⊢(1+3×⊢)@(⍸b←2|⍵)⊢⍵}
I will go back to my Bernard Legrand book...
BenoitM
 
Posts: 10
Joined: Tue Jan 12, 2021 3:04 pm

Re: conditional test in D-Fns

Postby Veli-Matti on Wed Aug 17, 2022 6:10 am

Hi, BenitM,

the core of the algorithm is the at operator @, which (in this case) may be thought as (function @ indices) argument which may be shortened to function@indices⊢argument.

First the indices for odd items are stored in b, and the train (1+3×⊢) is used for them (that could be written as {1+3×⍵} as well). NB: the result is the whole vector, not only the changed ones.

After that the even items are changed with function 2÷⍨ (i.e. 0.5× or {⍵÷2}).

Code golfing can be fun :)

-Veli-Matti
Veli-Matti
 
Posts: 93
Joined: Sat Nov 28, 2009 3:12 pm

Next

Return to New to Dyalog?

Who is online

Users browsing this forum: No registered users and 1 guest