GCD and LCM

Let your imagination run wild

GCD and LCM

PostPosted by drab » Mon Oct 20, 2014 3:33 pm

Primitive functions Or and And could be extended to integer arguments doing Greatest Common Divisor and Least Common Multiple.

Once upon a time, we actually had this implemented in APL2, but we ended up removing it because it had some problems with floating point arguments.

But I think it could probably be rigorous for integer and rational arguments. It could still be very useful in many simple cases, even if it just gave an error instead of a poor answer for some hard cases.
drab
 
Posts: 282
Joined: Thu Oct 09, 2014 6:23 am

Re: GCD and LCM

PostPosted by forummaster » Mon Oct 20, 2014 4:02 pm

Good news, that's already done:
Code: Select all
      12∧9
36
      12∨9
3
forummaster
 
Posts: 534
Joined: Wed Jan 23, 2013 1:00 pm

Re: GCD and LCM

PostPosted by forummaster » Mon Oct 20, 2014 4:03 pm

Please tell me more about the problems with floating point arguments.
forummaster
 
Posts: 534
Joined: Wed Jan 23, 2013 1:00 pm

Re: GCD and LCM

PostPosted by drab » Tue Oct 21, 2014 9:36 am

Great! I didn't see any documentation for it, and I was silly enough not to try it.

Sorry, I don't remember the problems, but maybe I can investigate it.
drab
 
Posts: 282
Joined: Thu Oct 09, 2014 6:23 am

Re: GCD and LCM

PostPosted by forummaster » Tue Oct 21, 2014 10:52 am

drab wrote:Great! I didn't see any documentation for it, ...

Due to my laziness and workload, generally I don't document stuff already documented elsewhere such as the Extended APL Standard or the APL2 Reference Manual unless there's some significant difference with what is in NARS2000.
forummaster
 
Posts: 534
Joined: Wed Jan 23, 2013 1:00 pm

Re: GCD and LCM

PostPosted by drab » Tue Oct 21, 2014 11:15 am

This is unexpected ...

12∧9.2
1.035827914E16
12r1∧9.2
1035827914_______

It makes sense if the trailing underscores are zeros.

Is that a bug, or some kind of new enhanced output? :-)
drab
 
Posts: 282
Joined: Thu Oct 09, 2014 6:23 am

Re: GCD and LCM

PostPosted by forummaster » Tue Oct 21, 2014 1:20 pm

drab wrote:This is unexpected ...

12∧9.2
1.035827914E16
12r1∧9.2
1035827914_______

It makes sense if the trailing underscores are zeros.

Is that a bug, or some kind of new enhanced output? :-)

The two results are consistent (although you might question if they are accurate) with a larger ⎕PP such as
Code: Select all
      ⎕PP←20
      12∧9.2
10358279142952140
      12x∧9.2
10358279142952140

In any case, that's what happens when one blindly follows Euclid's algorithm.

In general, I don't see how to obtain a meaningful result on floats. Perhaps I should enforce integer tolerance and signal a DOMAIN ERROR if not.

On the other hand, on Dyalog 14.0
Code: Select all
      12∧9.2
275.99999999999994

so I should be able to do better. Still, GCD/LCM on floats just doesn't sound right. I'm liking DOMAIN ERROR.

What do you think?

BTW, the trailing underscores indicate that there are more digits to display in the result, but ⎕PP is too small (10 in your case).
forummaster
 
Posts: 534
Joined: Wed Jan 23, 2013 1:00 pm

Re: GCD and LCM

PostPosted by drab » Tue Oct 21, 2014 3:06 pm

I wasn't questioning the accuracy (yet).

I was wondering about the trailing underscores.
drab
 
Posts: 282
Joined: Thu Oct 09, 2014 6:23 am

Re: GCD and LCM

PostPosted by drab » Tue Oct 21, 2014 5:09 pm

Here is an example that doesn't look right ...

2 ∧ ⎕←2+0.1×⍳9
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9
42 22 1.294784893E15 12 10 26 1.519964874E15 14 58

I think the answer should be:

42 22 46 12 10 26 54 14 58
drab
 
Posts: 282
Joined: Thu Oct 09, 2014 6:23 am

Re: GCD and LCM

PostPosted by drab » Wed Oct 22, 2014 7:22 am

I was right about what it should be ...

2 ∧ ⎕←2+(⍳9)÷10x
21r10 11r5 23r10 12r5 5r2 13r5 27r10 14r5 29r10
42 22 46 12 10 26 54 14 58
drab
 
Posts: 282
Joined: Thu Oct 09, 2014 6:23 am

Next

Return to New Primitive Operators

Who is online

Users browsing this forum: No registered users and 1 guest

cron