conditional test in D-Fns

[BenoitM]

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?

[Veli-Matti]

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

[petermsiegel]

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

[Veli-Matti]

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

[petermsiegel]

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

[Veli-Matti]

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

[petermsiegel]

[THUMBS UP]

[BenoitM]

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]

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

[Veli-Matti]

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