ENH: Add gcd and lcm ufuncs #8774

eric-wieser · 2017-03-12T03:01:43Z

Fixes #8772, implementing Least Common Multiple and Greatest Common Divisor as ufuncs

Since these are now both in the C++17 stdlib, it seems pretty reasonable that they should be part of numpy as well. Specification matches the C++17 one, where the result is always positive.

Defined for:

signed and unsigned ints
object
- builtin arbitrary-precision longs defer to math.gcd (if available)
- everything else (Decimal, Fraction, ...) defers to ~~fraction.gcd~~ np.core.internal._gcd, but enforcing consistency with math.gcd (returning a positive value)

Not defined for:

bool - doesn't seem useful, since it just decays to logical_or
np.inexact - not well defined

First commit is some minor cleanup to make it easier to see where to add new integer ufuncs. Githubs rendering of this diff is not very clear

eric-wieser · 2017-03-12T03:13:52Z

numpy/core/src/umath/loops.h.src

-U@TYPE@_absolute(char **args, npy_intp *dimensions, npy_intp *steps, void *NPY_UNUSED(func));
-
-NPY_NO_EXPORT void
-@TYPE@_absolute(char **args, npy_intp *dimensions, npy_intp *steps, void *NPY_UNUSED(func));


This commit's diff is just combining U@TYPE@_absolute and @TYPE@_absolute into @S@@TYPE@_absolute, and the same for _sign, _divide, and _remainder. This is already the pattern we use for other functions in this file

eric-wieser · 2017-03-12T03:35:21Z

Not the most efficient of algorithms - CPython 3.5 uses Lehmer's algorithm in math.gcd. But this is better than the python function that would otherwise be written by users of earlier versions of python.

Also, the builtin math.gcd works for arbitrary-precision integers, so actually needs the speed boost for 1000-bit integers - whereas we're limited to 64/128 anyway

eric-wieser · 2017-03-15T23:41:02Z

Ok, tests are added

~~One problem remains - np.gcd(Decimal(1), Decimal(1)) defers to fractions.gcd(Decimal(1), Decimal(1)). On python 3.5, this gives a warning~~

eric-wieser · 2017-03-16T15:38:05Z

All green, documented, and release note'd

homu · 2017-03-23T17:06:26Z

