GCD (Greatest Common Divisior)

[aman-godara]

As suggested in #365, providing gcd function out of the box will be a good addition.

Description

Have a look at these comments to know more:
#365 (comment)
j3-fortran/fortran_proposals#221 (comment)

Prior Art

Many languages provide gcd out of the box.

[Carltoffel]

Do you think it would be a good idea to split gcd into one gcd which swaps the arguments if necessary and another gcd which requires the first argument to be the greater one? I wonder if this could be used in some situations to make the routine a little bit faster.
On the one hand it will just be a tiny performance improvement (if any), on the other hand this would be very easy to implement (gcd with swap calls gcd without swap).

[arjenmarkus]

Even if you have a measurable performance gain, which I pretty much doubt (depending on how you swap things), then you do increase the burden on the user/programmer. They will now have to decide which one to use. Op wo 22 sep. 2021 om 11:26 schreef Carl ***@***.***>:

…

Do you think it would be a good idea to split gcd into one gcd which swaps the arguments if necessary and another gcd which requires the first argument to be the greater one? I wonder if this could be used in some situations to make the routine a little bit faster. On the one hand it will just be a tiny performance improvement (if any), on the other hand this would be very easy to implement (gcd with swap calls gcd without swap). — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#515 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAN6YR6GZ4JUBYR2PZDUCVLUDGOKXANCNFSM5DQYTFVA> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[Sideboard]

I would implement this to get started with stdlib.

[Sideboard]

CC from PR:

Is there interest in a version of gcd that works with a rank-1 array for more than two arguments?

[ivan-pi]

I've used gcd only once before in a derived-type mimicking rational numbers so I can't really estimate wider interest. In that case I would have been happy with the scalar version.

One thing I would point out is the similarity with some of the intrinsic functions, i.e. min(a, b[, c, [d...]]) which accepts two or more scalar arguments, and minval which seeks the minimum value (along a dimension) in an array. Maybe gcdval would be more fitting for the rank-1 array case? (To generalize to all possible dimensions and ranks takes a bit more effort with the preprocessor.)

Currently, the standard does not allow writing variadic functions like min but you can mimic it with optional arguments. I see Python 3.9 added support for an arbitrary number of arguments in math.gcd(*integers).

[aslozada]

Maybe gcdval would be more fitting for the rank-1 array case?

Two cases with arrays:
R https://rdrr.io/cran/DescTools/man/GCD.html
GCD(..., na.rm=FALSE)

Wolfram https://reference.wolfram.com/language/ref/GCD.html
GCD[n1,n2,n3,...]

[ivan-pi]

If we only plan to support two scalars or a vector I'm fine with putting these under the same interface like this:

interface gcd
  elemental function gcd_scalar(a,b) result(res)
    integer, intent(in) :: a, b
    integer :: res
  end function
  function gcd_vector(v) result(res)
    integer, intent(in) :: v(:)
    integer :: res
  end function
end interface

But as a language built on the foundation of arrays, I think a transformational function like shown below, fits well with existing Fortran intrinsics:

function gcdval(array,dim,mask) result(res)
  integer, intent(in) :: array(:,:)
  integer, intent(in) :: dim
  logical, intent(in) :: mask(:,:)
  integer :: res(:)
end function

Maybe @FortranFan is willing to share his opinion on what is the value/need for the val postfix and flexible dimension selection/masking? If gcd where to be proposed to J3 (and they did not reject it under the premise that users can write it themselves) what kind of expectations would there be from an array version?

[milancurcic]

I've never used gcd. The closest to it I did was getting all common denominators and that was in Python. So I can only suggest things here based on what seems would be a nice API, and not any experience.

I don't know whether a gcd with an arbitrary number of inputs is more useful than the gcd with just two. But it would be more general, so even if such need is small, a gcd_vector would be more useful than gcd_scalar. Then the gcd_scalar becomes just a convenience API if somebody doesn't want to wrap a and b into an array, i.e. gcd([a, b]). So, I like the generic gcd that wraps gcd_scalar and gcd_vector.

gcdval also seems nice (consistent API with some intrinsics), assuming that it's useful. Let's discuss that one in a separate issue and PR as it's a different function really.

[ivan-pi]

There were two posts about the GCD algorithm in Hacker News recently:

• Binary GCD: https://news.ycombinator.com/item?id=28819920
• Fast constant-time GCD algorithm and modular inversion: https://news.ycombinator.com/item?id=20172150