Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Numpy gcd function

Does numpy have a gcd function somewhere in its structure of modules?

I'm aware of fractions.gcd but thought a numpy equivalent maybe potentially quicker and work better with numpy datatypes.

I have been unable to uncover anything on google other than this link which seems out of date and I don't know how I would access the _gcd function it suggests exists.

Naively trying:

np.gcd
np.euclid

hasn't worked for me...

like image 786
bph Avatar asked Mar 22 '13 11:03

bph


People also ask

What is gcd function in Python?

Python math.gcd() Method The math.gcd() method returns the greatest common divisor of the two integers int1 and int2. GCD is the largest common divisor that divides the numbers without a remainder. GCD is also known as the highest common factor (HCF). Tip: gcd(0,0) returns 0.

How do you create a gcd function in Python?

Input: # math module contains the gcd function import math # now, let's calculate the gcd of 2 numbers. x = 10 y = 4 hcf = math. gcd(x,y) print(f"The GCD of {x} and {y} is {hcf}.")

How do you find the gcd of an array element in Python?

The Greatest Common Divisor (GCD) of two or more numbers is the largest positive number that divides each number. Python's numpy. gcd() method allows us to calculate the GCD of two numbers or two arrays.


5 Answers

The functions gcd (Greatest Common Divisor) and lcm (Lowest Common Multiple) have been added to numpy in version 1.15.

You can use them both "as is" on a pair of scalars

import numpy as np

np.gcd(-5, 10)  # yields '5'

or on a list or array using .reduce:

np.gcd.reduce(np.array([-5, 10, 0, 5]))  # yields '5'
like image 117
johannes_r Avatar answered Oct 23 '22 22:10

johannes_r


It seems there is no gcd function yet in numpy. However, there is a gcd function in fractions module. If you need to perform gcd on numpy arrays, you could build a ufunc using it:

gcd = numpy.frompyfunc(fractions.gcd, 2, 1)
like image 38
Charles Brunet Avatar answered Oct 23 '22 22:10

Charles Brunet


You can write it yourself:

def numpy_gcd(a, b):
    a, b = np.broadcast_arrays(a, b)
    a = a.copy()
    b = b.copy()
    pos = np.nonzero(b)[0]
    while len(pos) > 0:
        b2 = b[pos]
        a[pos], b[pos] = b2, a[pos] % b2
        pos = pos[b[pos]!=0]
    return a

Here is the code to test the result and speed:

In [181]:
n = 2000
a = np.random.randint(100, 1000, n)
b = np.random.randint(1, 100, n)
al = a.tolist()
bl = b.tolist()
cl = zip(al, bl)
from fractions import gcd
g1 = numpy_gcd(a, b)
g2 = [gcd(x, y) for x, y in cl]
print np.all(g1 == g2)

True

In [182]:
%timeit numpy_gcd(a, b)

1000 loops, best of 3: 721 us per loop

In [183]:
%timeit [gcd(x, y) for x, y in cl]

1000 loops, best of 3: 1.64 ms per loop
like image 22
HYRY Avatar answered Oct 24 '22 00:10

HYRY


Public service announcement for anyone using Python 3.5

from math import gcd
gcd(2, 4)

And if you want to write it yourself in a one-liner:

def gcd(a: int, b: int): return gcd(b, a % b) if b else a
like image 33
lababidi Avatar answered Oct 24 '22 00:10

lababidi


In case the desired result is not an element-wise gcd but rather the gcd of all numbers in the array, you may use the code below.

import numpy as np
from math import gcd as mathgcd

def numpy_set_gcd(a):
    a = np.unique(a)
    if not a.dtype == np.int or a[0] <= 0:
        raise ValueError("Argument must be an array of positive " +
                         "integers.")

    gcd = a[0]
    for i in a[1:]:
        gcd = mathgcd(i, gcd)
        if gcd == 1:
            return 1 

    return gcd

Depending on the use case, it can be faster to omit the sorting step a = np.unique(a).

An alternative (maybe more elegant but slower) implementation using ufuncs is

import numpy as np
from math import gcd as mathgcd
npmathgcd = np.frompyfunc(mathgcd, 2, 1)

def numpy_set_gcd2(a):
    a = np.unique(a)
    if not a.dtype == np.int or a[0] <= 0:
        raise ValueError("Argument must be an array of positive " +
                         "integers.")
    npmathgcd.at(a[1:], np.arange(a.size-1), a[:-1])
    return a[-1]
like image 1
Samufi Avatar answered Oct 23 '22 23:10

Samufi