☔ The latest upstream changes (presumably #8795) made this pull request unmergeable. Please resolve the merge conflicts.

WarrenWeckesser · 2017-03-23T21:44:36Z

numpy/core/src/umath/loops.c.src

 /**end repeat**/

 /**begin repeat
 * #TYPE = UBYTE, USHORT, UINT, ULONG, ULONGLONG#
 * #type = npy_ubyte, npy_ushort, npy_uint, npy_ulong, npy_ulonglong#
+ * #c    = u,u,u,ul,ull#


The standard codes for these are B, H, I, L and Q. Shouldn't you use those instead?

Possibly. Although I didn't see much point implementing B, H, and I separately, because arithmetic always promotes to int in C anyway, doesn't it?

~~Can you link me to a file that uses these standard codes?~~ Oh, these are the struct.pack codes, right? I was trying to write this as though it were a free C function, like labs and llabs are to abs. I guess in hindsight they use a prefix though...

A better example of what I was imitating might be strto{l,ll,ul,ull} from the C standard library.

...these are the struct.pack codes, right?

They are also documented in numpy; see https://docs.scipy.org/doc/numpy/reference/arrays.scalars.html#built-in-scalar-types and numpy.typecodes['Integer'], numpy.typecodes['UnsignedInteger'], etc.

homu · 2017-03-27T02:30:06Z

☔ The latest upstream changes (presumably #8847) made this pull request unmergeable. Please resolve the merge conflicts.

mhvk · 2017-05-05T17:52:13Z

Would be quite nice to have this! To me, it looks OK, but maybe e.g. @juliantaylor can have a look?

eric-wieser · 2017-05-06T01:04:41Z

numpy/core/code_generators/generate_umath.py

+          TD('O', f='npy_ObjectGCD'),
+          ),
+'lcm' :
+    Ufunc(2, 1, None,


Got this wrong until now. The identity of gcd is 0 since by definition, gcd(a, 0) == a.

The identity for lcm is some kind of epsilon. For the integers, that epsilon is simply 1 (lcm(a, 1) = a). However, for the rationals, (ie decimal.Decimal), this is incorrect (lcm(0.2, 1) != 0.2), nor is such an epsilon really representable anyway.

homu · 2017-05-08T00:31:09Z

☔ The latest upstream changes (presumably #9063) made this pull request unmergeable. Please resolve the merge conflicts.

eric-wieser · 2017-09-13T06:34:43Z

Rebased for 1.14

mhvk · 2017-12-12T18:22:38Z

I looked again at this, and it all looks fine, except there was the question about which character to use. Also, I'd explicitly check that calling the functions with a float gets you an error, and maybe that it works for a python super-long integer.

Fixes numpy#8772

Now works for builtin `long`, `Decimal`, and `Fraction` types

eric-wieser · 2017-12-13T05:00:20Z

@mhvk: Tests and release notes fixed. I don't think there's a strong argument to be made about the suffices - since they're a private implementation detail, I'd prefer to leave them

mhvk · 2017-12-13T15:10:17Z

OK, that looks great. Merging!

eric-wieser · 2017-12-13T17:12:15Z

Thanks! Glad I won't have to rebase for 1.16 too!

eric-wieser added 01 - Enhancement component: numpy._core labels Mar 12, 2017

eric-wieser force-pushed the lcm-gcd branch from c859224 to f379bb1 Compare March 12, 2017 03:09

eric-wieser changed the title ~~Lcm gcd~~ ENH: Add gcd and lcm ufuncs Mar 12, 2017

eric-wieser commented Mar 12, 2017

View reviewed changes

eric-wieser force-pushed the lcm-gcd branch 3 times, most recently from 160c2a5 to 264c1c7 Compare March 15, 2017 23:40

eric-wieser force-pushed the lcm-gcd branch 2 times, most recently from f881013 to 24774f6 Compare March 16, 2017 15:18

eric-wieser force-pushed the lcm-gcd branch from 24774f6 to 3e324fa Compare March 23, 2017 17:30

eric-wieser mentioned this pull request Mar 23, 2017

ENH: Add the 'heaviside' ufunc. #8795

Merged

WarrenWeckesser reviewed Mar 23, 2017

View reviewed changes

eric-wieser force-pushed the lcm-gcd branch 3 times, most recently from d282345 to 40b4bc8 Compare March 27, 2017 22:14

eric-wieser mentioned this pull request Apr 12, 2017

Missing ufuncs: np.divmod and np.positive #8932

Closed

mhvk mentioned this pull request May 5, 2017

BUG: Various fixes to _dtype_from_pep3118 #9054

Merged

eric-wieser force-pushed the lcm-gcd branch 2 times, most recently from adca9d6 to 36d6cc7 Compare May 6, 2017 01:01

eric-wieser commented May 6, 2017

View reviewed changes

eric-wieser force-pushed the lcm-gcd branch from 36d6cc7 to 7278d17 Compare September 13, 2017 06:34

eric-wieser force-pushed the lcm-gcd branch from 7278d17 to d1513be Compare September 13, 2017 06:40

eric-wieser added the 60 - Major release Issues that need or may be better addressed in a major release label Dec 12, 2017

eric-wieser added 4 commits December 12, 2017 20:58

ENH: Add gcd and lcm ufuncs

7ab0f15

Fixes numpy#8772

ENH: Add support for object arrays

1da646c

Now works for builtin `long`, `Decimal`, and `Fraction` types

TST: Add additional tests of lcm and gcd

bf35ddc

DOC: Add release notes for lcm and gcd

58998a8

eric-wieser force-pushed the lcm-gcd branch from d1513be to 58998a8 Compare December 13, 2017 04:58

eric-wieser added this to the 1.15.0 release milestone Dec 13, 2017

eric-wieser removed the 60 - Major release Issues that need or may be better addressed in a major release label Dec 13, 2017

mhvk merged commit d407f24 into numpy:master Dec 13, 2017

mhvk mentioned this pull request May 18, 2018

ENH: make np.where a ufunc #8994

Open

ganesh-k13 mentioned this pull request Jul 16, 2021

DOC: Add some documentation for adding new UFuncs #19494

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ENH: Add gcd and lcm ufuncs #8774

ENH: Add gcd and lcm ufuncs #8774

eric-wieser commented Mar 12, 2017 •

edited

Loading

eric-wieser Mar 12, 2017

eric-wieser commented Mar 12, 2017 •

edited

Loading

eric-wieser commented Mar 15, 2017 •

edited

Loading

eric-wieser commented Mar 16, 2017

homu commented Mar 23, 2017

WarrenWeckesser Mar 23, 2017

eric-wieser Mar 23, 2017 •

edited

Loading

eric-wieser Mar 23, 2017

WarrenWeckesser Mar 23, 2017

homu commented Mar 27, 2017

mhvk commented May 5, 2017

eric-wieser May 6, 2017 •

edited

Loading

homu commented May 8, 2017

eric-wieser commented Sep 13, 2017

mhvk commented Dec 12, 2017

eric-wieser commented Dec 13, 2017

mhvk commented Dec 13, 2017

eric-wieser commented Dec 13, 2017

ENH: Add gcd and lcm ufuncs #8774

ENH: Add gcd and lcm ufuncs #8774

Conversation

eric-wieser commented Mar 12, 2017 • edited Loading

eric-wieser Mar 12, 2017

Choose a reason for hiding this comment

eric-wieser commented Mar 12, 2017 • edited Loading

eric-wieser commented Mar 15, 2017 • edited Loading

eric-wieser commented Mar 16, 2017

homu commented Mar 23, 2017

WarrenWeckesser Mar 23, 2017

Choose a reason for hiding this comment

eric-wieser Mar 23, 2017 • edited Loading

Choose a reason for hiding this comment

eric-wieser Mar 23, 2017

Choose a reason for hiding this comment

WarrenWeckesser Mar 23, 2017

Choose a reason for hiding this comment

homu commented Mar 27, 2017

mhvk commented May 5, 2017

eric-wieser May 6, 2017 • edited Loading

Choose a reason for hiding this comment

homu commented May 8, 2017

eric-wieser commented Sep 13, 2017

mhvk commented Dec 12, 2017

eric-wieser commented Dec 13, 2017

mhvk commented Dec 13, 2017

eric-wieser commented Dec 13, 2017

eric-wieser commented Mar 12, 2017 •

edited

Loading

eric-wieser commented Mar 12, 2017 •

edited

Loading

eric-wieser commented Mar 15, 2017 •

edited

Loading

eric-wieser Mar 23, 2017 •

edited

Loading

eric-wieser May 6, 2017 •

edited

Loading